Improved bounds for sparse recovery from adaptive measurements

J. Haupt; R.M. Castro; R. Nowak

doi:10.1109/ISIT.2010.5513489

Improved bounds for sparse recovery from adaptive measurements

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

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

9 Citations (Scopus)

107 Downloads (Pure)

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
Title of host publication	Proceedings of the 2010 IEEE International Symposium on Information Theory (ISIT'10, Austin TX, USA, June 13-18, 2010)
Publisher	Institute of Electrical and Electronics Engineers
Pages	1563-1567
ISBN (Print)	978-1-4244-7890-3
DOIs	https://doi.org/10.1109/ISIT.2010.5513489
Publication status	Published - 2010

Access to Document

10.1109/ISIT.2010.5513489

Metis254471Final published version, 151 KB

Cite this

@inproceedings{9c35a0ef09df432fbea4f7102a532cba,

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 = "J. Haupt and R.M. Castro and R. Nowak",

year = "2010",

doi = "10.1109/ISIT.2010.5513489",

language = "English",

isbn = "978-1-4244-7890-3",

pages = "1563--1567",

booktitle = "Proceedings of the 2010 IEEE International Symposium on Information Theory (ISIT'10, Austin TX, USA, June 13-18, 2010)",

publisher = "Institute of Electrical and Electronics Engineers",

address = "United States",

}

Improved bounds for sparse recovery from adaptive measurements. / Haupt, J.; Castro, R.M.; Nowak, R.
Proceedings of the 2010 IEEE International Symposium on Information Theory (ISIT'10, Austin TX, USA, June 13-18, 2010). Institute of Electrical and Electronics Engineers, 2010. p. 1563-1567.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Improved bounds for sparse recovery from adaptive measurements

AU - Haupt, J.

AU - Castro, R.M.

AU - Nowak, R.

PY - 2010

Y1 - 2010

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.

U2 - 10.1109/ISIT.2010.5513489

DO - 10.1109/ISIT.2010.5513489

M3 - Conference contribution

SN - 978-1-4244-7890-3

SP - 1563

EP - 1567

BT - Proceedings of the 2010 IEEE International Symposium on Information Theory (ISIT'10, Austin TX, USA, June 13-18, 2010)

PB - Institute of Electrical and Electronics Engineers

ER -

Improved bounds for sparse recovery from adaptive measurements

Abstract

Access to Document

Fingerprint

Cite this