Compressive binary search
Mark A. Davenporta b, Ery Arias-castro Ac d
- aDepartment of Statistics, University of Stanford, USA
- bDept. of Statistics, Stanford University#TAB#
- cDepartment of Mathematics, University of California, San Diego, USA
- dDepartment of Mathematics University of California, San Diego
Papers open inside SciRah from the original publisher or repository; SciRah never hosts them.
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.
TL;DRThis paper considers a recursive bisection method which is dubbed the compressive binary search and shows that it improves on what any nonadaptive method can achieve, and establishes a non-asymptotic lower bound that applies to all methods, regardless of their computational complexity. (Semantic Scholar)