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
****************************