Solving the Robust Matrix Completion Problem via a System of Nonlinear Equations
This addresses robust matrix recovery from incomplete data, which is incremental as it builds on existing methods with a new algorithmic approach.
The paper tackles robust matrix completion by transforming it into solving a system of nonlinear equations using an alternative direction method, achieving linear convergence under assumptions and performing comparably to state-of-the-art methods in simulations.
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_*\in\mathbb{R}^{m\times 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.