Open Lecture — The Effectiveness of Convex Programming in the Information and Physical Sciences

We discuss 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 wishes to recover the high end of its spectrum so 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.

Light refreshments will be served before the lecture at 3:30 p.m.