Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 278B - Mathematics of Information, Data, and Signals

Dominik St"oger

University of Southern California

On the convex geometry of blind deconvolution and matrix completion

Abstract:

Low-rank matrix recovery from structured measurements has been a topic of intense study in the last decade and many important problems such as blind deconvolution and matrix completion have been formulated in this framework. An important benchmark method to solve these problems is to minimize the nuclear norm, a convex proxy for the rank. A common approach to establish recovery guarantees for this convex program relies on the construction of a so-called approximate dual certificate. However, this approach provides only limited insight in various respects. Most prominently, the noise bounds exhibit seemingly suboptimal dimension factors. In this talk, we will discuss a more geometric viewpoint to analyze the blind deconvolution scenario. We find that for both these applications the dimension factors in the noise bounds are not an artifact of the proof, but the problems are intrinsically badly conditioned. We show, however, that bad conditioning only arises for very small noise levels: Under mild assumptions that include many realistic noise levels we derive near-optimal error estimates for blind deconvolution under adversarial noise. At the end, we will briefly discuss how the results can be extended to the scenario of matrix completion.

Host: Rayan Saab

February 20, 2020

10:00 AM

AP&M 2402

****************************