UC Davis Mathematics

Mathematics Colloquia and Seminars

Return to Colloquia & Seminar listing

Murder, Matrices, and Minima - Adventures in Blind Deconvolution

PDE and Applied Math Seminar

Speaker: Thomas Strohmer, UC Davis
Location: 1147 MSB
Start time: Fri, May 20 2016, 4:10PM

I will first decribe how I once failed to catch a murderer (dubbed the "graveyard murderer" by the media), because I failed in solving a blind deconvolution problem. Blind deconvolution refers to the following problem: Assume we are given a function y which arises as the convolution of two unknown functions g and h; when and how is it possible to recover g and h from the knowledge of y? Blind deconvolution pervades many areas of science and technology, including astronomy, medical imaging, optics, and communications engineering. Blind deconvolution is obviously ill-posed and even under additional assumptions this is a very difficult non-convex problem full of undesirable local minima. I will then present the first blind deconvolution algorithm that is numerically efficient and at the same time comes with rigorous convergence guarantees. The mathematical techniques behind our framework carefully exploit methods from random matrix theory combined with tools from non-convex optimization.

We will also consider the even more difficult situation of a mixture of blind deconvolution problems, where we need to correctly blindly deconvolve and separate (demix) multiple functions at the same time from just a single measured function. I present a powerful convex framework for the solution of this problem and if time permits discuss connections to discrete geometry, quantum physics, and sphere packings. This problem is expected to play an important role in connection with the future Internet-of-Things. Thus, while the graveyard murderer is still on the loose, recent progress in blind deconvolution may at least have positive impact on the Internet-of-Things. (Joint work with Xiaodong Li, Shuyang Ling, and Ke Wei.)