Solving the Robust Matrix Completion Problem via a System of Nonlinear Equations

Abstract

We consider the problem of robust matrix completion, which aims to recover a low rank matrix L_* and a sparse matrix S_* from incomplete observations of their sum M=L_*+S_*R^m n. Algorithmically, the robust matrix completion problem is transformed into a problem of solving a system of nonlinear equations, and the alternative direction method is then used to solve the nonlinear equations. In addition, the algorithm is highly parallelizable and suitable for large scale problems. Theoretically, we characterize the sufficient conditions for when L_* can be approximated by a low rank approximation of the observed M_*. And under proper assumptions, it is shown that the algorithm converges to the true solution linearly. Numerical simulations show that the simple method works as expected and is comparable with state-of-the-art methods.

Tasks

Reproductions