Improved bounds for sparse recovery from adaptive measurements

J. Haupt, R.M. Castro, R. Nowak

    Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

    9 Citations (Scopus)
    134 Downloads (Pure)


    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
    Title of host publicationProceedings of the 2010 IEEE International Symposium on Information Theory (ISIT'10, Austin TX, USA, June 13-18, 2010)
    PublisherInstitute of Electrical and Electronics Engineers
    ISBN (Print)978-1-4244-7890-3
    Publication statusPublished - 2010


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

    Cite this