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

Cited by in corpus (18)

• 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
• Properties and refinements of the fused lasso
• Some sharp performance bounds for least squares regression with $L_1$ regularization
• Various thresholds for ${\ell }_1$-optimization in compressed sensing
• 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
• A Selective Overview of Variable Selection in High Dimensional Feature Space (Invited Review Article)
• Discussion: One-step sparse estimates in nonconcave penalized likelihood models
• Asymptotic distribution and sparsistency for l1-penalized parametric M-estimators with applications to linear SVM and logistic regression
• Informative Sensing
• Sparse Additive Models
• Autoregressive Process Modeling via the Lasso Procedure