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

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).

• Publication year

  2007

• Venue

  IEEE Transactions on Information Theory

• Publication date

  2007-02-11

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/TIT.2009.2032816arXiv math/0702301
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$ -Constrained Quadratic Programming (Lasso)

  2009influential reference
• Sampling bounds for sparse support recovery in the presence of noise

  2008cited by this paper
• Necessary and Sufficient Conditions on Sparsity Pattern Recovery

  2008cited by this paper
• LASSO-TYPE RECOVERY OF SPARSE REPRESENTATIONS FOR HIGH-DIMENSIONAL DATA

  2008cited by this paper
• SIMULTANEOUS ANALYSIS OF LASSO AND DANTZIG SELECTOR

  2008cited by this paper
• Information-Theoretic Limits on Sparse Signal Recovery: Dense versus Sparse Measurement Matrices

  2008cited by this paper
• Rate-Distortion Bounds for Sparse Approximation

  2007cited by this paper
• Multi-Stage Variable Selection: Screen and Clean

  2007cited by this paper
• Information theoretic bounds to sensing capacity of sensor networks under fixed SNR

  2007cited by this paper
• Shannon-Theoretic Limits on Noisy Compressive Sampling

  2007cited by this paper
• For most large underdetermined systems of equations, the minimal 𝓁1‐norm near‐solution approximates the sparsest near‐solution

  2006cited by this paper
• High-dimensional graphs and variable selection with the Lasso

  2006influential reference
• On Model Selection Consistency of Lasso

  2006cited by this paper
• Denoising by Sparse Approximation: Error Bounds Based on Rate-Distortion Theory

  2006cited by this paper
• Counting faces of randomly-projected polytopes when the projection radically lowers dimension

  2006cited by this paper
• Just relax: convex programming methods for identifying sparse signals in noise

  2006influential reference
• Thresholds for the Recovery of Sparse Solutions via L1 Minimization

  2006influential reference
• For most large underdetermined systems of linear equations the minimal 𝓁1‐norm solution is also the sparsest solution

  2006cited by this paper
• Decoding by linear programming

  2005influential reference
• Stable signal recovery from incomplete and inaccurate measurements

  2005cited by this paper
• The Dantzig selector: Statistical estimation when P is much larger than n

  2005cited by this paper
• Elements of Information Theory

  2005influential reference
• Optimal sparse representations in general overcomplete bases

  2004cited by this paper
• Recovery of exact sparse representations in the presence of noise

  2004cited by this paper
• On sparse representation in pairs of bases

  2003cited by this paper
• A generalized uncertainty principle and sparse representation in pairs of bases

  2002cited by this paper
• Chapter 8 - Local Operator Theory, Random Matrices and Banach Spaces

  2001cited by this paper
• An alternative point of view on Lepski's method

  2001cited by this paper
• ADAPTIVE ESTIMATION OF A QUADRATIC FUNCTIONAL BY MODEL SELECTION

  2001cited by this paper
• Information-theoretic determination of minimax rates of convergence

  1999cited by this paper
• Atomic Decomposition by Basis Pursuit

  1998cited by this paper
• Festschrift for Lucien Le Cam

  1997cited by this paper
• Regression Shrinkage and Selection via the Lasso

  1996cited by this paper
• Sparse Approximate Solutions to Linear Systems

  1995cited by this paper
• Constructive Approximation

  1993cited by this paper
• Subset Selection in Regression

  1992cited by this paper
• Subset Selection in Regression

  1991cited by this paper
• A Lower Bound on the Error in Nonparametric Regression Type Problems

  1988cited by this paper
• Matrix analysis

  1985cited by this paper
• Statistical estimation : asymptotic theory

  1981influential reference
• A Lower Bound on the Risks of Non-Parametric Estimates of Densities in the Uniform Metric

  1979cited by this paper

• Direct and Converse Theorems in Estimating Signals with Sublinear Sparsity

  2026cites this paper
• Separating Oblivious and Adaptive Models of Variable Selection

  2026cites this paper
• A GPU-accelerated Nonlinear Branch-and-Bound Framework for Sparse Linear Models

  2026cites this paper
• Support estimation and sign recovery in high‐dimensional heteroscedastic mean regression

  2025influential citation
• Generalized Approximate Message-Passing for Compressed Sensing with Sublinear Sparsity

  2025cites this paper
• Overcoming Output Dimension Collapse: When Sparsity Enables Zero-shot Brain-to-Image Reconstruction at Small Data Scales

  2025cites this paper
