Improved bounds for sparse recovery from adaptive measurements

Jarvis Haupt, Rui Castro, Robert Nowak

Research output: Chapter in Book/Report/Conference proceedingConference contribution

8 Scopus citations

Abstract

It is shown here that adaptivity in sampling results in dramatic improvements in the recovery of sparse signals in white Gaussian noise. An adaptive sampling-and-refinement procedure called distilled sensing is discussed and analyzed, resulting in fundamental new asymptotic scaling relationships in terms of the minimum feature strength required for reliable signal detection or localization (support recovery). In particular, reliable detection and localization using non-adaptive samples is possible only if the feature strength grows logarithmically in the problem dimension. Here it is shown that using adaptive sampling, reliable detection is possible provided the feature strength exceeds a constant, and localization is possible when the feature strength exceeds any (arbitrarily slowly) growing function of the problem dimension.

Original languageEnglish (US)
Title of host publication2010 IEEE International Symposium on Information Theory, ISIT 2010 - Proceedings
Pages1563-1567
Number of pages5
DOIs
StatePublished - Aug 23 2010
Event2010 IEEE International Symposium on Information Theory, ISIT 2010 - Austin, TX, United States
Duration: Jun 13 2010Jun 18 2010

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8103

Other

Other2010 IEEE International Symposium on Information Theory, ISIT 2010
CountryUnited States
CityAustin, TX
Period6/13/106/18/10

Fingerprint Dive into the research topics of 'Improved bounds for sparse recovery from adaptive measurements'. Together they form a unique fingerprint.

  • Cite this

    Haupt, J., Castro, R., & Nowak, R. (2010). Improved bounds for sparse recovery from adaptive measurements. In 2010 IEEE International Symposium on Information Theory, ISIT 2010 - Proceedings (pp. 1563-1567). [5513489] (IEEE International Symposium on Information Theory - Proceedings). https://doi.org/10.1109/ISIT.2010.5513489