Information-Theoretic Limits on Sparse Signal Recovery: Dense versus Sparse Measurement Matrices

We study the information-theoretic limits of exactly recovering the support set of a sparse signal, using noisy projections defined by various classes of measurement matrices. Our analysis is high-dimensional in nature, in which the number of observations n, the ambient signal dimension p, and the signal sparsity k are all allowed to tend to infinity in a general manner. This paper makes two novel contributions. First, we provide sharper necessary conditions for exact support recovery using general (including non-Gaussian) dense measurement matrices. Combined with previously known sufficient conditions, this result yields sharp characterizations of when the optimal decoder can recover a signal for various scalings of the signal sparsity k and sample size n, including the important special case of linear sparsity (k = ¿(p)) using a linear scaling of observations (n = ¿(p)). Our second contribution is to prove necessary conditions on the number of observations n required for asymptotically reliable recovery using a class of ¿-sparsified measurement matrices, where the measurement sparsity parameter ¿(n, p, k) ¿ (0,1] corresponds to the fraction of nonzero entries per row. Our analysis allows general scaling of the quadruplet (n, p, k, ¿) , and reveals three different regimes, corresponding to whether measurement sparsity has no asymptotic effect, a minor effect, or a dramatic effect on the information-theoretic limits of the subset recovery problem.

• Publication year

  2008

• Venue

  IEEE Transactions on Information Theory

• Publication date

  2008-06-03

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1109/TIT.2010.2046199arXiv 0806.0604
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Compressed Sensing

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

  2009cited by this paper
• High-dimensional subset recovery in noise: Sparsified measurements without loss of statistical efficiency

  2008cited by this paper
• Information-theoretic limits on sparse support recovery: Dense versus sparse measurements

  2008cited by this paper
• Sampling bounds for sparse support recovery in the presence of noise

  2008cited by this paper
• Sparse Signal Sampling using Noisy Linear Projections

  2008cited by this paper
• Combining geometry and combinatorics: A unified approach to sparse signal recovery

  2008cited by this paper
• Fundamental Limits on Sensing Capacity for Sensor Networks and Compressed Sensing

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

  2008cited 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
• Efficient Compressive Sensing with Deterministic Guarantees Using Expander Graphs

  2007cited by this paper
• Information-Theoretic Limits on Sparsity Recovery in the High-Dimensional and Noisy Setting

  2007influential reference
• Distributed Sparse Random Projections for Refinable Approximation

  2007cited by this paper
• Algorithmic linear dimension reduction in the l_1 norm for sparse vectors

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

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

  2006cited by this paper
• Sharp thresholds for high-dimensional and noisy recovery of sparsity

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

  2006cited by this paper
• Sudocodes ߝ Fast Measurement and Reconstruction of Sparse Signals

  2006cited by this paper
• Stable recovery of sparse overcomplete representations in the presence of noise

  2006cited by this paper
• Stable signal recovery from incomplete and inaccurate measurements

  2005cited by this paper
• Decoding by linear programming

  2005cited by this paper
• Elements of Information Theory

  2005cited by this paper
• Towards an Algorithmic Theory of Compressed Sensing

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

  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
• Assouad, Fano, and 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
• Subset Selection in Regression

  1992cited by this paper
• Subset Selection in Regression

  1991cited by this paper
• Statistical estimation : asymptotic theory

  1981cited by this paper
• Approximation Theorems of Mathematical Statistics

  1980cited by this paper
• Approximation Theorems of Mathematical Statistics

  1980cited by this paper
• A Lower Bound on the Risks of Non-Parametric Estimates of Densities in the Uniform Metric

  1979cited by this paper

• UWB Physical Layer Key Sharing Using the Frequency Domain CIR Magnitude

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

  2025cites this paper
• UWB-based Physical Layer Key Sharing for BAN Devices

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

  2025influential citation
• The Price of Sparsity: Sufficient Conditions for Sparse Recovery using Sparse and Sparsified Measurements

  2025influential citation
• Your Causal Self-Attentive Recommender Hosts a Lonely Neighborhood

  2024cites this paper
• On the Compressibility of State Snapshots for String Systems

  2024cites this paper
