Robust Matrix Completion via Alternating Projection

Matrix completion aims to find the missing entries from incomplete observations using the low-rank property. Conventional convex optimization based techniques for matrix completion minimize the nuclear norm subject to a constraint on the Frobenius norm of the residual. However, they are not robust to outliers and have a high computational complexity. Different from the existing schemes based on solving a minimization problem, we formulate matrix completion as a feasibility problem. An alternating projection algorithm (APA) is devised to find a feasible point in the intersection of the low-rank constraint set and fidelity constraint set. To achieve resistance to outliers, the fidelity constraint set is modeled as an ℓ_p-ball, where the ball center corresponds to the observed data. Furthermore, there is no stepsize within the framework of APA. Convergence of the APA is analyzed and the local linear convergence rate is established. Simulation results demonstrate the efficiency, accuracy, and outlier robustness of the APA.

I. Introduction

Matrix completion refers to finding the missing entries of a matrix from incomplete observations by making the use of the low-rank property [1]– [4]. It has a variety of applications in many fields, such as recommender systems, image inpainting and restoration, and path loss reconstruction [1]– [6].