Adaptive sensing performance lower bounds for sparse estimation and testing

Research output: Book/ReportReportAcademic

Abstract

This paper gives a precise characterization of the fundamental limits of adaptive sensing for diverse estimation and testing problems concerning sparse signals. We consider in particular the setting introduced in Haupt, Castro and Nowak (2011) and show necessary conditions on the minimum signal magnitude for both detection and estimation: if $x\in\R^n$ is a sparse vector with $s$ non-zero components then it can be reliably detected in noise provided the magnitude of the non-zero components exceeds $\sqrt{2/s}$. Furthermore, the signal support can be exactly identified provided the minimum magnitude exceeds $\sqrt{2\log s}$. Notably there is no dependence on $n$, the extrinsic signal dimension. These results show that the adaptive sensing methodologies proposed previously in the literature are essentially optimal, and cannot be substantially improved. In addition these results provide further insights on the limits of adaptive compressive sensing.
Original languageEnglish
Publishers.n.
Number of pages26
Publication statusPublished - 2012

Publication series

NamearXiv
Volume1206.0648

Fingerprint Dive into the research topics of 'Adaptive sensing performance lower bounds for sparse estimation and testing'. Together they form a unique fingerprint.

  • Cite this