2013/04/23 by Anna C. Gilbert, Gilbert, Anna C., Hung Q. Ngo +7 · 24 citations
Computer Science · Engineering · Mathematics · #Algorithm #Binary logarithm #Bounded function #Combinatorics #Compressed sensing #Computer science #Constant (computer programming) #Data Structures and Algorithms (cs.DS) #Decoding methods #Discrete mathematics #Distributed Sensor Networks and Detection Algorithms #FOS: Computer and information sciences #Matching (statistics) #Mathematical analysis #Mathematics #Microwave Imaging and Scattering Analysis #Omega #Physics #Sparse and Compressive Sensing Techniques #Statistics #Upper and lower bounds #cs.DS
paper · pdf · doi:10.48550/arxiv.1304.6232
published in arXiv (Cornell University) (Cornell University) · 1 figure, extended abstract to appear in ICALP 2013
arxiv created 2013/04/23 · openalex publication_date 2013/04/23 · arxiv updated 2013/04/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/06
In this paper, we consider the "foreach" sparse recovery problem with failure probability p. The goal of which is to design a distribution over m × N matrices Φ and a decoding algorithm \algo such that for every \vx∈\RN, we have the following error guarantee with probability at least 1-p ‖\vx-\algo(Φ\vx)‖2≤ C‖\vx-\vxk‖2, where C is a constant (ideally arbitrarily close to 1) and \vxk is the best k-sparse approximation of \vx. Much of the sparse recovery or compressive sensing literature has focused on the case of either p = 0 or p = Ω(1). We initiate the study of this problem for the entire range of failure probability. Our two main results are as follows: \beginenumerate \item We prove a lower bound on m, the number measurements, of Ω(klog(n/k)+log(1/p)) for 2-Θ(N)≤ p <1. Cohen, Dahmen, and DeVore \citeCDD2007:NearOptimall2l2 prove that this bound is tight. \item We prove nearly matching upper bounds for sub-linear time decoding. Previous such results addressed only p = Ω(1). \endenumerate Our results and techniques lead to the following corollaries: (i) the first ever sub-linear time decoding \lolo "forall" sparse recovery system that requires a logγN extra factor (for some γ<1) over the optimal O(klog(N/k)) number of measurements, and (ii) extensions of Gilbert et al. \citeGHRSW12:SimpleSignals results for information-theoretically bounded adversaries.