Robust Matrix Completion Via Lp-Greedy Pursuits

A novel $\ell_p$-greedy pursuit (GP) algorithm for robust matrix completion, i.e., recovering a low-rank matrix from only a subset of its noisy and outlier-contaminated entries, is devised. The $\ell_p$-GP uses the strategy of sequential rank-one update. In each iteration, a rank-one completion is solved by minimizing the $\ell_p$-norm of the residual. Unlike the existing greedy methods that use the principal singular vectors of the residual matrix as the solution to the rank-one completion with the index information of the observed entries being ignored, the $\ell_p$-GP employs alternating minimization to obtain an improved solution by fully exploiting the index information. More importantly, it achieves outlier-robustness by setting $p=1$. For $p=1$, only computing the weighted medians is involved, which yields that the complexity is near-linear with the number of observations. The low complexity enables the $\ell_1$-GP to be applicable to very large-scale problems. Simulation results demonstrate the superiority of the $\ell_p$-GP over other approaches.