The ACO Seminar (2011-2012)

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 http://arxiv.org/abs/1110.4414 and http://arxiv.org/abs/1110.3850.