• Statistical-Computational Tradeoffs in Mixed Sparse Linear Regression

  2023influential citation
• Evolving scientific discovery by unifying data and background knowledge with AI Hilbert

  2023cites 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
• A Novel Model-Based Security Scheme for LoRa Key Generation

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

  2020cites this paper
• Diagonal Remainder Matrix Based Analog to Information Conversion

  2020cites this paper
• KEHKey

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

  2020cites this paper
• On the Error Exponent of Approximate Sufficient Statistics for M-ary Hypothesis Testing

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

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

  2020cites this paper
• Basic tail and concentration bounds

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

  2019cites this paper
• Feature selection for data integration with mixed multiview data

  2019cites this paper
• Contributions to variable selection, clustering and statistical estimation inhigh dimension

  2019cites this paper
• Sparse Regression: Scalable Algorithms and Empirical Performance

  2019cites this paper
• H2B: Heartbeat-based Secret Key Generation Using Piezo Vibration Sensors

  2019cites this paper
• Compressive sensing-based sequential data gathering in WSNs

  2019cites this paper
• Information Theoretic Bounds for Sparse Reconstruction in Random Noise

  2019cites this paper
• LoRa-Key: Secure Key Generation System for LoRa-Based Network

  2019cites this paper
• Iterative algorithm for discrete structure recovery

  2019cites this paper
• Minimax Lower Bounds

  2019cites this paper
• Sparse linear models in high dimensions

  2019cites this paper
• High-Dimensional Statistics

  2019cites this paper
• Metric entropy and its uses

  2019cites this paper
• Optimal Variable Selection and Adaptive Noisy Compressed Sensing

  2018influential citation
• A Coded Compressed Sensing Scheme for Uncoordinated Multiple Access

  2018cites this paper
• Sparse Signal Processing and Statistical Inference for Internet of Things

  2018cites this paper
• Enhancing the sufficient condition of sparsity pattern recovery

  2018cites this paper
• Compressive Acquisition and Processing of Sparse Analog Signals

  2018cites this paper
• Sparsity estimation from compressive projections via sparse random matrices

  2018influential citation
• A Coupled Compressive Sensing Scheme for Uncoordinated Multiple Access

  2018cites this paper
• Limits on Sparse Data Acquisition: RIC Analysis of Finite Gaussian Matrices

  2018cites this paper
• A sparsity feedback-based data gathering algorithm for Wireless Sensor Networks

  2018cites this paper
• Data gathering in wireless sensor networks via regular low density parity check matrix

  2018cites this paper
• Data-Driven Sparse Sensor Placement for Reconstruction: Demonstrating the Benefits of Exploiting Known Patterns

  2017cites this paper
• Limits on Support Recovery With Probabilistic Models: An Information-Theoretic Framework

  2017influential citation
• Enhancing the fundamental limits of sparsity pattern recovery

  2017cites this paper
• Which bridge estimator is optimal for variable selection?

  2017cites this paper
• Diffusion wavelet basis algorithm for sparse representation of sensory data in WSNs

  2017cites this paper
• Support Recovery with Sparsely Sampled Free Random Matrices for Wideband Cognitive Radio Receiver

  2017cites this paper
• High Dimensional Regression with Binary Coefficients. Estimating Squared Error and a Phase Transtition

  2017cites this paper
• Sparse High-Dimensional Linear Regression. Algorithmic Barriers and a Local Search Algorithm

  2017cites this paper
• Sparse classification: a scalable discrete optimization perspective

  2017influential citation
• Data-Driven Sparse Sensor Placement

  2017cites this paper
• Sparse Classification and Phase Transitions: A Discrete Optimization Perspective

  2017cites this paper
• Compressive Sensing Based Signal Processing in Wireless Sensor Networks: A Survey

  2017cites this paper
• Sparse Sensor Placement Optimization for Classification

  2016cites this paper
• Greedy Subspace Pursuit for Joint Sparse Recovery

  2016cites this paper
• COMPU-EYE: a high resolution computational compound eye.

  2016cites this paper
• A Deep Neural Network Architecture Using Dimensionality Reduction with Sparse Matrices

  2016cites this paper
