The Complexity of Stable Sparse Recovery

(1+eps)-approximate Sparse Recovery

We give new algorithms and lower bounds that show the dependence on eps 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. for p = 2, our bound of (1/eps) 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 (1/eps^p) k polylog(n).This shows the distinction between the complexity of sparse and non-sparse outputs is fundamental.