Approximate Sparsity Pattern Recovery: Information-Theoretic Lower Bounds

Recovery of the sparsity pattern (or support) of an unknown sparse vector from a small number of noisy linear mea- surements 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 er- rors, is established by comparison with existing achievable bounds. Near optimality is shown for a wide variety of practically motivated signal models.


Published in:
IEEE Transactions on Information Theory, 59, 6, 3451-3465
Year:
2013
Publisher:
Piscataway, Institute of Electrical and Electronics Engineers
ISSN:
0018-9448
Keywords:
Laboratories:




 Record created 2013-05-21, last modified 2018-03-17


Rate this document:

Rate this document:
1
2
3
 
(Not yet reviewed)