Necessary and Sufficient Conditions on Sparsity Pattern Recovery

The problem of detecting the sparsity pattern of a k-sparse vector in R^n from m random noisy measurements is of interest in many areas such as system identification, denoising, pattern recognition, and compressed sensing. This paper addresses the scaling of the number of measurements m, with signal dimension n and sparsity-level nonzeros k, for asymptotically-reliable detection. We show a necessary condition for perfect recovery at any given SNR for all algorithms, regardless of complexity, is m = Omega(k log(n-k)) measurements. Conversely, it is shown that this scaling of Omega(k log(n-k)) measurements is sufficient for a remarkably simple ``maximum correlation'' estimator. Hence this scaling is optimal and does not require more sophisticated techniques such as lasso or matching pursuit. The constants for both the necessary and sufficient conditions are precisely defined in terms of the minimum-to-average ratio of the nonzero components and the SNR. The necessary condition improves upon previous results for maximum likelihood estimation. For lasso, it also provides a necessary condition at any SNR and for low SNR improves upon previous work. The sufficient condition provides the first asymptotically-reliable detection guarantee at finite SNR.

• Publication year

  2008

• Venue

  arXiv.org

• Publication date

  2008-04-11

• Fields of study

  Mathematics, Computer Science, Engineering

• Identifiers
  DOI 10.1109/TIT.2009.2032726arXiv 0804.1839
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Compressive Sampling and Lossy Compression

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

  2008cited by this paper
• Noisy compressive sampling limits in linear and sublinear regimes

  2008influential reference
• Information-Theoretic Limits on Sparsity Recovery in the High-Dimensional and Noisy Setting

  2007influential reference
• Shannon-Theoretic Limits on Noisy Compressive Sampling

  2007influential reference
• Rate-Distortion Bounds for Sparse Approximation

  2007cited by this paper
• On sensing capacity of sensor networks for the class of linear observation, fixed SNR models

  2007cited 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

  2006influential reference
• Just relax: convex programming methods for identifying sparse signals in noise

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

  2006cited by this paper
• Signal Reconstruction From Noisy Random Projections

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

  2006cited by this paper
• Sparse approximation, denoising, and large random frames

  2005cited by this paper
• Greed is good: algorithmic results for sparse approximation

  2004cited by this paper
• Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information

  2004cited by this paper
• Near-Optimal Signal Recovery From Random Projections: Universal Encoding Strategies?

  2004cited by this paper
• Atomic Decomposition by Basis Pursuit

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

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

  1995cited by this paper
• Matching pursuits with time-frequency dictionaries

  1993cited by this paper
• Subset Selection in Regression

  1992cited by this paper
• Monographs on statistics and applied probability

  1990cited by this paper
• Statistical distributions

  1983cited by this paper

• A GPU-accelerated Nonlinear Branch-and-Bound Framework for Sparse Linear Models

  2026cites 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
• Optimality and computational barriers in variable selection under dependence

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

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

  2025cites this paper
• Generalized Approximate Message-Passing for Compressed Sensing with Sublinear Sparsity

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

  2024cites this paper
• Compressive Beam Alignment for Indoor Millimeter-Wave Systems

  2024cites this paper
• Oracle-Net for Nonlinear Compressed Sensing in Electrical Impedance Tomography Reconstruction Problems

  2024cites this paper
• Channel Estimation for Underwater Acoustic Communications in Impulsive Noise Environments: A Sparse, Robust, and Efficient Alternating Direction Method of Multipliers-Based Approach

  2024cites this paper
• Detecting Location Spoofing Attacks using Multiple Angle of Signal Arrivals in MM-Wave Vehicular Networks

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

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

  2023cites this paper
• Operational Support Estimator Networks

  2023cites this paper
• Joint Spatial and Reflecting Modulation for Active IRS Assisted MIMO Communications

  2023cites this paper
• Recovery Guarantees for Distributed-OMP

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

  2022influential citation
• Variable selection, monotone likelihood ratio and group sparsity

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

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

  2021cites this paper
• Millimeter-Wave Antenna Array Diagnosis with Partial Channel State Information

  2020cites this paper
• Sparse Index OFDM Modulation for IoT Communications

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

  2020cites this paper
• Near-Optimal Comparison Based Clustering

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

  2020cites this paper
• Sparse regression at scale: branch-and-bound rooted in first-order optimization

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

  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
• Joint Sparsity Pattern Recovery With 1-b Compressive Sensing in Distributed Sensor Networks

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

  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
• Iterative algorithm for discrete structure recovery

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

  2019cites this paper
• Sparse linear models in high dimensions

  2019cites this paper
• Basic tail and concentration bounds

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

  2019cites this paper
