(1 + eps)-Approximate Sparse Recovery

The problem central to sparse recovery and compressive sensing is that of stable sparse recovery: we want a distribution A of matrices A∈R^m×n such that, for any c∈Rⁿ and with probability 1-δ>;2/3 over A∈A, there is an algorithm to recover x̂ from Ax with ∥x̂-x∥_p ≤ C_k-sparsex´^min∥x-x´∥_p (1) for some constant C>;1 and norm p. The measurement complexity of this problem is well understood for constant C>;1. However, in a variety of applications it is important to obtain C=1+ϵ for a small ϵ>;0, and this complexity is not well understood. We resolve the dependence on ϵ in the number of measurements required of a k-sparse recovery algorithm, up to polylogarithmic factors for the central cases of p=1 and p=2. Namely, we give new algorithms and lower bounds that show the number of measurements required is k/ϵ^p/2polylog(n). For p = 2, our bound of 1/ϵklog(n/k) is tight up to constant factors. We also give matching bounds when the output is required to be fc-sparse, in which case we achieve k/ϵ^ppolylog(n). This shows the distinction between the complexity of sparse and non sparse outputs is fundamental.