Sparse Representation in Redundant Systems

CSIC Building (#406), Seminar Room 4122.
Directions: home.cscamm.umd.edu/directions

Decoding by Linear Programming and Other Perhaps Surprising Phenomena

Dr. Emmanuel Candes

Applied / Computational Mathematics at California Institute of Technology

Abstract:   Suppose we wish to transmit an n-dimensional vector f (the ``plaintext'). We generate another m-dimensional vector Af (the ``ciphertext') where A is an m by n matrix with m > n which is to be sent. A recurrent problem with real communication or storage devices is that some of the entries of the ciphertext may become corrupted; the corrupted entries are unreliable and may have nothing to do with the original values. We do not know which entries are affected nor do we know how they are affected. We will show that no matter what the corruption is like, it is provably possible to recover the original message by solving a convenient linear program (provided that the fraction of corrupted entries is not excessively large). This work is related to the problem of finding sparse solutions to vastly underdetermined systems of linear equations. I will discuss these significant connections and introduce a new collection of results showing that it is possible to recover sparse or compressible signals accurately, and sometimes even exactly, from highly incomplete measurements. Parts of this work are joint with Terence Tao and Justin Romberg.

[LECTURE SLIDES]