Apr 26, 3:30pm, Wean 8220

Eric Price, MIT

Algorithms and Lower Bounds for Sparse Recovery

Eric Price, MIT

Algorithms and Lower Bounds for Sparse Recovery

Abstract:

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.