Stochastic Systems Group  

Explicit constructions for compressed sensing problems
Piotr Indyk
MIT
Compressed sensing (a.k.a. signal sketching) is a recent paradigm for recovering a "large" signal from a "small" number of measurements. Specifically, consider ddimensional signals x of lowcomplexity (e.g., having at most m nonzero elements). The goal is to construct a t * d matrix A, t "close to" m, such that one can efficiently recover any lowcomplexity signal x from the t measurements Ax. Such results have interesting applications in several areas, such as digital signal processing and data stream algorithms.
There are by now several results showing existence of matrices A with the desired properties. Until recently, however, all of them were constructed probabilistically. In this talk I will give an overview of very recent *explicit* constructions of such matrices.
Problems with this site should be emailed to jonesb@mit.edu