Near-Optimal Compressive Binary Search

Understand

We propose a simple modification to the recently proposed compressive binary search.

• The modification removes an unnecessary and suboptimal factor of log log n from the SNR requirement, making the procedure optimal (up to a small constant).
• Simulations show that the new procedure performs significantly better in practice as well.
• We also contrast this problem with the more well known problem of noisy binary search.