Low-rank matrix recovery with composite optimization: good conditioning and rapid convergence
This addresses a key computational bottleneck in low-rank matrix recovery for applications like phase retrieval and robust PCA, offering an incremental improvement in optimization efficiency.
The paper tackles the problem of poor conditioning in smooth formulations of low-rank matrix recovery by showing that nonsmooth penalty formulations avoid this issue, leading to rapid dimension-independent convergence for standard algorithms when properly initialized.
The task of recovering a low-rank matrix from its noisy linear measurements plays a central role in computational science. Smooth formulations of the problem often exhibit an undesirable phenomenon: the condition number, classically defined, scales poorly with the dimension of the ambient space. In contrast, we here show that in a variety of concrete circumstances, nonsmooth penalty formulations do not suffer from the same type of ill-conditioning. Consequently, standard algorithms for nonsmooth optimization, such as subgradient and prox-linear methods, converge at a rapid dimension-independent rate when initialized within constant relative error of the solution. Moreover, nonsmooth formulations are naturally robust against outliers. Our framework subsumes such important computational tasks as phase retrieval, blind deconvolution, quadratic sensing, matrix completion, and robust PCA. Numerical experiments on these problems illustrate the benefits of the proposed approach.