Improved bounds for sparse recovery from adaptive measurements

Jarvis Haupt; Rui Castro; Robert Nowak

doi:10.1109/ISIT.2010.5513489

Improved bounds for sparse recovery from adaptive measurements

Jarvis Haupt, Rui Castro, Robert Nowak

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	2010 IEEE International Symposium on Information Theory, ISIT 2010 - Proceedings
Pages	1563-1567
Number of pages	5
DOIs	https://doi.org/10.1109/ISIT.2010.5513489
State	Published - Aug 23 2010
Event	2010 IEEE International Symposium on Information Theory, ISIT 2010 - Austin, TX, United States Duration: Jun 13 2010 → Jun 18 2010

Publication series

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

Other

Other	2010 IEEE International Symposium on Information Theory, ISIT 2010
Country	United States
City	Austin, TX
Period	6/13/10 → 6/18/10

Access

10.1109/ISIT.2010.5513489

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

Improved bounds for sparse recovery from adaptive measurements. / Haupt, Jarvis; Castro, Rui; Nowak, Robert.

2010 IEEE International Symposium on Information Theory, ISIT 2010 - Proceedings. 2010. p. 1563-1567 5513489 (IEEE International Symposium on Information Theory - Proceedings).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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., 5513489, IEEE International Symposium on Information Theory - Proceedings, pp. 1563-1567, 2010 IEEE International Symposium on Information Theory, ISIT 2010, Austin, TX, United States, 6/13/10. https://doi.org/10.1109/ISIT.2010.5513489

@inproceedings{ad2c45a0691c41f09a06db1dfa4f5aab,

title = "Improved bounds for sparse recovery from adaptive measurements",

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.",

author = "Jarvis Haupt and Rui Castro and Robert Nowak",

year = "2010",

month = aug,

day = "23",

doi = "10.1109/ISIT.2010.5513489",

language = "English (US)",

isbn = "9781424469604",

series = "IEEE International Symposium on Information Theory - Proceedings",

pages = "1563--1567",

booktitle = "2010 IEEE International Symposium on Information Theory, ISIT 2010 - Proceedings",

note = "2010 IEEE International Symposium on Information Theory, ISIT 2010 ; Conference date: 13-06-2010 Through 18-06-2010",

}

TY - GEN

T1 - Improved bounds for sparse recovery from adaptive measurements

AU - Haupt, Jarvis

AU - Castro, Rui

AU - Nowak, Robert

PY - 2010/8/23

Y1 - 2010/8/23

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=77955671530&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77955671530&partnerID=8YFLogxK

U2 - 10.1109/ISIT.2010.5513489

DO - 10.1109/ISIT.2010.5513489

M3 - Conference contribution

AN - SCOPUS:77955671530

SN - 9781424469604

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 1563

EP - 1567

BT - 2010 IEEE International Symposium on Information Theory, ISIT 2010 - Proceedings

T2 - 2010 IEEE International Symposium on Information Theory, ISIT 2010

Y2 - 13 June 2010 through 18 June 2010

ER -