In this paper, we consider the "foreach" sparse recovery problem with failure probability p. The goal of the problem is to design a distribution over m × N matrices Φ and a decoding algorithm A such that for every x ∈ R~N, we have with probability at least 1 - p ‖x-A(Φx)‖_2≤C‖x-x_k‖_2, where x_k is the best k-sparse approximation of x. Our two main results are: (1) 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 prove that this bound is tight. (2) We prove nearly matching upper bounds that also admit sub-linear time decoding. Previous such results were obtained only when p = Ω(1). One corollary of our result is an an extension of Gilbert et al. results for information-theoretically bounded adversaries.
展开▼
