Wednesday, 15.12.2010, 13:30
Sparse recovery, or compressive sensing, is the problem of approximating
a vector x from a low-dimensional linear sketch Ax, where A is an m x n
matrix with m << n. We cannot recover x exactly, so we require that, if
x is "close" to being "good", the recovered vector is "close" to x.
Essentially optimal solutions are known when "close" uses l_1 or l_2
distance and "good" means being k-sparse, but not for other definitions
of "close" and "good".
We give a framework for sparse recovery where the problem is split into
two parts. In the first part we locate the large coefficients of x, and
in the second part we estimate their values (termed the "set query
problem"). We give an optimal algorithm for the set query problem,
leaving only the first part for problem-specific development. We then
give improved algorithms for locating the large coefficients when x is
close to being (1) distributed according to a power law distribution or
(2) block sparse. In contrast to methods based on pseudoinverses or
dense matrices, our constructions use sparse matrices and support linear
or nearly linear recovery time.