Necessary and Sufficient Conditions on Sparsity Pattern Recovery

Abstract

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.

Submitted to IEEE Transactions on Information Theory

References in corpus (7)

• Compressed Sensing and Redundant Dictionaries
• Necessary and Sufficient Conditions on Sparsity Pattern Recovery
• Sharp thresholds for high-dimensional and noisy recovery of sparsity
• On-Off Random Access Channels: A Compressed Sensing Framework
• On sensing capacity of sensor networks for the class of linear observation, fixed SNR models
• Shannon Theoretic Limits on Noisy Compressive Sampling
• Information-theoretic limits on sparse signal recovery: Dense versus sparse measurement matrices

Cited by in corpus (38)

• Necessary and Sufficient Conditions on Sparsity Pattern Recovery
• Boolean Compressed Sensing and Noisy Group Testing
• Asymptotic Analysis of MAP Estimation via the Replica Method and Applications to Compressed Sensing
• LDPC Codes for Compressed Sensing
• Information theoretic bounds for Compressed Sensing
• Sparse Estimation using Bayesian Hierarchical Prior Modeling for Real and Complex Linear Models
• On-Off Random Access Channels: A Compressed Sensing Framework
• Why Gabor Frames? Two Fundamental Measures of Coherence and Their Role in Model Selection
• Peak Reduction and Clipping Mitigation by Compressive Sensing
• Group Testing with Probabilistic Tests: Theory, Design and Application
• Joint Design of Measurement Matrix and Sparse Support Recovery Method via Deep Auto-encoder
• Sparse Signal Processing with Linear and Nonlinear Observations: A Unified Shannon-Theoretic Approach
• Orthogonal Matching Pursuit: A Brownian Motion Analysis
• Improving Noise Robustness in Subspace-based Joint Sparse Recovery
• Sub-linear Time Support Recovery for Compressed Sensing using Sparse-Graph Codes
• Model Selection: Two Fundamental Measures of Coherence and Their Algorithmic Significance
• Representation Based Regression for Object Distance Estimation
• Which bridge estimator is optimal for variable selection?
• An Estimation Theoretic Approach for Sparsity Pattern Recovery in the Noisy Setting
• Compressive Sensing Using Low Density Frames
• Ranked Sparse Signal Support Detection
• Lossy Compression via Sparse Linear Regression: Performance under Minimum-distance Encoding
• Compressive Sensing for Feedback Reduction in MIMO Broadcast Channels
• Approximate Sparsity Pattern Recovery: Information-Theoretic Lower Bounds
• Bayesian Hypothesis Test using Nonparametric Belief Propagation for Noisy Sparse Recovery
• Convolutional Sparse Support Estimator Network (CSEN) From energy efficient support estimation to learning-aided Compressive Sensing
• Sparse Recovery with Linear and Nonlinear Observations: Dependent and Noisy Data
• Level set estimation from projection measurements: Performance guarantees and fast computation
• Sharp Sufficient Conditions on Exact Sparsity Pattern Recovery
• Jointly Sparse Signal Recovery and Support Recovery via Deep Learning with Applications in MIMO-based Grant-Free Random Access
• An Information Theoretic Study for Noisy Compressed Sensing With Joint Sparsity Model-2
• Sparsity Pattern Recovery in Bernoulli-Gaussian Signal Model
• Exact Dynamic Support Tracking with Multiple Measurement Vectors using Compressive MUSIC
• Operational Support Estimator Networks
• Phase Transition Analysis of Sparse Support Detection from Noisy Measurements
• "Compressed" Compressed Sensing
• KL-BSS: Rethinking optimality for neighbourhood selection in structural equation models
• Compressive Sensing Based Opportunistic Protocol for Throughput Improvement in Wireless Networks