Emmanuel Candes,

California Institute of Technology

 
 

 

Applications of Compressive Sampling to Error Correction
Abstract

"Compressed Sensing'' or "Compressive Sampling'' (CS) is a new sampling or sensing theory which goes somewhat against the conventional wisdom in signal acquisition. This theory allows the faithful recovery of signals and images from what appear to be highly incomplete sets of data, i.e. from far fewer data bits than traditional methods use. It is believed that this phenomenon may have significant implications. For instance, CS may come to underlie procedures for sensing and compressing data simultaneously and much faster. In this talk, we will present the basic tenets of this new sampling theory and introduce applications in the area of error correction.

Consider a stylized communications problem where one wishes to transmit a real-valued signal x Î Rn (a block of n pieces of information) to a remote receiver. We ask whether it is possible to transmit this information reliably when a fraction of the transmitted codeword is corrupted by arbitrary (malicious) gross errors, and when in addition, all the entries of the codeword might be contaminated by smaller errors (e.g. quantization errors). We show that if one encodes the information as Ax where A Î Rmn (m≥n) is a suitable coding matrix, there are a couple of decoding schemes which allow the recovery of the block of n pieces of information x with nearly the same accuracy as if no gross errors occur upon transmission (or equivalently as if one has an oracle supplying perfect information about the sites and amplitudes of the gross errors). In the special case where there are only gross errors, the decoded vector is provably exact. The key point is that both decoding strategies are very concrete and only involve solving simple convex optimization programs, either a linear program or a second-order cone program. Numerical simulations show that the encoder/decoder pair performs remarkably well.

 

About the Speaker

Emmanuel Candes received his B. Sc. degree from the Ecole Polytechnique (France) in 1993, and the Ph.D. degree in statistics from Stanford University in 1998. He is the Ronald and Maxine Linde Professor of Applied and Computational Mathematics at the California Institute of Technology. Prior to joining Caltech, he was an Assistant Professor of Statistics at Stanford University, 1998--2000. His research interests are in computational harmonic analysis, multiscale analysis, approximation theory, statistical estimation and detection with applications to the imaging sciences, signal processing, scientific computing, inverse problems. Other topics of interest include theoretical computer science, mathematical optimization, and information theory.

Dr. Candes received the Third Popov Prize in Approximation Theory in 2001, and the DOE Young Investigator Award in 2002. He was selected as an Alfred P. Sloan Research Fellow in 2001. He co-authored a paper that won the Best Paper Award of the European Association for Signal, Speech and Image Processing (EURASIP) in 2003. He was selected as the main lecturer at the NSF-sponsored 29th Annual Spring Lecture Series in the Mathematical Sciences in 2004 and as the Aziz Lecturer in 2007.

He was awarded the James H. Wilkinson Prize in Numerical Analysis and  Scientific Computing by SIAM in 2005. He is the recipient of the 2006  Alan T. Waterman Medal awarded by the US National Science Foundation.