Three Recent Examples of the Effectiveness of Convex Programming in the Information Sciences

2013 ISIT Plenary Lecture
Three Recent Examples of the Effectiveness of Convex Programming in the Information Sciences
Emmanuel Candes
Stanford University


This talk discusses three concrete problems characterized by incomplete information about an object of interest. The first is the century-old phase retrieval problem where intensity-only measurements -- phase information is completely missing -- are available about an image as in X-ray crystallography, and we wish to recover the phase. The second is a problem in data analysis, where we observe only a few entries in a data matrix -- for instance users' preferences for a collection of items -- which may have been further corrupted, and we wish to infer reliably all the missing and corrupted entries. The third is the super-resolution problem where one can only observe the low-frequencies of a signal and/or image due to physical laws, and wish to recover the high-end of its spectrum as to `beat' the diffraction limit'. To retrieve what seems lost, we describe three simple solutions with a common theme, namely, the use of ideas from semidefinite programming. We present some theory explaining when one can and cannot expect these methods to provide accurate answers, as well as some applications. 


Emmanuel Candès is the Barnum-Simons in Mathematics and Statistics, and a Professor of Electrical Engineering (by courtesy) at Stanford University. He received his Ph.D. degree in statistics from Stanford in 1998. His research interests are in computational harmonic analysis, statistics, information theory, signal processing and mathematical optimization. He received several awards including the Alan T. Waterman Award -- the highest honor bestowed by the National Science Foundation which recognizes the achievements of scientists who are no older than 35, or not more than seven years beyond their doctorate. He has given over 50 plenary lectures at major international conferences.