The DOI matches its Crossref record; 35 of the 35 references it cites were found in a registry or an index.
Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)
Abstract
The problem of consistently estimating the sparsity pattern of a vector beta* isin Rpbased on observations contaminated by noise arises in various contexts, including signal denoising, sparse approximation, compressed sensing, and model selection. We analyze the behavior of l1-constrained quadratic programming (QP), also referred to as the Lasso, for recovering the sparsity pattern. Our main result is to establish precise conditions on the problem dimension p, the number k of nonzero elements in beta*, and the number of observations n that are necessary and sufficient for sparsity pattern recovery using the Lasso. We first analyze the case of observations made using deterministic design matrices and sub-Gaussian additive noise, and provide sufficient conditions for support recovery and linfin-error bounds, as well as results showing the necessity of incoherence and bounds on the minimum value. We then turn to the case of random designs, in which each row of the design is drawn from a N (0, Sigma) ensemble. For a broad class of Gaussian ensembles satisfying mutual incoherence conditions, we compute explicit values of thresholds 0l(Sigma) les thetasu(Sigma)0, if n > 2 (thetasu+ delta) klog (p- k), then the Lasso succeeds in recovering the sparsity pattern with probability converging to one for large problems, whereas for nl- delta)klog (p - k), then the probability of successful recovery converges to zero. For the special case of the uniform Gaussian ensemble (Sigma = Iptimesp), we show that thetasl= thetasu= 1, so that the precise threshold n = 2 klog(p- k) is exactly determined.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Regression shrinkage and selection via the lasso
Tibshirani, R. (1996) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.2517-6161.1996.tb02080.x · Cited by 51,482
Donoho, D. L. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2006.871582 · Cited by 23,994
Donoho, D. L. (2004) · Cited by 16,703
Candes, E. J., Romberg, J., & Tao, T. (2006) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.862083 · Cited by 15,639
Bertsekas, D. P. (1997) · Journal of the Operational Research Society · doi:10.1038/sj.jors.2600425 · Cited by 11,726
Efron, B., Hastie, T., Johnstone, I., & Tibshirani, R. (2004) · The Annals of Statistics · doi:10.1214/009053604000000067 · Cited by 9,357
Variable Selection via Nonconcave Penalized Likelihood and its Oracle Properties
Fan, J., & Li, R. (2001) · Journal of the American Statistical Association · doi:10.1198/016214501753382273 · Cited by 8,900
Decoding by Linear Programming
Candes, E. J., & Tao, T. (2005) · IEEE Transactions on Information Theory · doi:10.1109/tit.2005.858979 · Cited by 7,121
Atomic Decomposition by Basis Pursuit
Chen, S. S., Donoho, D. L., & Saunders, M. A. (1998) · SIAM Journal on Scientific Computing · doi:10.1137/s1064827596304010 · Cited by 6,845
Greed is Good: Algorithmic Results for Sparse Approximation
Tropp, J. A. (2004) · IEEE Transactions on Information Theory · doi:10.1109/tit.2004.834793 · Cited by 3,635
Cited by
Meinshausen, N., & Bühlmann, P. (2010) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.1467-9868.2010.00740.x · Cited by 2,215
An Interior-Point Method for Large-Scale -Regularized Least Squares
Kim, S.-J., Koh, K., Lustig, M., Boyd, S., & Gorinevsky, D. (2007) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2007.910971 · Cited by 2,083
Gentzkow, M., Kelly, B., & Taddy, M. (2019) · Journal of Economic Literature · doi:10.1257/jel.20181020 · Cited by 1,236
Nonlocal Transform-Domain Filter for Volumetric Data Denoising and Reconstruction
Maggioni, M., Katkovnik, V., Egiazarian, K., & Foi, A. (2013) · IEEE Transactions on Image Processing · doi:10.1109/tip.2012.2210725 · Cited by 1,002
Confidence Intervals for Low Dimensional Parameters in High Dimensional Linear Models
Zhang, C.-H., & Zhang, S. S. (2014) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/rssb.12026 · Cited by 993
High-dimensional Ising model selection using ℓ1-regularized logistic regression
Ravikumar, P., Wainwright, M. J., & Lafferty, J. D. (2010) · The Annals of Statistics · doi:10.1214/09-aos691 · Cited by 892
Self-citationSparse Models and Methods for Optimal Instruments With an Application to Eminent Domain
(2012) · Econometrica · doi:10.3982/ecta9626 · Cited by 889
High-Dimensional Statistics: A Non-Asymptotic Viewpoint
Wainwright, M. J. (2019) · Cambridge University Press eBooks · doi:10.1017/9781108627771 · Cited by 882
Self-citationOptimization for Machine Learning
(2011) · The MIT Press eBooks · doi:10.7551/mitpress/8996.001.0001 · Cited by 875
On asymptotically optimal confidence regions and tests for high-dimensional models
van de Geer, S., Bühlmann, P., Ritov, Y., & Dezeure, R. (2014) · The Annals of Statistics · doi:10.1214/14-aos1221 · Cited by 822
High-dimensional covariance estimation by minimizing ℓ1-penalized log-determinant divergence
Ravikumar, P., Wainwright, M. J., Raskutti, G., & Yu, B. (2011) · Electronic Journal of Statistics · doi:10.1214/11-ejs631 · Cited by 744
Self-citationTaming the Factor Zoo: A Test of New Factors
FENG, G., GIGLIO, S., & XIU, D. (2020) · The Journal of Finance · doi:10.1111/jofi.12883 · Cited by 707
On the conditions used to prove oracle results for the Lasso
van de Geer, S. A., & Bühlmann, P. (2009) · Electronic Journal of Statistics · doi:10.1214/09-ejs506 · Cited by 684
Least Squares After Model Selection in High-Dimensional Sparse Models
Belloni, A., & Chernozhukov, V. (2009) · SSRN Electronic Journal · doi:10.2139/ssrn.1582594 · Cited by 683
Consistency of the group Lasso and multiple kernel learning
Bach, F. (2007) · arXiv (Cornell University) · doi:10.48550/arxiv.0707.3390 · Cited by 669
Best subset selection via a modern optimization lens
Bertsimas, D., King, A., & Mazumder, R. (2016) · The Annals of Statistics · doi:10.1214/15-aos1388 · Cited by 655
Strong Rules for Discarding Predictors in Lasso-Type Problems
Tibshirani, R., Bien, J., Friedman, J., Hastie, T., Simon, N., Taylor, J., & Tibshirani, R. J. (2012) · Journal of the Royal Statistical Society Series B: Statistical Methodology · doi:10.1111/j.1467-9868.2011.01004.x · Cited by 653
Confidence Intervals and Hypothesis Testing for High-Dimensional Regression
Javanmard, A., & Andrea Montanari, A. (2013) · arXiv (Cornell University) · doi:10.48550/arxiv.1306.3171 · Cited by 635
Square-root lasso: pivotal recovery of sparse signals via conic programming
Belloni, A., Chernozhukov, V., & Wang, L. (2011) · Biometrika · doi:10.1093/biomet/asr043 · Cited by 635
Optimization with Sparsity-Inducing Penalties
Bach, F. (2011) · now publishers, Inc. eBooks · doi:10.1561/9781601985118 · Cited by 608
A significance test for the lasso
Lockhart, R., Taylor, J., Tibshirani, R. J., & Tibshirani, R. (2014) · The Annals of Statistics · doi:10.1214/13-aos1175 · Cited by 541
Estimation of (near) low-rank matrices with noise and high-dimensional scaling
Negahban, S., & Wainwright, M. J. (2011) · The Annals of Statistics · doi:10.1214/10-aos850 · Cited by 537
Self-citationThe lasso problem and uniqueness
Tibshirani, R. J. (2013) · Electronic Journal of Statistics · doi:10.1214/13-ejs815 · Cited by 507
Minimax Rates of Estimation for High-Dimensional Linear Regression Over $\ell_q$-Balls
Raskutti, G., Wainwright, M. J., & Yu, B. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2165799 · Cited by 455
Self-citationAMP-Inspired Deep Networks for Sparse Linear Inverse Problems
Borgerding, M., Schniter, P., & Rangan, S. (2017) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2017.2708040 · Cited by 455
Robust PCA via Outlier Pursuit
Xu, H., Caramanis, C., & Sanghavi, S. (2012) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2173156 · Cited by 445
Structured Variable Selection with Sparsity-Inducing Norms
Jenatton, R., Audibert, J.-Y., & Bach, F. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0904.3523 · Cited by 431
Nonconcave Penalized Likelihood With NP-Dimensionality
Fan, J., & Lv, J. (2011) · IEEE Transactions on Information Theory · doi:10.1109/tit.2011.2158486 · Cited by 427
Information-Theoretic Limits on Sparsity Recovery in the High-Dimensional and Noisy Setting
Wainwright, M. J. (2009) · IEEE Transactions on Information Theory · doi:10.1109/tit.2009.2032816 · Cited by 420
Self-citationBolasso: model consistent Lasso estimation through the bootstrap
Bach, F. R. (2008) · Proceedings of the 25th international conference on Machine learning - ICML '08 · doi:10.1145/1390156.1390161 · Cited by 387
An overview of the estimation of large covariance and precision matrices
Fan, J., Liao, Y., & Liu, H. (2016) · The Econometrics Journal · doi:10.1111/ectj.12061 · Cited by 385
Latent variable graphical model selection via convex optimization
Chandrasekaran, V., Parrilo, P. A., & Willsky, A. S. (2012) · The Annals of Statistics · doi:10.1214/11-aos949 · Cited by 377
Support union recovery in high-dimensional multivariate regression
Obozinski, G., Wainwright, M. J., & Jordan, M. I. (2011) · The Annals of Statistics · doi:10.1214/09-aos776 · Cited by 350
Self-citationOracle inequalities and optimal inference under group sparsity
Lounici, K., Pontil, M., van de Geer, S., & Tsybakov, A. B. (2011) · The Annals of Statistics · doi:10.1214/11-aos896 · Cited by 341
Sparse Modeling for Image and Vision Processing
Mairal, J. (2014) · now publishers, Inc. eBooks · doi:10.1561/9781680830095 · Cited by 322
Structured Sparsity through Convex Optimization
Bach, F., Jenatton, R., Mairal, J., & Obozinski, G. (2012) · Statistical Science · doi:10.1214/12-sts394 · Cited by 315
Strong oracle optimality of folded concave penalized estimation
Fan, J., Xue, L., & Zou, H. (2014) · The Annals of Statistics · doi:10.1214/13-aos1198 · Cited by 313
Sun, Q., Zhou, W.-X., & Fan, J. (2020) · Journal of the American Statistical Association · doi:10.1080/01621459.2018.1543124 · Cited by 312
Recovering Sparse Signals With a Certain Family of Nonconvex Penalties and DC Programming
Gasso, G., Rakotomamonjy, A., & Canu, S. (2009) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2009.2026004 · Cited by 304
A General Theory of Concave Regularization for High-Dimensional Sparse Estimation Problems
Zhang, C.-H., & Zhang, T. (2012) · Statistical Science · doi:10.1214/12-sts399 · Cited by 296
A Unified Framework for High-Dimensional Analysis of $M$-Estimators with Decomposable Regularizers
Negahban, S. N., Ravikumar, P., Wainwright, M. J., & Yu, B. (2012) · Statistical Science · doi:10.1214/12-sts400 · Cited by 287
Self-citationBayesian Inference and Optimal Design for the Sparse Linear Model
Seeger, M. (2008) · Infoscience (Ecole Polytechnique Fédérale de Lausanne) · doi:10.5555/1390681.1390707 · Cited by 277
Proximal Methods for Hierarchical Sparse Coding
Jenatton, R., Mairal, J., Obozinski, G., & Bach, F. (2010) · arXiv (Cornell University) · doi:10.48550/arxiv.1009.2139 · Cited by 272
Ganguli, S., & Sompolinsky, H. (2012) · Annual Review of Neuroscience · doi:10.1146/annurev-neuro-062111-150410 · Cited by 256
On the Use of the Lasso for Instrumental Variables Estimation with Some Invalid Instruments
Windmeijer, F., Farbmacher, H., Davies, N., & Davey Smith, G. (2019) · Journal of the American Statistical Association · doi:10.1080/01621459.2018.1498346 · Cited by 144
Yu, B. (2013) · Bernoulli · doi:10.3150/13-bejsp14 · Cited by 113
Empirical Asset Pricing via Machine Learning
Gu, S., Kelly, B. T., & Xiu, D. (2018) · The Review of Financial Studies · doi:10.2139/ssrn.3159577 · Cited by 52
Metadata
- Authors
- Wainwright, M. J.
- Venue
- IEEE Transactions on Information Theory
- Published
- 2009-05
- Volume
- 55
- Issue
- 5
- Pages
- 2183-2202
- ISSN
- 0018-9448 (ISSN-L)
- OpenAlex
- W2127300249
- Cited by
- 1,198
- References
- 35
- FWCI
- 63.13
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.