(1 + ε)-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 ∈ ℝ m x n such that, for any x ∈ ℝ n and with probability 1 - δ >, 2/3 over A ∈ A, there is an algorithm to recover x̂ from Ax with ∥x̂ - x∥ p ≤ C min k-sparse x′∥x - x′∥ p 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/2 polylog(n). For p=2, our bound of 1/εk log (n/k) is tight up to constant factors. We also give matching bounds when the output is required to be k-sparse, in which case we achieve k/ε p polylog(n). This shows the distinction between the complexity of sparse and non-sparse outputs is fundamental. © 2011 IEEE.