Robust M-estimation Based Matrix Completion

Abstract

Conventional approaches to matrix completion are sensitive to outliers and impulsive noise. This paper develops robust and computationally efficient M-estimation based matrix completion algorithms. By appropriately arranging the observed entries, and then applying alternating minimization, the robust matrix completion problem is converted into a set of regression M-estimation problems. Making use of differentiable loss functions, the proposed algorithm overcomes a weakness of the ℓ <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</sub> -loss (p ≤ 1), which easily gets stuck in an inferior point. We prove that our algorithm converges to a stationary point of the nonconvex problem. Huber's joint M-estimate of regression and scale can be used as a robust starting point for Tukey's redescending M-estimator of regression based on an auxiliary scale. Numerical experiments on synthetic and real-world data demonstrate the superiority to state-of-the-art approaches.