• A Graphical Global Optimization Framework for Parameter Estimation of Statistical Models with Nonconvex Regularization Functions

  2025cites this paper
• Exact recovery in the double sparse model: Sufficient and necessary signal conditions

  2025cites this paper
• Generalized Orthogonal Approximate Message-Passing for Sublinear Sparsity

  2025influential citation
• Bayesian compressive sensing using generative models

  2025cites this paper
• Optimality and computational barriers in variable selection under dependence

  2025influential citation
• Theoretical limits of descending ℓ0 sparse-regression ML algorithms

  2024cites this paper
• Bayesian Model Selection via Composite Likelihood for High‐dimensional Data Integration

  2024cites this paper
• Learning Dynamic Bayesian Networks from Data: Foundations, First Principles and Numerical Comparisons

  2024cites this paper
• Recovering Exact Support in Federated lasso without Optimization

  2024influential citation
• Inference of nonlinear causal effects with application to TWAS with GWAS summary data

  2024cites this paper
• Generalized Approximate Message-Passing for Compressed Sensing With Sublinear Sparsity

  2024influential citation
• Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression

  2023influential citation
• Tale of two c(omplex)ities

  2023influential citation
• Resolving Non-identifiability Mitigates Bias in Models of Neural Tuning and Functional Coupling

  2023cites this paper
• Average case analysis of Lasso under ultra-sparse conditions

  2023influential citation
• Recovery of partly sparse and dense signals

  2023cites this paper
• Smoothing the Edges: A General Framework for Smooth Optimization in Sparse Regularization using Hadamard Overparametrization

  2023cites this paper
• Learning Sparse Group Models Through Boolean Relaxation

  2023cites this paper
• On the Computational Complexity of Private High-dimensional Model Selection via the Exponential Mechanism

  2023cites this paper
• Optimal Sparse Recovery with Decision Stumps

  2023influential citation
• New Bounds for Hyperparameter Tuning of Regression Problems Across Instances

  2023cites this paper
• Structured Low-Rank Tensors for Generalized Linear Models

  2023cites this paper
• Misspecified Phase Retrieval with Generative Priors

  2022cites this paper
• Tight bounds for maximum $\ell_1$-margin classifiers

  2022cites this paper
• Sparse Mixed Linear Regression with Guarantees: Taming an Intractable Problem with Invex Relaxation

  2022cites this paper
• Non-Iterative Recovery from Nonlinear Observations using Generative Models

  2022cites this paper
• Fast rates for noisy interpolation require rethinking the effects of inductive bias

  2022cites this paper
• Universal 1-Bit Compressive Sensing for Bounded Dynamic Range Signals

  2022cites this paper
• Optimal estimation of Gaussian DAG models

  2022cites this paper
• Provable Guarantees for Sparsity Recovery with Deterministic Missing Data Patterns

  2022cites this paper
• Two-Stage Robust and Sparse Distributed Statistical Inference for Large-Scale Data

  2022cites this paper
• The Lifecycle of a Statistical Model: Model Failure Detection, Identification, and Refitting

  2022cites this paper
• High-dimensional variable selection with heterogeneous signals: A precise asymptotic perspective

  2022influential citation
• Sparse high-dimensional linear regression. Estimating squared error and a phase transition

  2022cites this paper
• The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics

  2022cites this paper
• Inference of nonlinear causal effects with GWAS summary data

  2022cites this paper
• On Sure Early Selection of the Best Subset

  2021cites this paper
• On the early solution path of best subset selection

  2021cites this paper
• Nonconvex matrix and tensor recovery with applications in machine learning

  2021cites this paper
• Robust 1-bit Compressive Sensing with Partial Gaussian Circulant Matrices and Generative Priors

  2021cites this paper
• On Support Recovery With Sparse CCA: Information Theoretic and Computational Limits

  2021influential citation
• Multiple Support Recovery Using Very Few Measurements Per Sample

  2021cites this paper
• Pooled testing with compressive sensing

  2021cites this paper
• Supplementary Material for “Nonparametric Variable Screening with Optimal Decision Stumps”

  2021cites this paper
• Phase Transitions for Support Recovery from Gaussian Linear Measurements

  2021cites this paper
• A New Perspective on Debiasing Linear Regressions

  2021cites this paper
• Numerical characterization of support recovery in sparse regression with correlated design

  2021influential citation
• A Minimax Lower Bound for Low-Rank Matrix-Variate Logistic Regression

  2021cites this paper
• Introduction to Information Theory and Data Science.

  2021cites this paper
• High-dimensional inference via hybrid orthogonalization

  2021cites this paper
