Source-linked AI summary
Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting
Martin J. Wainwright
TL;DR
The paper studies when the sparsity pattern of an unknown vector can be exactly recovered from noisy, high-dimensional linear observations. It derives sufficient conditions for the optimal decoder and necessary conditions for any decoder under Gaussian measurements, and compares these limits with the Lasso threshold.
Problem
The central question is which relationships among n, p, and s are necessary or sufficient for asymptotically perfect sparsity-pattern recovery from noisy observations.
Method
The analysis considers noisy linear observations with i.i.d. standard Gaussian measurement vectors and examines optimal-decoder recovery under asymptotic scaling.
Results
The paper derives sufficient and necessary recovery conditions, with a threshold of order n = Θ(s log(p −s)) in a sublinear-sparsity regime, essentially matching the Lasso threshold there.
Takeaways & Limitations
The information-theoretic analysis identifies fundamental recovery limits and can reveal whether computationally tractable methods achieve those limits or leave a gap.
Takeaways & Limitations
The bounds are essentially matching only in certain scaling regimes, and the necessary-condition analysis has slack because it uses a restricted ensemble.
Abstract
from arXiv · showhide
The problem of recovering the sparsity pattern of a fixed but unknown vector $β^* \in \real^p based on a set of $n$ noisy observations arises in a variety of settings, including subset selection in regression, graphical model selection, signal denoising, compressive sensing, and constructive approximation. Of interest are conditions on the model dimension $p$, the sparsity index $s$ (number of non-zero entries in $β^*$), and the number of observations $n$ that are necessary and/or sufficient to ensure asymptotically perfect recovery of the sparsity pattern. This paper focuses on the information-theoretic limits of sparsity recovery: in particular, for a noisy linear observation model based on measurement vectors drawn from the standard Gaussian ensemble, we derive both a set of sufficient conditions for asymptotically perfect recovery using the optimal decoder, as well as a set of necessary conditions that any decoder, regardless of its computational complexity, must satisfy for perfect recovery. This analysis of optimal decoding limits complements our previous work (ARXIV: math.ST/0605740) on sharp thresholds for sparsity recovery using the Lasso ($\ell_1$-constrained quadratic programming) with Gaussian measurement ensembles.
1 Introduction
The paper studies information-theoretic limits for recovering sparse supports from noisy, high-dimensional linear observations. It develops optimal-decoder conditions for asymptotically reliable recovery and compares them with computationally tractable methods across sparsity regimes.
- Sparsity recovery estimates the nonzero index set of a sparse vector from noisy observations, with applications spanning regression, graphical models, denoising, and compressive sensing.
- The analysis targets necessary and sufficient scaling conditions in n, p, and s for exact recovery under standard Gaussian measurement vectors and additive Gaussian noise.
- The paper uses the 0−1 support-recovery loss and analyzes optimal decoders, complementing prior work on Lasso thresholds and ℓ2-error criteria.
- The results cover general scaling of (n, p, s), beyond the linear and sublinear sparsity regimes emphasized by much previous work.
- Regime of sublinear sparsity: For sublinear sparsity with M2(β*) = Θ(1/s), the threshold is n = Θ(s log(p−s)), and the Lasso essentially achieves the information-theoretic bounds.
- Regime of linear sparsity: For linear sparsity s = αp, n = Θ(p) observations can suffice when M2(β*)s → +∞, while the Lasso requires substantially more observations, motivating efficient alternatives.
2 Analysis
The analysis develops an optimal-decoding error framework for Gaussian linear observations, then proves sufficient and necessary recovery conditions using tail bounds and Fano’s method.
- Optimal decoding: The proof represents each candidate support through reconstruction errors and characterizes when the optimal decoder prefers a wrong subset over the true support.The decoder selects the size-s subset minimizing reconstruction error; failure occurs when at least one competing subset is preferred.
- Optimal decoding: For candidates differing from the true support in k entries, the analysis reduces error control to tail bounds for a non-central χ2 variate with n −s degrees of freedom.The non-centrality parameter is determined by the norm of the omitted true coefficients.
- Proof of sufficient conditions: The sufficient-condition proof bounds the total error probability by counting competing subsets at each overlap level and applying a union bound.A weakened bound depending only on k enables analysis of the resulting summation over candidate supports.
- Proof of sufficient conditions: The sufficient analysis requires (n −s)M2(β∗) →+∞ and yields a condition ensuring asymptotically reliable recovery.The requirement ensures that the relevant error term decays asymptotically.
- Proof of necessary conditions: The necessary-condition proof applies a Fano-method lower bound based on Kullback–Leibler divergences in a multiway support-testing problem.If the divergence-based quantity remains bounded away from one, the averaged probability of error remains bounded away from zero.
3 Conclusion
The paper establishes lower and upper observation bounds for asymptotically reliable sparsity recovery in a Gaussian linear model, while identifying regimes where the analysis remains incomplete and computationally tractable methods are still sought.
- 3 Conclusion: The analysis establishes lower and upper bounds on observations n as functions of model dimension p and sparsity index s for reliable recovery.These bounds apply to the linear observation model with measurement vectors drawn from the standard Gaussian ensemble.
- 3 Conclusion: For sublinear sparsity with minimum M2(β*) = Θ(1/s), the upper and lower bounds are essentially matching.
- 3 Conclusion: For linear sparsity s = αp, reliable recovery is possible with n = βp when the minimum M2(β*) decays sufficiently slowly.
- 3 Conclusion: The necessary-condition analysis may contain slack because it relies on a very restricted ensemble.
- 3 Conclusion: A computationally tractable method approaching optimal performance remains unknown in the linear-sparsity regime because the Lasso cannot reliably recover there.
A Proof of Lemma 1
The lemma proof rewrites the subset objective using an orthogonal projection, then uses least-squares projection identities and the projection’s null action on the design range.
- A Proof of Lemma 1: For any subset U with X_U full rank, the function f has an equivalent orthogonal-projection form.
- A Proof of Lemma 1: The linear least-squares estimator on U satisfies X_U β̂_U = Π_U Y.
- A Proof of Lemma 1: Substituting the least-squares identity into the quadratic norm and expanding yields the claimed equivalent expression.
- A Proof of Lemma 1: Equation (13) follows because Π_U^⊥v = 0 for every vector v in the range of X_U.
B Proof of Lemma 4
The proof controls a rescaled sum of nonnegative random variables with Markov’s inequality, bounding its expectation before selecting a threshold.
- B Proof of Lemma 4: Z_{U,V} is a rescaled sum of N^2 dependent, non-identically distributed variables, but nonnegativity permits Markov’s inequality.
- B Proof of Lemma 4: The expectation satisfies E[Z_{U,V}] = γ(U,V)n, with γ(U,V) ≤ 2M2(β*)s.
- B Proof of Lemma 4: Choosing t = 4M2(β*)sn in the resulting bound establishes the claim.
C Bounds on binomial coefficients
The section introduces crude binomial-coefficient bounds for repeated use in the analysis.
- C Bounds on binomial coefficients: Crude bounds on binomial coefficients are used frequently throughout the analysis.
D Tail bounds for chi-square variables
This section introduces large-deviation tail bounds for centralized and non-central chi-square variables. The centralized bounds are attributed to Laurent and Massart, while the non-central analogues are attributed to Birgé and obtained via the Chernoff bound.
- Centralized chi-square bounds: Centralized chi-square tail bounds are stated for a variable X with d degrees of freedom and x ≥ 0.The bounds are taken from Laurent and Massart.
- Non-central chi-square bounds: Non-central chi-square tail bounds extend the setup to non-centrality parameter ν ≥ 0 and x > 0.These analogous bounds are attributed to Birgé.
- Non-central chi-square bounds: The non-central bounds can be established using the Chernoff bound.