• Density evolution of Orthogonal Matching Pursuit

  2019cites this paper
• High-Dimensional Statistics

  2019cites this paper
• Research on the high pixels ladar imaging system based on compressive sensing

  2019cites this paper
• Relay-Aided Channel Estimation for mmWave Systems with Imperfect Antenna Arrays

  2019cites this paper
• Metric entropy and its uses

  2019cites this paper
• Minimax Lower Bounds

  2019cites this paper
• Harmless Interpolation of Noisy Data in Regression

  2019cites this paper
• Channel Estimation in Millimeter Wave Systems with Inter Cell Interference

  2019cites this paper
• Streak tube imaging system based on compressive sensing

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

  2018influential citation
• A greedy approach for correlation-aware sparse support recovery

  2018cites this paper
• Sparse PCA from Sparse Linear Regression

  2018cites this paper
• An Opportunistic Thresholding Detector for IoT Random Access in Massive MIMO

  2018cites this paper
• Non-Asymptotic Guarantees for Correlation-Aware Support Detection

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

  2018cites this paper
• IoT Random Access in Massive MIMO: Exploiting Diversity in Sensing Matrices

  2018cites this paper
• On Fundamental Limits of Joint Sparse Support Recovery Using Certain Correlation Priors

  2018cites this paper
• Fast Fourier-Based Generation of the Compression Matrix for Deterministic Compressed Sensing

  2018cites this paper
• Enhancing the fundamental limits of sparsity pattern recovery

  2017cites this paper
• An Information-Theoretic Study for Joint Sparsity Pattern Recovery With Different Sensing Matrices

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

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

  2017cites this paper
• On the Equivalence of Sparse Statistical Problems

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

  2017cites this paper
• Towards fundamental limits of bursty multi-user communications in wireless networks

  2017cites this paper
• Performance assessment of a compressive sensing single-pixel imaging system

  2017cites this paper
• Compressive Sensing for Blockage Detection in Vehicular Millimeter Wave Antenna Arrays

  2016cites this paper
• Compressive Sensing for Millimeter Wave Antenna Array Diagnosis

  2016cites this paper
• On the Feedback Reduction of Multiuser Relay Networks Using Compressive Sensing

  2016cites this paper
• SHO-FA: Robust Compressive Sensing With Order-Optimal Complexity, Measurements, and Bits

  2016cites this paper
• An Information Theoretic Study for Noisy Compressed Sensing With Joint Sparsity Model-2

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

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

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

  2016cites this paper
• On finding a subset of non-defective items from a large population using group tests: Recovery algorithms and bounds

  2015cites this paper
• Finding A Subset Of Non-defective Items From A Large Population : Fundamental Limits And Efficient Algorithms

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

  2015influential citation
• Opportunistic Relay Selection With Limited Feedback

  2015cites this paper
• Joint sparsity pattern recovery with 1-bit compressive sensing in sensor networks

  2015cites this paper
• Information-Theoretic Characterization and Undersampling Ratio Determination for Compressive Radar Imaging in a Simulated Environment

  2015cites this paper
• Compressive Sensing for Feedback Reduction in Wireless Multiuser Networks

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

  2015influential citation
• On the detection probability of sparse signals with sensor networks based on distributed subspace pursuit

  2015cites this paper
• Performance Limits of Sparse Support Recovery Algorithms

  2015influential citation
• Information-theoretic analysis of support recovery from sparsely corrupted measurements

  2015cites this paper
• On the Feedback Reduction of Relay Aided Multiuser Networks using Compressive Sensing

  2015cites this paper
• Limits on Support Recovery with Probabilistic Models: An Information-Spectrum Approach

  2015cites this paper
• Bayesian Hypothesis Test Using Nonparametric Belief Propagation for Noisy Sparse Recovery

  2015cites this paper
• ISIT 2015 Tutorial: Information Theory and Machine Learning

  2015cites this paper
• Informational Analysis for Compressive Sampling in Radar Imaging

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

  2014cites this paper
• Downlink scheduling using non-orthogonal uplink beams

  2014influential citation
• Sub-Linear Time Support Recovery for Compressed Sensing Using Sparse-Graph Codes

  2014cites this paper
• Concentration of Measure

  2014cites this paper
• An adaptive PAPR reduction scheme for OFDM using SLM with clipping at the transmitter, and sparse reconstruction at the receiver

  2014cites this paper
• Information-Theoretic Characterization of Sparse Recovery

  2014cites this paper
• Compressive parameter estimation via K-median clustering

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

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

  2014cites this paper
• Compressive Parameter Estimation with Emd

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

  2014cites this paper
• Sparse Recovery with Linear and Nonlinear Observations: Dependent and Noisy Data

  2014cites this paper