Alternating Direction Method Of Multipliers For Robust Low Rank Matrix Completion

The matrix completion is the process of completing a matrix with missing ele-ments.In recent years,the matrix completion has been applied to recommendation systems,image recovery,trust prediction and other fields.How to design a reasonable matrix completion model and an effective algorithm have been a hot topic.Generally speaking,the matrix we wish to recover has the structure of low rank or approximately low rank.But the rank function is nonconvex and discontinuous,the rank minimization problem is generally NP-hard.Current researches focus on the convex approximation,nonconvex approximation of the rank function,or the matrix decomposition.There are some errors between there approximate models and the solution of the rank function minimization model,which may affect the completion effect.Moreover,it is very likely that the observed matrix is polluted by a variety of noise.In this paper,we aim to eliminate a kind of row structured noise which often appears in recommendation systems.We propose a novel robust low rank matrix completion model,which adds the L_2,1-norm penalty directly to the rank function in the objective function in order to alleviate the row structured noise under the condition of equality constraint.We adapt the alternating direction method of multipliers?ADMM?to solve the nonconvex and discontinuous model directly and show its convergence.We show that the sequence generated by the ADMM is bounded,the subsequence converges to the stationary point of the model under certain assumptions.Finally,extensive numer-ical results on artificial and real datasets show that compared with the state-of-the-art methods,our method can get the completion matrix with the structure of low rank and less affected by the row structured noise within acceptable computation time.