Distilled sensing: Adaptive sampling for sparse detection and estimation

Jarvis Haupt, Rui M. Castro, Robert Nowak

Research output: Contribution to journalArticlepeer-review

102 Scopus citations

Abstract

Adaptive sampling results in significant improvements in the recovery of sparse signals in white Gaussian noise. A sequential adaptive sampling-and-refinement procedure called Distilled Sensing (DS) is proposed and analyzed. DS is a form of multistage experimental design and testing. Because of the adaptive nature of the data collection, DS can detect and localize far weaker signals than possible from non-adaptive measurements. In particular, reliable detection and localization (support estimation) using non-adaptive samples is possible only if the signal amplitudes grow logarithmically with the problem dimension. Here it is shown that using adaptive sampling, reliable detection is possible provided the amplitude exceeds a constant, and localization is possible when the amplitude exceeds any arbitrarily slowly growing function of the dimension.

Original languageEnglish (US)
Article number6006586
Pages (from-to)6222-6235
Number of pages14
JournalIEEE Transactions on Information Theory
Volume57
Issue number9
DOIs
StatePublished - Sep 2011

Bibliographical note

Funding Information:
Manuscript received May 27, 2010; revised April 10, 2011; accepted April 12, 2011. Date of current version August 31, 2011. This work was supported in part by NSF Grant CCF-0353079 and AFOSR Grant FA9550-09-1-0140, and is dedicated to the memory of Dr. Dennis Healy, who inspired and supported this direction of research through the DARPA Analog-to-Information Program. Dennis’ guidance, vision, and inspiration will be missed. A preliminary version of this paper appeared at the IEEE International Symposium on Information Theory, Austin, TX, June 2010.

Keywords

  • Adaptive sampling
  • experimental design
  • multiple hypothesis testing
  • sequential sensing
  • sparse recovery

Fingerprint

Dive into the research topics of 'Distilled sensing: Adaptive sampling for sparse detection and estimation'. Together they form a unique fingerprint.

Cite this