Matrix completion via minimizing an approximate rank

The low rank matrix completion problem which aims to recover a matrix from that having missing entries has received much attention in many fields such as image processing and machine learning. The rank of a matrix may be measured by the 0 norm of the vector of its singular values. Due to the nonconvexity and discontinuity of the 0 norm, solving the low rank matrix completion problem which is clearly NP hard suffers from computational challenges. In this paper, we propose a constrained matrix completion model in which a novel nonconvex continuous rank surrogate is used to approximate the rank function of a matrix, promote low rank of the recovered matrix and address the computational challenges. The proposed rank surrogate differs from the convex nuclear norm and other existing state-of-the-art nonconvex surrogates in a way that it alleviates the discontinuity and nonconvexity of the rank function through a local 2-relaxation of the 0 norm so that it possesses several desirable properties. These properties ensure that it accurately approximates the rank function by choosing an appropriate relaxation parameter. We moreover develop an efficient iterative algorithm to solve the resulting model. We also propose strategies of automatically updating the relaxation parameter to practically ensure the global convergence and speed up the algorithm. We establish theoretical convergence results for the proposed algorithm. Experimental results are presented to demonstrate significant performance improvements of the proposed model and the associated algorithm as compared to state-of-the-art methods in both recoverability and computational efficiency.