The blind deconvolution problem seeks to recover a pair of vectors from a set of rank one bilinear measurements. This problem appears in an array of different fields, including image processing, coding theory, and wireless communications. In this talk I will present a natural nonsmooth formulation of the problem and show that, under standard statistical assumptions, it satisfies nice regularity properties (even when a constant fraction of the measurements are arbitrarily corrupt). Which cause standard algorithms, such as the subgradient and prox-linear methods, to converge at a rapid dimension-independent rate when initialized within constant relative error of the solution. Additionally, I’ll introduce a new initialization strategy, complementing the local search algorithms. The initialization procedure is both provably efficient and robust to outlying measurements.

This is joint work with V. Charisopoulos, D. Davis, and D. Drusvyatskiy.