# Near-Optimal Adaptive Compressed Sensing

arXiv: https://arxiv.org/abs/1306.6239 · HTML: https://mlsanity.com/paper/1306.6239/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Jun 2013.

## Built on by (most cited first, 8 of 8)

- [Adaptive Compressed Sensing with Diffusion-Based Posterior Sampling](https://mlsanity.com/paper/2407.08256/) (2024)
- [The Role of Interactivity in Structured Estimation](https://mlsanity.com/paper/2203.06870/) (2022)
- [Active Learning of Piecewise Gaussian Process Surrogates](https://mlsanity.com/paper/2301.08789/) (2023)
- [Active Structure Learning of Bayesian Networks in an Observational Setting](https://mlsanity.com/paper/2103.13796/) (2021)
- [RL-NCS: Reinforcement learning based data-driven approach for nonuniform compressed sensing](https://mlsanity.com/paper/2107.00838/) (2021)
- [Multi-Agent Active Search using Detection and Location Uncertainty](https://mlsanity.com/paper/2203.04524/) (2022)
- [Gaussian Process Model for Estimating Piecewise Continuous Regression Functions](https://mlsanity.com/paper/2104.06487/) (2021)
- [Reinforcement Learning of Adaptive Acquisition Policies for Inverse Problems](https://mlsanity.com/paper/2407.07794/) (2024)

## Abstract (arXiv)

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.