{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,11,3]],"date-time":"2026-11-03T18:30:26Z","timestamp":1793730626756,"version":"4.6.1"},"reference-count":38,"publisher":"Institute of Mathematical Statistics","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Ann. Statist."],"published-print":{"date-parts":[[2007,12,1]]},"abstract":"<jats:p>In many important statistical applications, the number of variables or parameters p is much larger than the number of observations n. Suppose then that we have observations y=X\u03b2+z, where \u03b2\u2208Rp is a parameter vector of interest, X is a data matrix with possibly far fewer rows than columns, n\u226ap, and the zi\u2019s are i.i.d. N(0, \u03c32). Is it possible to estimate \u03b2 reliably based on the noisy data y? To estimate \u03b2, we introduce a new estimator\u2014we call it the Dantzig selector\u2014which is a solution to the \u21131-regularization problem $$\\min_{\\tilde{\\beta}\\in\\mathbf{R}^{p}}\\|\\tilde{\\beta}\\|_{\\ell_{1}}\\quad\\mbox{subject to}\\quad \\|X^{*}r\\|_{\\ell_{\\infty}}\\leq(1+t^{-1})\\sqrt{2\\log p}\\cdot\\sigma,$$ where r is the residual vector y\u2212X\u03b2\u0303 and t is a positive scalar. We show that if X obeys a uniform uncertainty principle (with unit-normed columns) and if the true parameter vector \u03b2 is sufficiently sparse (which here roughly guarantees that the model is identifiable), then with very large probability, \u2016\u03b2\u0302\u2212\u03b2\u2016\u211322\u2264C2\u22c52log\u2009p\u22c5(\u03c32+\u2211imin(\u03b2i2, \u03c32)). Our results are nonasymptotic and we give values for the constant C. Even though n may be much smaller than p, our estimator achieves a loss within a logarithmic factor of the ideal mean squared error one would achieve with an oracle which would supply perfect information about which coordinates are nonzero, and which were above the noise level. In multivariate regression and from a model selection viewpoint, our result says that it is possible nearly to select the best subset of variables by solving a very simple convex program, which, in fact, can easily be recast as a convenient linear program (LP).<\/jats:p>","DOI":"10.1214\/009053606000001523","type":"journal-article","created":{"date-parts":[[2008,3,5]],"date-time":"2008-03-05T12:59:38Z","timestamp":1204721978000},"page":"2313-2351","source":"Crossref","is-referenced-by-count":1720,"title":["The Dantzig selector: Statistical estimation when p is much larger than n"],"prefix":"10.1214","volume":"35","author":[{"given":"Emmanuel","family":"Candes","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Terence","family":"Tao","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"108","reference":[{"key":"38","doi-asserted-by":"publisher","unstructured":"Tibshirani, R. (1996). Regression shrinkage and selection via the lasso. <i>J. Roy. Statist. Soc. Ser. B<\/i> <b>58<\/b> 267\u2013288.","DOI":"10.1111\/j.2517-6161.1996.tb02080.x"},{"key":"36","doi-asserted-by":"publisher","unstructured":"Schwarz, G. (1978). Estimating the dimension of a model. <i>Ann. Statist.<\/i> <b>6<\/b> 461\u2013464.","DOI":"10.1214\/aos\/1176344136"},{"key":"15","doi-asserted-by":"publisher","unstructured":"Chen, S. S., Donoho, D. L. and Saunders, M. A. (1998). Atomic decomposition by basis pursuit. <i>SIAM J. Sci. Comput.<\/i> <b>20<\/b> 33\u201361.","DOI":"10.1137\/S1064827596304010"},{"key":"25","doi-asserted-by":"publisher","unstructured":"Fan, J. and Peng, H. (2004). Nonconcave penalized likelihood with a diverging number of parameters. <i>Ann. Statist.<\/i> <b>32<\/b> 928\u2013961.","DOI":"10.1214\/009053604000000256"},{"key":"21","doi-asserted-by":"publisher","unstructured":"Donoho, D. L. and Johnstone, I. M. (1994). Ideal spatial adaptation by wavelet shrinkage. <i>Biometrika<\/i> <b>81<\/b> 425\u2013455.","DOI":"10.1093\/biomet\/81.3.425"},{"key":"34","doi-asserted-by":"publisher","unstructured":"Rudin, L. I., Osher, S. and Fatemi, E. (1992). Nonlinear total variation based noise removal algorithms. <i>Physica D<\/i> <b>60<\/b> 259\u2013268.","DOI":"10.1016\/0167-2789(92)90242-F"},{"key":"26","doi-asserted-by":"publisher","unstructured":"Foster, D. P. and George, E. I. (1994). The risk inflation criterion for multiple regression. <i>Ann. Statist.<\/i> <b>22<\/b> 1947\u20131975.","DOI":"10.1214\/aos\/1176325766"},{"key":"23","unstructured":"Donoho, D. L. and Johnstone, I. M. (1995). Empirical atomic decomposition. Unpublished manuscript."},{"key":"3","doi-asserted-by":"publisher","unstructured":"Baraud, Y. (2000). Model selection for regression on a fixed design. <i>Probab. Theory Related Fields<\/i> <b>117<\/b> 467\u2013493.","DOI":"10.1007\/PL00008731"},{"key":"2","doi-asserted-by":"publisher","unstructured":"Antoniadis, A. and Fan, J. (2001). Regularization of wavelet approximations (with discussion). <i>J. Amer. Statist. Assoc.<\/i> <b>96<\/b> 939\u2013967.","DOI":"10.1198\/016214501753208942"},{"key":"31","doi-asserted-by":"crossref","unstructured":"Mallows, C. L. (1973). Some comments on $C_p$. <i>Technometrics<\/i> <b>15<\/b> 661\u2013675.","DOI":"10.1080\/00401706.1973.10489103"},{"key":"1","doi-asserted-by":"publisher","unstructured":"Akaike, H. (1974). A new look at the statistical model identification. <i>IEEE Trans. Automatic Control<\/i> <b>19<\/b> 716\u2013723.","DOI":"10.1109\/TAC.1974.1100705"},{"key":"7","doi-asserted-by":"publisher","unstructured":"Birg\u00e9, L. and Massart, P. (2001). Gaussian model selection. <i>J. Eur. Math. Soc.<\/i> <b>3<\/b> 203\u2013268.","DOI":"10.1007\/s100970100031"},{"key":"5","doi-asserted-by":"publisher","unstructured":"Barron, A. R. and Cover, T. M. (1991). Minimum complexity density estimation. <i>IEEE Trans. Inform. Theory<\/i> <b>37<\/b> 1034\u20131054.","DOI":"10.1109\/18.86996"},{"key":"22","unstructured":"Donoho, D. L. and Johnstone, I. M. (1994). Ideal denoising in an orthonormal basis chosen from a library of bases. <i>C. R. Acad. Sci. Paris S\u00e9r. I Math.<\/i> <b>319<\/b> 1317\u20131322."},{"key":"28","doi-asserted-by":"publisher","unstructured":"Greenshtein, E. and Ritov, Y. (2004). Persistence in high-dimensional linear predictor selection and the virtue of overparametrization. <i>Bernoulli<\/i> <b>10<\/b> 971\u2013988.","DOI":"10.3150\/bj\/1106314846"},{"key":"4","doi-asserted-by":"publisher","unstructured":"Barron, A. R., Birg\u00e9, L. and Massart, P. (1999). Risk bounds for model selection via penalization. <i>Probab. Theory Related Fields<\/i> <b>113<\/b> 301\u2013413.","DOI":"10.1007\/s004400050210"},{"key":"6","doi-asserted-by":"crossref","unstructured":"Birg\u00e9, L. and Massart, P. (1997). From model selection to adaptive estimation. In <i>Festschrift for Lucien Le Cam<\/i> (D. Pollard, E. Torgersen and G. L. Yang, eds.) 55\u201387. Springer, New York.","DOI":"10.1007\/978-1-4612-1880-7_4"},{"key":"8","doi-asserted-by":"crossref","unstructured":"Boyd, S. and Vandenberghe L. (2004). <i>Convex Optimization<\/i>. Cambridge Univ. Press.","DOI":"10.1017\/CBO9780511804441"},{"key":"10","doi-asserted-by":"publisher","unstructured":"Cand\u00e8s, E. J., Romberg, J. and Tao, T. (2006). Stable signal recovery from incomplete and inaccurate measurements. <i>Comm. Pure Appl. Math.<\/i> <b>59<\/b> 1207\u20131223.","DOI":"10.1002\/cpa.20124"},{"key":"11","doi-asserted-by":"publisher","unstructured":"Cand\u00e8s, E. J., Romberg, J. and Tao, T. (2006). Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information. <i>IEEE Trans. Inform. Theory<\/i> <b>52<\/b> 489\u2013509.","DOI":"10.1109\/TIT.2005.862083"},{"key":"12","doi-asserted-by":"crossref","unstructured":"Cand\u00e8s, E. J., Rudelson, M., Vershynin, R. and Tao, T. (2005). Error correction via linear programming. In <i>Proc. 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS)<\/i> 295\u2013308. IEEE, Los Alamitos, CA.","DOI":"10.1109\/SFCS.2005.5464411"},{"key":"13","doi-asserted-by":"publisher","unstructured":"Cand\u00e8s, E. J. and Tao, T. (2005). Decoding by linear programming. <i>IEEE Trans. Inform. Theory<\/i> <b>51<\/b> 4203\u20134215.","DOI":"10.1109\/TIT.2005.858979"},{"key":"14","doi-asserted-by":"publisher","unstructured":"Cand\u00e8s, E. J. and Tao, T. (2006). Near-optimal signal recovery from random projections: Universal encoding strategies? <i>IEEE Trans. Inform. Theory<\/i> <b>52<\/b> 5406\u20135425.","DOI":"10.1109\/TIT.2006.885507"},{"key":"16","doi-asserted-by":"crossref","unstructured":"Daniel, B. L., Yen, Y. F., Glover, G. H. et al. (1998). Breast disease: Dynamic spiral MR imaging. <i>Radiology<\/i> <b>209<\/b> 499\u2013509.","DOI":"10.1148\/radiology.209.2.9807580"},{"key":"17","unstructured":"Daubechies, I. (2005). Personal communication."},{"key":"18","doi-asserted-by":"publisher","unstructured":"Donoho, D. L. (2006). For most large underdetermined systems of linear equations the minimal $\\ell_1$-norm solution is also the sparsest solution. <i>Comm. Pure Appl. Math.<\/i> <b>59<\/b> 797\u2013829.","DOI":"10.1002\/cpa.20132"},{"key":"19","doi-asserted-by":"publisher","unstructured":"Donoho, D. L. (2006). Compressed sensing. <i>IEEE Trans. Inform. Theory<\/i> <b>52<\/b> 1289\u20131306.","DOI":"10.1109\/TIT.2006.871582"},{"key":"20","doi-asserted-by":"publisher","unstructured":"Donoho, D. L. and Huo, X. (2001). Uncertainty principles and ideal atomic decomposition. <i>IEEE Trans. Inform. Theory<\/i> <b>47<\/b> 2845\u20132862.","DOI":"10.1109\/18.959265"},{"key":"24","doi-asserted-by":"publisher","unstructured":"Elad, M. and Bruckstein, A. M. (2002). A generalized uncertainty principle and sparse representation in pairs of bases. <i>IEEE Trans. Inform. Theory<\/i> <b>48<\/b> 2558\u20132567.","DOI":"10.1109\/TIT.2002.801410"},{"key":"27","doi-asserted-by":"publisher","unstructured":"Fuchs, J. (2004). On sparse representations in arbitrary redundant bases. <i>IEEE Trans. Inform. Theory<\/i> <b>50<\/b> 1341\u20131344.","DOI":"10.1109\/TIT.2004.828141"},{"key":"29","doi-asserted-by":"publisher","unstructured":"Haupt, J. and Nowak, R. (2006). Signal reconstruction from noisy random projections. <i>IEEE Trans. Inform. Theory<\/i> <b>52<\/b> 4036\u20134048.","DOI":"10.1109\/TIT.2006.880031"},{"key":"30","unstructured":"Kettenring, J., Lindsay, B. and Siegmund, D., eds. (2003). Statistics: Challenges and opportunities for the twenty-first century. NSF report. Available at www.pnl.gov\/scales\/docs\/nsf_report.pdf."},{"key":"32","doi-asserted-by":"publisher","unstructured":"Natarajan, B. K. (1995). Sparse approximate solutions to linear systems. <i>SIAM J. Comput.<\/i> <b>24<\/b> 227\u2013234.","DOI":"10.1137\/S0097539792240406"},{"key":"33","doi-asserted-by":"crossref","unstructured":"Peters, D. C., Korosec, F. R., Grist, T. M., Block, W. F., Holden, J. E., Vigen, K. K. and Mistretta, C. A. (2000). Undersampled projection reconstruction applied to MR angiography. <i>Magnetic Resonance in Medicine<\/i> <b>43<\/b> 91\u2013101.","DOI":"10.1002\/(SICI)1522-2594(200001)43:1<91::AID-MRM11>3.0.CO;2-4"},{"key":"35","doi-asserted-by":"crossref","unstructured":"Sardy, S., Bruce, A. G. and Tseng, P. (2000). Block coordinate relaxation methods for nonparametric wavelet denoising. <i>J. Comput. Graph. Statist.<\/i> <b>9<\/b> 361\u2013379.","DOI":"10.1080\/10618600.2000.10474885"},{"key":"37","doi-asserted-by":"publisher","unstructured":"Szarek, S. J. (1991). Condition numbers of random matrices. <i>J. Complexity<\/i> <b>7<\/b> 131\u2013149.","DOI":"10.1016\/0885-064X(91)90002-F"},{"key":"9","doi-asserted-by":"crossref","unstructured":"Cand\u00e8s, E. J. and Romberg, J. (2005). Practical signal recovery from random projections. In <i>Computational Imaging III<i>:<\/i> Proc. SPIE International Symposium on Electronic Imaging <\/i> <b>1<\/b> 76\u201386. San Jose, CA.","DOI":"10.1117\/12.600722"}],"container-title":["The Annals of Statistics"],"original-title":[],"link":[{"URL":"https:\/\/projecteuclid.org\/download\/pdfview_1\/euclid.aos\/1201012958","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,10,10]],"date-time":"2026-10-10T00:05:33Z","timestamp":1791590733000},"score":1,"resource":{"primary":{"URL":"https:\/\/projecteuclid.org\/journals\/annals-of-statistics\/volume-35\/issue-6\/The-Dantzig-selector--Statistical-estimation-when-p-is-much\/10.1214\/009053606000001523.full"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2007,12,1]]},"references-count":38,"journal-issue":{"issue":"6","published-online":{"date-parts":[[2007,12,1]]}},"URL":"https:\/\/doi.org\/10.1214\/009053606000001523","relation":{},"ISSN":["0090-5364","2168-8966"],"issn-type":[{"value":"0090-5364","type":"print"},{"value":"2168-8966","type":"electronic"}],"subject":[],"published":{"date-parts":[[2007,12,1]]}}}