ACO The ACO Seminar (2011-2012)

Apr 26, 3:30pm, Wean 8220
Eric Price, MIT
Algorithms and Lower Bounds for Sparse Recovery


The goal of stable sparse recovery or compressive sensing is to recover a K-sparse approximation x* of a vector x in R^N from M linear measurements of x. This problem has a wide variety of applications, including streaming algorithms, image acquisition, and genetic testing. A common formulation is to recover x* such that

||x-x*||_2 < (1 + eps) min_{K-sparse x'} ||x-x'||_2

for some constant eps with 3/4 probability over the choice of measurements.

In this talk, we will give upper and lower bounds for this problem. For the nonadaptive setting, where all the measurements must be chosen independent of x, we give a lower bound showing M = Theta((1/eps) K log (N/K)) is optimal. In the adaptive setting, where each measurement may be based on the results of previous measurements, we show that M = O((1/\eps) K log log (N/K)) is possible, an exponential improvement in N/K.

These results contain joint work with David Woodruff and Piotr Indyk, and appeared in FOCS 2011. They are available at and

Back to the ACO home page