The Taub Faculty of Computer Science Events and Talks

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.