Mathematics Colloquium: Nonconvex compressive sensing: getting the most from very little information
12:10 pm, CUE 319
Abstract: In this talk we'll look at the exciting, recent results showing that most images and other signals can be reconstructed from much less information than previously thought possible, using simple, efficient algorithms. A consequence has been the explosive growth of the new field known as compressive sensing, so called because the results show how a small number of measurements of a signal can be regarded as tantamount to a compression of that signal. The many potential applications include reducing exposure time in medical imaging, sensing devices that can collect much less data in the first place instead of collecting and then compressing, getting reconstructions from what seems like insufficient data (such as EEG), and very simple compression methods that are effective for streaming data and preserve nonlinear geometry. We'll see how replacing the convex optimization problem typically used in this field with a nonconvex variant has the effect of reducing still further the number of measurements needed to reconstruct a signal. A very surprising result is that a simple algorithm, designed only for finding one of the many local minima of the optimization problem, typically finds the global minimum. Understanding this is an interesting and challenging theoretical problem. We'll see examples, and discuss algorithms, theory, and applications.