For-all Sparse Recovery in Near-Optimal Time

Anna C. Gilbert, Yi Li, Ely Porat +1

An approximate sparse recovery system in ${\ell }_1$ norm consists of parameters $k$, $\epsilon$, $N$, an $m$-by-$N$ measurement $\Phi$, and a recovery algorithm, $\mathcal{R}$. Given a vector,…