Necessary and Sufficient Conditions for Sparsity Pattern Recovery
- 17 November 2009
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 55 (12), 5758-5772
- https://doi.org/10.1109/tit.2009.2032726
Abstract
The paper considers the problem of detecting the sparsity pattern of a k -sparse vector in \BBR n from m random noisy measurements. A new necessary condition on the number of measurements for asymptotically reliable detection with maximum-likelihood (ML) estimation and Gaussian measurement matrices is derived. This necessary condition for ML detection is compared against a sufficient condition for simple maximum correlation (MC) or thresholding algorithms. The analysis shows that the gap between thresholding and ML can be described by a simple expression in terms of the total signal-to-noise ratio (SNR), with the gap growing with increasing SNR. Thresholding is also compared against the more sophisticated Lasso and orthogonal matching pursuit (OMP) methods. At high SNRs, it is shown that the gap between Lasso and OMP over thresholding is described by the range of powers of the nonzero component values of the unknown signals. Specifically, the key benefit of Lasso and OMP over thresholding is the ability of Lasso and OMP to detect signals with relatively small components.Keywords
This publication has 28 references indexed in Scilit:
- Sharp Thresholds for High-Dimensional and Noisy Sparsity Recovery Using $\ell _{1}$-Constrained Quadratic Programming (Lasso)IEEE Transactions on Information Theory, 2009
- Counting faces of randomly projected polytopes when the projection radically lowers dimensionJournal of the American Mathematical Society, 2008
- The Dantzig selector: Statistical estimation when p is much larger than nThe Annals of Statistics, 2007
- Rate-Distortion Bounds for Sparse ApproximationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2007
- Denoising by Sparse Approximation: Error Bounds Based on Rate-Distortion TheoryEURASIP Journal on Advances in Signal Processing, 2006
- Greed is Good: Algorithmic Results for Sparse ApproximationIEEE Transactions on Information Theory, 2004
- Atomic Decomposition by Basis PursuitSIAM Journal on Scientific Computing, 1998
- Sparse Approximate Solutions to Linear SystemsSIAM Journal on Computing, 1995
- Matching pursuits with time-frequency dictionariesIEEE Transactions on Signal Processing, 1993
- Orthogonal least squares methods and their application to non-linear system identificationInternational Journal of Control, 1989