Adaptive sensing performance lower bounds for sparse signal detection and support estimation
arXiv:1206.0648 · doi:10.3150/13-BEJ555
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 (IEEE Trans. Inform. Theory 57 (2011) 6222-6235) and show necessary conditions on the minimum signal magnitude for both detection and estimation: if is a sparse vector with non-zero components then it can be reliably detected in noise provided the magnitude of the non-zero components exceeds . Furthermore, the signal support can be exactly identified provided the minimum magnitude exceeds . Notably there is no dependence on , 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.
arXiv commentPublished in at http://dx.doi.org/10.3150/13-BEJ555 the Bernoulli (http://isi.cbs.nl/bernoulli/) by the International Statistical Institute/Bernoulli Society (http://isi.cbs.nl/BS/bshome.htm)
References in corpus (8)
- Higher criticism for detecting sparse heterogeneous mixtures
- Estimating the proportion of false null hypotheses among a large number of independently tested hypotheses
- Detection of a sparse submatrix of a high-dimensional noisy matrix
- Searching for a trail of evidence in a maze
- On combinatorial testing problems
- Hierarchical testing designs for pattern recognition
- Estimation and confidence sets for sparse normal mixtures
- Rates of convergence in active learning