|Stochastic Systems Group|
Explicit constructions for compressed sensing problems
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 email@example.com