Stochastic Systems Group
Home Research Group Members Programs  
Demos Calendar Publications Mission Statement Alumni

SSG Seminar Abstract

Explicit constructions for compressed sensing problems

Piotr Indyk

Compressed sensing (a.k.a. signal sketching) is a recent paradigm for recovering a "large" signal from a "small" number of measurements. Specifically, consider d-dimensional signals x of low-complexity (e.g., having at most m non-zero elements). The goal is to construct a t * d matrix A, t "close to" m, such that one can efficiently recover any low-complexity 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