TY - GEN
T1 - ℓ2/ℓ2-foreach sparse recovery with low risk
AU - Gilbert, Anna C.
AU - Ngo, Hung Q.
AU - Porat, Ely
AU - Rudra, Atri
AU - Strauss, Martin J.
PY - 2013
Y1 - 2013
N2 - 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 x N matrices Φ and a decoding algorithm A such that for every x ∈ ℝN, we have with probability at least 1 - p ∥x - A(Φx∥2 ≤ C∥x - xk∥2, where xk 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 Ω(k log(n/k) + log(1/p)) for 2-Θ(N) ≤ p < 1. Cohen, Dahmen, and DeVore [4] 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. [6] results for information-theoretically bounded adversaries.
AB - 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 x N matrices Φ and a decoding algorithm A such that for every x ∈ ℝN, we have with probability at least 1 - p ∥x - A(Φx∥2 ≤ C∥x - xk∥2, where xk 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 Ω(k log(n/k) + log(1/p)) for 2-Θ(N) ≤ p < 1. Cohen, Dahmen, and DeVore [4] 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. [6] results for information-theoretically bounded adversaries.
UR - https://www.scopus.com/pages/publications/84880272599
U2 - 10.1007/978-3-642-39206-1_39
DO - 10.1007/978-3-642-39206-1_39
M3 - Conference contribution
AN - SCOPUS:84880272599
SN - 9783642392054
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 461
EP - 472
BT - Automata, Languages, and Programming - 40th International Colloquium, ICALP 2013, Proceedings
T2 - 40th International Colloquium on Automata, Languages, and Programming, ICALP 2013
Y2 - 8 July 2013 through 12 July 2013
ER -