Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People
Events

The Taub Faculty of Computer Science Events and Talks

Pixel Club Seminar: Efficient Linear Sketches for the Set Query Problem
event speaker icon
Eric Price (MIT)
event date icon
Wednesday, 15.12.2010, 13:30
event location icon
EE Meyer Building 1061
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.