Sharp thresholds for high-dimensional and noisy recovery of sparsity

Abstract

The problem of consistently estimating the sparsity pattern of a vector $\betastar \in \real^\mdim$ based on observations contaminated by noise arises in various contexts, including subset selection in regression, structure estimation in graphical models, sparse approximation, and signal denoising. We analyze the behavior of ${\ell }_1$-constrained quadratic programming (QP), also referred to as the Lasso, for recovering the sparsity pattern. Our main result is to establish a sharp relation between the problem dimension $\mdim$, the number $\spindex$ of non-zero elements in $\betastar$, and the number of observations $\numobs$ that are required for reliable recovery. For a broad class of Gaussian ensembles satisfying mutual incoherence conditions, we establish existence and compute explicit values of thresholds $\ThreshLow$ and $\ThreshUp$ with the following properties: for any $\epsilon >0$, if $\numobs > 2 (\ThreshUp + ε) \log (\mdim - \spindex) + \spindex + 1$, then the Lasso succeeds in recovering the sparsity pattern with probability converging to one for large problems, whereas for $\numobs < 2 (\ThreshLow - ε) \log (\mdim - \spindex) + \spindex + 1$, then the probability of successful recovery converges to zero. For the special case of the uniform Gaussian ensemble, we show that $\ThreshLow = \ThreshUp = 1$, so that the threshold is sharp and exactly determined.

Appeared as Technical Report 708, Department of Statistics, UC Berkeley

References in corpus (11)

• Least Angle Regression
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Discussion of "Least angle regression" by Efron et al
• Rejoinder to "Least angle regression" by Efron et al
• An error bound in the Sudakov-Fernique inequality

Cited by in corpus (49)

• Nearly unbiased variable selection under minimax concave penalty
• Least squares after model selection in high-dimensional sparse models
• The sparsity and bias of the Lasso selection in high-dimensional linear regression
• Lasso-type recovery of sparse representations for high-dimensional data
• High-dimensional variable selection
• Near-ideal model selection by ${\ell }_1$ minimization
• A unified approach to model selection and sparse recovery using regularized least squares
• Necessary and Sufficient Conditions on Sparsity Pattern Recovery
• Asymptotic Analysis of MAP Estimation via the Replica Method and Applications to Compressed Sensing
• Properties and refinements of the fused lasso
• Group Lasso with Overlaps: the Latent Group Lasso approach
• Some sharp performance bounds for least squares regression with $L_1$ regularization
• A framework to characterize performance of LASSO algorithms
• Various thresholds for ${\ell }_1$-optimization in compressed sensing
• Rates of convergence of the Adaptive LASSO estimators to the Oracle distribution and higher order refinements by the bootstrap
• On-Off Random Access Channels: A Compressed Sensing Framework
• Performance of Linear Field Reconstruction Techniques with Noise and Uncertain Sensor Locations
• Block-length dependent thresholds in block-sparse compressed sensing
• Discussion: A tale of three cousins: Lasso, L2Boosting and Dantzig
• The Multivariate Hawkes Process in High Dimensions: Beyond Mutual Excitation
• Bootstrap inference for network construction with an application to a breast cancer microarray study
• A Selective Overview of Variable Selection in High Dimensional Feature Space (Invited Review Article)
• Orthogonal Matching Pursuit: A Brownian Motion Analysis
• Discussion: One-step sparse estimates in nonconcave penalized likelihood models
• The log-linear group-lasso estimator and its asymptotic properties
• Asymptotic distribution and sparsistency for l1-penalized parametric M-estimators with applications to linear SVM and logistic regression
• Upper-bounding ${\ell }_1$-optimization weak thresholds
• Informative Sensing
• An Estimation Theoretic Approach for Sparsity Pattern Recovery in the Noisy Setting
• The Lasso under Heteroscedasticity
• A performance analysis framework for SOCP algorithms in noisy compressed sensing
• Sparse Additive Models
• High-dimensional robust regression and outliers detection with SLOPE
• Approximate Sparsity Pattern Recovery: Information-Theoretic Lower Bounds
• Optimized Compressed Sensing via Incoherent Frames Designed by Convex Optimization
• Selection and Estimation for Mixed Graphical Models
• Regularization after retention in ultrahigh dimensional linear regression models
• Modelling Interactions in High-dimensional Data with Backtracking
• Sparse Group Selection Through Co-Adaptive Penalties
• Likelihood Adaptively Modified Penalties
• Sparse and Robust Linear Regression: An Optimization Algorithm and Its Statistical Properties
• LASSO ISOtone for High Dimensional Additive Isotonic Regression
• Linear under-determined systems with sparse solutions: Redirecting a challenge?
• "Compressed" Compressed Sensing
• Autoregressive Process Modeling via the Lasso Procedure
• Network Reconstruction From High Dimensional Ordinary Differential Equations
• Sparse linear regression -- CLuP achieves the ideal \emph{exact} ML
• LASSO risk and phase transition under dependence
• A problem dependent analysis of SOCP algorithms in noisy compressed sensing