• Limits on Sparse Support Recovery via Linear Sketching with Random Expander Matrices

  2016cites this paper
• Signal sparsity estimation from compressive noisy projections via γ-sparsified random matrices

  2016influential citation
• Adaptivity provably helps: Information-theoretic limits on l0 cost of non-adaptive sensing

  2016cites this paper
• A note on support recovery of sparse signals using linear programming

  2016cites this paper
• Capacity of Gaussian Many-Access Channels

  2016cites this paper
• Sparsification of Matrices and Compressed Sensing

  2015cites this paper
• Information-theoretic analysis of support recovery from sparsely corrupted measurements

  2015cites this paper
• Information estimations and acquisition costs for quantized compressive sensing

  2015cites this paper
• On the fly estimation of the sparsity degree in Compressed Sensing using sparse sensing matrices

  2015cites this paper
• Limits on support recovery with probabilistic models: An information-theoretic framework

  2015cites this paper
• Sub-linear Time Compressed Sensing for Support Recovery using Sparse-Graph Codes

  2015influential citation
• Bayesian Hypothesis Test Using Nonparametric Belief Propagation for Noisy Sparse Recovery

  2015influential citation
• Limits on Support Recovery with Probabilistic Models: An Information-Spectrum Approach

  2015cites this paper
• Wireless Compressive Sensing Over Fading Channels With Distributed Sparse Random Projections

  2015cites this paper
• Restricted Isometry Property on Banded Block Toeplitz Matrices with Application to Multi-Channel Convolutive Source Separation

  2015cites this paper
• Compressive Video Acquisition with Multiple Sensors and No Reference Frames

  2015cites this paper
• High-Resolution Light Field Capture With Coded Aperture

  2015cites this paper
• Sub-linear time compressed sensing using sparse-graph codes

  2015cites this paper
• Compressive Classification: Where Wireless Communications Meets Machine Learning

  2015cites this paper
• A Novel Probabilistic Approach for Vehicle Position Prediction in Free,Partial and Full GPS Outages

  2015cites this paper
• Compressive Classification of a Mixture of Gaussians: Analysis, Designs and Geometrical Interpretation

  2014cites this paper
• On the sensing matrix performance for support recovery of noisy sparse signals

  2014cites this paper
• On Compressive Sensing in Coding Problems: A Rigorous Approach

  2014cites this paper
• Performance analysis of compressed sensing with uniform scalar quantisation

  2014cites this paper
• Compressive Sampling and Rapid Reconstruction of Broadband Frequency Hopping Signals with Interference

  2014cites this paper
• Compressed Sensing of Memoryless Sources - A Deterministic Hadamard Construction

  2014cites this paper
• Information theoretic bounds for compressed sensing in SAR imaging

  2014cites this paper
• Sub-Linear Time Support Recovery for Compressed Sensing Using Sparse-Graph Codes

  2014cites this paper
• Concentration of Measure

  2014cites this paper
• Compressive Sparsity Order Estimation for Wideband Cognitive Radio Receiver

  2014cites this paper
• Performance analysis of partial support recovery and signal reconstruction of compressed sensing

  2014cites this paper
• Compressive sparsity order estimation for wideband Cognitive Radio receiver

  2014cites this paper
• Joint Optimization of Sensor Selection and Routing for Distributed Estimation in Wireless Sensor Networks

  2014cites this paper
• A Measurement Rate-MSE Tradeoff for Compressive Sensing Through Partial Support Recovery

  2014cites this paper
• Performance Limits of Segmented Compressive Sampling: Correlated Measurements Versus Bits

  2014cites this paper
• Discrimination on the grassmann manifold: Fundamental limits of subspace classifiers

  2014cites this paper
• Signal reconstruction in linear mixing systems with different error metrics

  2013cites this paper
• Interference Cancellation in Wideband Receivers using Compressed Sensing

  2013cites this paper
• Neural Networks and Sparse Information Acquisition

  2013cites this paper
• Sparse signal processing with linear and non-linear observations: A unified shannon theoretic approach

  2013influential citation
• Optimal sensing matrix design with hardware friendliness

  2013influential citation