Information-theoretic limits on sparsity recovery in the high-dimensional and noisy setting

2007/02/11 by Martin J. Wainwright, Wainwright, Martin J. · 7 citations
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #FOS: Mathematics #Image and Signal Denoising Methods #Information Theory (cs.IT) #Photoacoustic and Ultrasonic Imaging #Sparse and Compressive Sensing Techniques #Statistics Theory (math.ST) #cs.IT #math.IT #math.ST #stat.TH

paper · pdf · doi:10.48550/arxiv.math/0702301

Appeared as Technical Report 725, Department of Statistics, UC Berkeley January 2007

openalex publication_date 2007/02/11 · arxiv created 2007/02/20 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The problem of recovering the sparsity pattern of a fixed but unknown vector β^* ∈ \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 (ℓ₁-constrained quadratic programming) with Gaussian measurement ensembles.

Citations

• Atomic Decomposition by Basis Pursuit
• Sparse Approximate Solutions to Linear Systems
• For most large underdetermined systems of equations, the minimal 𝓁1‐norm near‐solution approximates the sparsest near‐solution
• Stable signal recovery from incomplete and inaccurate measurements

Cited by

• Generalized Orthogonal Approximate Message-Passing for Sublinear Sparsity
• The Scaling Properties of Implicit Deductive Reasoning in Transformers
• Optimality and computational barriers in variable selection under dependence
• Overcoming Output Dimension Collapse: When Sparsity Enables Zero-shot Brain-to-Image Reconstruction at Small Data Scales
• Compressive Sensing Using Low Density Frames
• Shannon Theoretic Limits on Noisy Compressive Sampling
• Discussion: Latent variable graphical model selection via convex optimization

Related

• Sharp thresholds for high-dimensional and noisy recovery of sparsity
• Information-theoretic limits on sparse signal recovery: Dense versus sparse measurement matrices
• Approximate Sparsity Pattern Recovery: Information-Theoretic Lower Bounds
• Sharp Sufficient Conditions on Exact Sparsity Pattern Recovery
• High-dimensional subset recovery in noise: Sparsified measurements without loss of statistical efficiency