Robust Matrix Completion via l_P-Greedy Pursuits

摘要

A novel l_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 l_p-GP uses the strategy of sequential rank-one update. In each iteration, a rank-one completion is solved by minimizing the l_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 l_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 l_1-GP to be applicable to very large-scale problems. Simulation results demonstrate the superiority of the l_p-GP over other approaches.