2013 ISIT Plenary Lecture
Three Recent Examples of the Effectiveness of Convex Programming in the Information Sciences
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.