Information-Theoretic Limits on Sparsity Recovery in the High-Dimensional and Noisy Setting

By Martin J. Wainwright. IEEE Transactions on Information Theory, 2007

519 citations recorded by the source corpus.

The problem of sparsity pattern or support set recovery refers to estimating the set of nonzero coefficients of an unknown vector beta* isin Ropfp based on a set of n noisy observations. It arises in a variety of settings, including subset selection in regression, graphical model selection, signal denoising, compressive sensing, and constructive approximation. The sample complexity of a given method for subset recovery refers to the scaling of the required sample size n as a function of the signal dimension p, sparsity index k (number of non-zeroes in beta*), as well as the minimum value betamin of beta* over its support and other parameters of measurement matrix. This paper studies the information-theoretic limits of sparsity recovery: in particular, for a noisy linear observation model based on random measurement matrices drawn from general Gaussian measurement matrices, we derive both a set of sufficient conditions for exact support recovery using an exhaustive search decoder, as well as a set of necessary conditions that any decoder, regardless of its computational complexity, must satisfy for exact support recovery. This analysis of fundamental limits complements our previous work on sharp thresholds for support set recovery over the same set of random measurement ensembles using the polynomial-time Lasso method (lscr1-constrained quadratic programming).

Subfields: Computational Mechanics, Computer Networks and Communications, Signal Processing

View Paper: https://www.semanticscholar.org/paper/5d6906070d7e69ed794058720b52e46d2899e96b

How researchers see this paper

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

In Computational Mechanics

In Computer Networks and Communications

In Signal Processing

Citations in the corpus

Detection boundary in sparse regression (2010, methodology): “This can be compared with the asymptotically optimal recovery of sparsity pattern (RSP) by the Lasso in the same Gaussian regression model as ours [29, 30].”
Unified lower bounds for interactive high-dimensional estimation under information constraints (2020, background): “Finally, note that for l≥ d log(2d/s) (and similarly for ̺ ≥ d log(2d/s) ), the lower bound follows from the minimax rate in the unconstrained setting, which can be seen to be Ω (√ s2/p log(2d/s)/n ) [29, 31].”
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…”
A unified framework for high-dimensional analysis of $M$-estimators with decomposable regularizers (2009, methodology): “The informationtheoretic limits of sparse linear regression are also well understood, and 1-based methods are known to be optimal for q -ball sparsity [56] and near-optimal for model selection [74].”
The adaptive and the thresholded Lasso for potentially misspecified models (and a lower bound for the Lasso) (2011, background): “The papers [30, 31] analyze the smallest sample size needed to recover a sparse signal under certain incoherence conditions.”
Learning Sparse Additive Models with Interactions in High Dimensions (2016, background): “Such problems arise for instance, in modeling complex physical processes [1, 2, 3].”
High-dimensional regression with unknown variance (2011, background): “For other statistical problems, including the prediction problem with random design, the inverse problem (estimation of β0), the variable selection problem (estimation of the support of β0), the dimension reduction problem [47, 77, 78], the minimax risks increase exponentially fast in an ultra-high-”
Harmless interpolation of noisy data in regression (2019, background): “In the absence of underlying sparse structure, we unavoidably have non-zero noiseless error in the asymptotic high dimensional regime [27], [28].”
Variable Importance Using Decision Trees (2017, methodology): “Our results for the linear case, derived as a special case of the general theory, allow us to compare the performance of DSTUMP to the information theoretic limits for sample complexity established in [11], and to the performance of existing methods more tailored to this setting, such as the Lasso [”
Finding and Leveraging Structure in Learning Problems (2012, background): “Wainwright [197, 198] studied information theoretic limits and localization properties of the LASSO procedure.”
Robust High Dimensional Sparse Regression and Matching Pursuit (2013, background): “However, we show in the next section that a broad class of convex optimization-based approaches, with (2) as a special case, fail when the covariate X is also corrupted.”
High-dimensional analysis of semidefinite relaxations for sparse principal components (2008, methodology): “Our proof is based on the standard approach of applying Fano’s inequality (e.g., [7, 16, 37, 38]).”
Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$ -Constrained Quadratic Programming (Lasso) (2009, methodology): “Interestingly, information-theoretic analysis of this sparsity recovery problem [ 34 ], [36] shows that the optimal decoder—namely, an exponential-time algorithm that can search exhaustively over all subsets—has a fundamentally different scaling than the Lasso in some regimes.”