2012/03/08 by Matthew Malloy, Matthew L. Malloy, Malloy, Matthew L. +2 · 1 citation
Computer Science · Engineering · Mathematics · #FOS: Computer and information sciences #Information Theory (cs.IT) #Machine Learning and Algorithms #Optimization and Search Problems #Sparse and Compressive Sensing Techniques #cs.IT #math.IT
paper · pdf · doi:10.48550/arxiv.1203.1804
openalex publication_date 2012/03/08 · arxiv created 2012/05/08 · arxiv updated 2012/05/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.