2009.04.15 | Else Magård

Title: Lower Bounds in Compressed Sensing

Speaker: Eric Price, Massachusetts Institute of Technology (MIT)

Abstract:

Compressed sensing is a method for reconstructing a sparse signal from a low-rank linear sketch.This is useful because many real-world signals have sparserepresentations in some basis; for example, images are sparse in the wavelet basis and music is sparse in the Fourier basis.

In the past five years, a variety of sketch matrices and reconstruction techniques have emerged that can efficiently and stably recover an N-dimensional vector withK non-zero components from O(K log N/K) linear measurements.

We prove that any stable recovery scheme requires O(Klog N/K) linear measurements, matching the upper bound. This contrasts with the T(K) measurements required for unstable recovery.

Joint work with:

Piotr Indyk, MIT
Khanh Do Ba, MIT

Host: Gerth Stølting Brodal