Adaptive sensing performance lower bounds for sparse signal detection and support estimation

DOI10.3150/13-BEJ555MaRDI QIDQ470072zbMATH OpenFDO

Authors Rui M. Castro

Publication date 11 November 2014

Published in Bernoulli (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1206.0648, https://projecteuclid.org/euclid.bj/1411134458

zbMATH Keywords

minimax lower boundsadaptive sensingsequential experimental designsparsity-based models

Mathematics Subject Classification ID

Sequential statistical design (62L05) Non-Markovian processes: estimation (62M09) Signal theory (characterization, reconstruction, filtering, etc.) (94A12) Non-Markovian processes: hypothesis testing (62M07) Detection theory in information and communication theory (94A13)

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 $mathbfxinmathbb{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 $sqrt2/s$. Furthermore, the signal support can be exactly identified provided the minimum magnitude exceeds $sqrt2logs$. 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.

Recommendations

• On adaptive sensing for high-dimensional signal inference
• Adaptive sensing for estimation of structured sparse signals
• How well can we estimate a sparse vector?
• Adaptive sparse recovery with limited adaptivity
• Lower bounds for adaptive sparse recovery

Cites work

• scientific article; zbMATH DE number 1149423 (Why is no real title available?)
• scientific article; zbMATH DE number 3045589 (Why is no real title available?)
• All of Nonparametric Statistics
• Analysis of perceptron-based active learning
• Asymptotically efficient adaptive allocation rules
• Compressed sensing
• Detection of a sparse submatrix of a high-dimensional noisy matrix
• Distilled Sensing: Adaptive Sampling for Sparse Detection and Estimation
• Estimating the proportion of false null hypotheses among a large number of independently tested hypotheses
• Estimation and confidence sets for sparse normal mixtures
• Hierarchical testing designs for pattern recognition
• Higher criticism for detecting sparse heterogeneous mixtures.
• Introduction to nonparametric estimation
• Minimax Bounds for Active Learning
• Nonparametric goodness-of-fit testing under Gaussian models
• On combinatorial testing problems
• On the Fundamental Limits of Adaptive Sensing
• On the power of adaption
• Rademacher complexities and bounding the excess risk in active learning
• Rates of convergence for the sup-norm risk in image models under sequential designs
• Rates of convergence in active learning
• Searching for a trail of evidence in a maze
• Selective sampling using the query by committee algorithm
• Sequential Design of Experiments
• Sequential methods for design-adaptive estimation of discontinuities in regression curves and surfaces
• Some problems of hypothesis testing leading to infinitely divisible distributions
• Übersichtsarbeiten

Cited in

(8)

• scientific article; zbMATH DE number 7559135 (Why is no real title available?)
• Adaptive sensing for estimation of structured sparse signals
• On the Fundamental Limits of Adaptive Sensing
• Performance Guarantees for Adaptive Estimation of Sparse Signals
• A novel detection scheme with multiple observations for sparse signal based on likelihood ratio test with sparse estimation
• Are there needles in a moving haystack? Adaptive sensing for detection of dynamically evolving signals
• On adaptive sensing for high-dimensional signal inference
• Detection of Sparse Stochastic Signals With Quantized Measurements in Sensor Networks

This page was built for publication: Adaptive sensing performance lower bounds for sparse signal detection and support estimation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q470072)