Matrix completion via minimizing an approximate rank

Xueying Zeng, Lixin Shen, Yuesheng Xu, Jian Lu

Research output: Contribution to journalArticlepeer-review

3 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)689-713
Number of pages25
JournalAnalysis and Applications
Issue number5
StatePublished - Sep 1 2019


  • Low rank matrices
  • matrix completion
  • singular value decomposition

ASJC Scopus subject areas

  • Analysis
  • Applied Mathematics


Dive into the research topics of 'Matrix completion via minimizing an approximate rank'. Together they form a unique fingerprint.

Cite this