On the power of adaptivity in sparse recovery
Piotr Indyk, Eric Price, et al.
FOCS 2011
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.
Piotr Indyk, Eric Price, et al.
FOCS 2011
Erich P. Stuntebeck, John S. Davis II, et al.
HotMobile 2008
Raymond Wu, Jie Lu
ITA Conference 2007
Pradip Bose
VTS 1998