Near-Optimal Adaptive Compressed Sensing

DOI10.1109/TIT.2014.2321552zbMATH Open1360.94088arXiv1306.6239OpenAlexW2121835854MaRDI QIDQ2986271FDOQ2986271

Matthew L. Malloy, Robert D. Nowak

Publication date: 16 May 2017

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Abstract: This paper proposes a simple adaptive sensing and group testing algorithm for sparse signal recovery. The algorithm, termed Compressive Adaptive Sense and Search (CASS), is shown to be near-optimal in that it succeeds at the lowest possible signal-to-noise-ratio (SNR) levels, improving on previous work in adaptive compressed sensing. Like traditional compressed sensing based on random non-adaptive design matrices, the CASS algorithm requires only k log n measurements to recover a k-sparse signal of dimension n. However, CASS succeeds at SNR levels that are a factor log n less than required by standard compressed sensing. From the point of view of constructing and implementing the sensing operation as well as computing the reconstruction, the proposed algorithm is substantially less computationally intensive than standard compressed sensing. CASS is also demonstrated to perform considerably better in practice through simulation. To the best of our knowledge, this is the first demonstration of an adaptive compressed sensing algorithm with near-optimal theoretical guarantees and excellent practical performance. This paper also shows that methods like compressed sensing, group testing, and pooling have an advantage beyond simply reducing the number of measurements or tests -- adaptive versions of such methods can also improve detection and estimation performance when compared to non-adaptive direct (uncompressed) sensing.

Full work available at URL: https://arxiv.org/abs/1306.6239

Mathematics Subject Classification ID

Signal theory (characterization, reconstruction, filtering, etc.) (94A12)

Cited In (7)

• Adaptive Matrix Design for Boosting Compressed Sensing
• Optimal Phase Transitions in Compressed Sensing
• Approximation Algorithms for Model-Based Compressive Sensing
• Competitive optimization of compressed sensing
• An adaptive inverse scale space method for compressed sensing
• Statistical properties of SNR for compressed measurements
• Energy-based spectrum sensing under nonreconstruction framework

This page was built for publication: Near-Optimal Adaptive Compressed Sensing

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