Robust Matrix Completion via ℓP-Greedy Pursuits

Xue Jiang; Abdelhak M. Zoubir; Xingzhao Liu

ICASSP 2020accepted0 citations

Robust Matrix Completion via ℓP-Greedy Pursuits

Xue Jiang, Abdelhak M. Zoubir, Xingzhao Liu

Abstract

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

BibTeX

@inproceedings{icassp2020_robustmatrixcomp,
  title = {Robust Matrix Completion via ℓP-Greedy Pursuits},
  author = {Xue Jiang and Abdelhak M. Zoubir and Xingzhao Liu},
  booktitle = {ICASSP 2020},
  year = {2020}
}