Sharp thresholds for high-dimensional and noisy recovery of sparsity

By Martin J. Wainwright. 2006

239 citations recorded by the source corpus.

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 + \epsilon) \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 - \epsilon) \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.

Subfields: Applied Mathematics, Computational Mechanics, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Applied Mathematics

In Computational Mechanics

In Computer Vision and Pattern Recognition

Citations in the corpus

Sparse additive models (2007, methodology): “Codewords/patch 8.14, RSS 0.1894 Codewords/patch 8.08, RSS 0.0913 is sparsistent : b References include Wainwright (2006), Meinshausen and P.”
Stability selection (2008, background): “E-mail: meinshausen@stats.ox.ac.uk some discrete optimization problems, e.g. by l1-penalty approaches (Donoho and Elad, 2003; Meinshausen and Bühlmann, 2006; Zhao and Yu, 2006; Wainwright, 2009; Yuan and Lin, 2007) or greedy algorithms (Freund and Schapire, 1996; Tropp, 2004; Zhang, 2009).”
Nearly unbiased variable selection under minimax concave penalty (2010, background): “Wainwright (2006) proved ‖Σ−1Ao‖∞”
Adaptive Huber Regression (2017, methodology): “This near-perfect alignment in Figure 4 is also observed by Wainwright (2009) for Lasso with sub-Gaussian errors.”
Properties and refinements of the fused lasso (2008, background): “2. Equation (12) actually implies not only thatJ0 can be consistently estimated, but also that the true signs of the jumps can be recovered with overwhelming probability, a feature known in the lasso literature as sign consistency (see, e.g. Wainwright, 2006; Zhao and Yu, 2006).”
LASSO Isotone for High-Dimensional Additive Isotonic Regression (2010, methodology): “As we can see, as in a variety of LASSO-type algorithms (Wainwright 2009), there is a sharp threshold between success and failure in recovery of sparsity patterns as a function of n.”
On the Consistency of Feature Selection using Greedy Least Squares Regression (2009, unknown): “Givenx ∈ Rn andF̄ ⊂ {1, . . . ,d}, let β̂X(F̄ ,x) = min β∈Rd 1 n ‖Xβ−x‖22 subject to supp(β) ⊂ F̄ .”
Some sharp performance bounds for least squares regression with L1 regularization (2009, background): “, [5, 18, 19, 20]), or more generally, identify features with target coefficients larger than a certain threshold (see Section 7).”
A Selective Overview of Variable Selection in High Dimensional Feature Space (2009, background): “See, e.g., Wainwright (2006).”
On the asymptotic properties of the group lasso estimator for linear models (2008, background): “…been shown to have optimal theoretical properties: model selection, or sign consistency, or sparsistency (see, e.g., Meinshausen and Bühlmann, 2006; Wainwright, 2006, 2007; Zhao and Yu, 2006), consistency and oracle properties (see, e.g. Meinshausen and Yu, 2006; Bickel et al., 2007; Bunea et…”
The Lasso Problem and Uniqueness (2012, background): “For example, see Osborne et al. (2000 b ), Fuchs (2005), Wainwright (2009), Candes & Plan (2009).”
An Interior-Point Method for Large-Scale $\ell_1$-Regularized Least Squares (2007, background): “Recently , theoretical properties of -regularized linear regression have been studied by several researchers; see, e.g., [20], [29], [33], [56], [62], [61].”
Compressed and Privacy-Sensitive Sparse Regression (2009, methodology): “Assuming that satisfies the -incoherence condition, we show that with high probability also satisfies the -incoherence condition, and hence the incoherence conditions (106a) and (106b) used in [6].”