Compressive binary search

Abstract

In this paper we consider the problem of locating a nonzero entry in a high-dimensional vector from possibly adaptive linear measurements. We consider a recursive bisection method which we dub the compressive binary search and show that it improves on what any nonadaptive method can achieve. We also establish a non-asymptotic lower bound that applies to all methods, regardless of their computational complexity. Combined, these results show that the compressive binary search is within a double logarithmic factor of the optimal performance.

References in corpus (2)

• Near-Optimal Compressive Binary Search
• On the Fundamental Limits of Adaptive Sensing

Cited by in corpus (4)

• Near-Optimal Compressive Binary Search
• On the Fundamental Limits of Adaptive Sensing
• Adaptivity provably helps: information-theoretic limits on $l_0$ cost of non-adaptive sensing
• Sequential Sensing with Model Mismatch