• Representation Based Regression for Object Distance Estimation

  2021cites this paper
• Exploring Fundamental Limits of Spatiotemporal Sensing for Non-Linear Inverse problems

  2021cites this paper
• Variable Selection in GLM and Cox Models with Second-Generation P-Values

  2021cites this paper
• Best Subset, Forward Stepwise or Lasso? Analysis and Recommendations Based on Extensive Comparisons

  2020cites this paper
• Massive Random Access in Massive MIMO via Opportunistic Thresholding

  2020cites this paper
• The Complete Lasso Tradeoff Diagram

  2020cites this paper
• The Complete Lasso Diagram

  2020cites this paper
• A Comparative Study on Early Detection of COVID-19 from Chest X-Ray Images

  2020cites this paper
• Unified lower bounds for interactive high-dimensional estimation under information constraints

  2020cites this paper
• Jointly Sparse Signal Recovery and Support Recovery via Deep Learning With Applications in MIMO-Based Grant-Free Random Access

  2020cites this paper
• A Sharp Sufficient Condition for Sparsity Pattern Recovery

  2020influential citation
• High-dimensional model recovery from random sketched data by exploring intrinsic sparsity

  2020cites this paper
• Exact Support Recovery in Federated Regression with One-shot Communication

  2020influential citation
• Sparse regression at scale: branch-and-bound rooted in first-order optimization

  2020cites this paper
• Modeling, Analysis, and Optimization of Grant-Free NOMA in Massive MTC via Stochastic Geometry

  2020cites this paper
• High-dimensional asymptotics: new insights and methods

  2020cites this paper
• Statistics, computation, and adaptation in high dimensions

  2020cites this paper
• Approximation of signals and functions in high dimensions with low dimensional structure: finite-valued sparse signals and generalized ridge functions

  2020cites this paper
• Variable Selection With Second-Generation P-Values

  2020cites this paper
• Algorithmic advancements in discrete optimization Applications to machine learning and healthcare operations

  2020cites this paper
• Penalised robust estimators for sparse and high-dimensional linear models

  2020cites this paper
• Convolutional Sparse Support Estimator-Based COVID-19 Recognition From X-Ray Images

  2020cites this paper
• of the Bernoulli Society for Mathematical Statistics and Probability Volume Twenty Six Number Four November 2020

  2020cites this paper
• Advance Warning Methodologies for COVID-19 Using Chest X-Ray Images

  2020cites this paper
• A Coded Compressed Sensing Scheme for Unsourced Multiple Access

  2020cites this paper
• Nonparametric Variable Screening with Optimal Decision Stumps

  2020cites this paper
• Inference in high dimensional linear measurement error models

  2020cites this paper
• Convolutional Sparse Support Estimator Network (CSEN): From Energy-Efficient Support Estimation to Learning-Aided Compressive Sensing

  2020cites this paper
• Nonlinear Variable Selection via Deep Neural Networks

  2020cites this paper
• Sample Complexity Bounds for 1-bit Compressive Sensing and Binary Stable Embeddings with Generative Priors

  2020cites this paper
• Small-Data, Large-Scale Linear Optimization with Uncertain Objectives

  2020cites this paper
• Sample Complexity Lower Bounds for Compressive Sensing with Generative Models

  2020cites this paper
• A Regularization-Based Adaptive Test for High-Dimensional Generalized Linear Models

  2020cites this paper
• A Discussion on Practical Considerations with Sparse Regression Methodologies

  2020cites this paper
• Support estimation in high-dimensional heteroscedastic mean regression

  2020influential citation
• On the Error Exponent of Approximate Sufficient Statistics for M-ary Hypothesis Testing

  2020cites this paper
• On the Error Probability of Support Recovery for Orthogonal Matching Pursuit With a Random Measurement Matrix

  2020cites this paper
• Minimax Lower Bounds

  2019cites this paper
• The All-or-Nothing Phenomenon in Sparse Linear Regression

  2019cites this paper
• Harmless interpolation of noisy data in regression

  2019cites this paper
• Analysis on User Activity in Compressed Sensing based Random Access

  2019cites this paper
• Joint Design of Measurement Matrix and Sparse Support Recovery Method via Deep Auto-Encoder

  2019cites this paper
• Sample-Measurement Tradeoff in Support Recovery Under a Subgaussian Prior

  2019cites this paper
• Guaranteed Localization of More Sources Than Sensors With Finite Snapshots in Multiple Measurement Vector Models Using Difference Co-Arrays

  2019cites this paper