Outlier-Robust Matrix Completion via p-Minimization

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journal

12 Scopus Citations
View graph of relations


Related Research Unit(s)


Original languageEnglish
Article number8219728
Pages (from-to)1125-1140
Journal / PublicationIEEE Transactions on Signal Processing
Issue number5
Online published18 Dec 2017
Publication statusPublished - 1 Mar 2018


Matrix completion refers to recovering a low-rank matrix from only a subset of its possibly noisy entries, and has a variety of important applications because many real-world signals can be modeled by a n1 × n2 matrix with rank r << min (n1, n2). Most existing techniques for matrix completion assume Gaussian noise and, thus, they are not robust to outliers. In this paper, we devise two algorithms for robust matrix completion based on low-rank matrix factorization and p-norm minimization of the fitting error with 0 < p < 2. The first method tackles the low-rank matrix factorization with missing data by iteratively solving (n1 + n2) linear p-regression problems, whereas the second applies the alternating direction method of multipliers (ADMM) in the p-space. At each iteration of the ADMM, it requires performing a least squares (LS) matrix factorization and calculating the proximity operator of the pth power of the p-norm. The LS factorization is efficiently solved using linear LS regression while the proximity operator has closed-form solution for p=1 or can be obtained by root finding of a scalar nonlinear equation for other values of p. The two proposed algorithms have comparable recovery capability and computational complexity of O(K|Ω|r2), where |Ω| is the number of observed entries and K is a fixed constant of several hundreds to thousands and dimension independent. It is demonstrated that they are superior to the singular value thresholding, singular value projection, and alternating projection schemes in terms of computational simplicity, statistical accuracy, and outlier-robustness.

Research Area(s)

  • Alternating direction method of multipliers (ADMM), lp-minimization, Matrix completion, matrix factorization, outlier, robust recovery