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

Yunfeng Cai, Ping Li
Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, PMLR 108:4162-4172, 2020.

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_*\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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v108-cai20b, title = {Solving the Robust Matrix Completion Problem via a System of Nonlinear Equations}, author = {Cai, Yunfeng and Li, Ping}, booktitle = {Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics}, pages = {4162--4172}, year = {2020}, editor = {Chiappa, Silvia and Calandra, Roberto}, volume = {108}, series = {Proceedings of Machine Learning Research}, month = {26--28 Aug}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v108/cai20b/cai20b.pdf}, url = {https://proceedings.mlr.press/v108/cai20b.html}, 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_*\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.} }
Endnote
%0 Conference Paper %T Solving the Robust Matrix Completion Problem via a System of Nonlinear Equations %A Yunfeng Cai %A Ping Li %B Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2020 %E Silvia Chiappa %E Roberto Calandra %F pmlr-v108-cai20b %I PMLR %P 4162--4172 %U https://proceedings.mlr.press/v108/cai20b.html %V 108 %X 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.
APA
Cai, Y. & Li, P.. (2020). Solving the Robust Matrix Completion Problem via a System of Nonlinear Equations. Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 108:4162-4172 Available from https://proceedings.mlr.press/v108/cai20b.html.

Related Material