Back to Search
Start Over
Approximate Sparsity Pattern Recovery: Information-Theoretic Lower Bounds.
- Source :
-
IEEE Transactions on Information Theory . Jun2013, Vol. 59 Issue 6, p3451-3465. 15p. - Publication Year :
- 2013
-
Abstract
- Recovery of the sparsity pattern (or support) of an unknown sparse vector from a small number of noisy linear measurements is an important problem in compressed sensing. In this paper, the high-dimensional setting is considered. It is shown that if the measurement rate and per-sample signal-to-noise ratio (SNR) are finite constants independent of the length of the vector, then the optimal sparsity pattern estimate will have a constant fraction of errors. Lower bounds on the measurement rate needed to attain a desired fraction of errors are given in terms of the SNR and various key parameters of the unknown vector. The tightness of the bounds in a scaling sense, as a function of the SNR and the fraction of errors, is established by comparison with existing achievable bounds. Near optimality is shown for a wide variety of practically motivated signal models. [ABSTRACT FROM PUBLISHER]
- Subjects :
- *ERRORS
*PAPER arts
*NOISE
*REMOTE sensing
*INFORMATION theory
Subjects
Details
- Language :
- English
- ISSN :
- 00189448
- Volume :
- 59
- Issue :
- 6
- Database :
- Academic Search Index
- Journal :
- IEEE Transactions on Information Theory
- Publication Type :
- Academic Journal
- Accession number :
- 87618002
- Full Text :
- https://doi.org/10.1109/TIT.2013.2253852