MINDS 2021 Winter Symposium- Mateo Díaz
Title– Composite optimization for robust low-rank matrix recovery: good conditioning and rapid convergence
Abstract– The task of recovering a structured signal from its noisy linear measurements plays a central role in computational science. Smooth optimization formulations for these problems often exhibit an undesirable phenomenon: the condition number, classically defined, scales poorly with the dimension of the ambient space. The goal of the talk is to introduce a variety of concrete circumstances where nonsmooth penalty formulations present two clear advantages over their smooth counterparts: first, they do not suffer from the same type of ill-conditioning, and second, they are robust against noise and gross outliers. As a consequence, standard algorithms for nonsmooth optimization, such as subgradient and prox-linear methods, converge at a rapid dimension-independent rate, when initialized close to the solution, even when a constant fraction of the measurements are corrupted. This framework subsumes such important computational tasks as matrix sensing, phase retrieval, blind deconvolution, matrix completion, and robust PCA. To complement these results, we present a spectral initialization method for the blind deconvolution problem that can handle high levels of outliers. Numerical experiments illustrate the benefits of the proposed approach.