Sampling Bounds for Sparse Support Recovery in the Presence of Noise

It is well known that the support of a sparse signal can be recovered from a small number of random projections. However, in the presence of noise all known sufficient conditions require that the per-sample signal-to-noise ratio (SNR) grows without bound with the dimension of the signal. If the noise is due to quantization of the samples, this means that an unbounded rate per sample is needed. In this paper, it is shown that an unbounded SNR is also a necessary condition for perfect recovery, but any fraction (less than one) of the support can be recovered with bounded SNR. This means that a finite rate per sample is sufficient for partial support recovery. Necessary and sufficient conditions are given for both stochastic and non-stochastic signal models. This problem arises in settings such as compressive sensing, model selection, and signal denoising.

Published in:
2008 Ieee International Symposium On Information Theory Proceedings, Vols 1-6, 2187-2191
Presented at:
IEEE International Symposium on Information Theory, Toronto, CANADA, Jul 06-11, 2008
Ieee Service Center, 445 Hoes Lane, Po Box 1331, Piscataway, Nj 08855-1331 Usa

 Record created 2011-10-17, last modified 2018-03-17

Rate this document:

Rate this document:
(Not yet reviewed)