Approximation of rank function and its application to the nearest low-rank correlation matrix

The rank function rank(.) is neither continuous nor convex which brings much difficulty to the solution of rank minimization problems. In this paper, we provide a unified framework to construct the approximation functions of rank(.), and study their favorable properties. Particularly, with two families of approximation functions, we propose a convex relaxation method for the rank minimization problems with positive semidefinite cone constraints, and illustrate its application by computing the nearest low-rank correlation matrix. Numerical results indicate that this convex relaxation method is comparable with the sequential semismooth Newton method (Li and Qi in SIAM J Optim 21:1641–1666, <CitationRef CitationID="CR22">2011</CitationRef>) and the majorized penalty approach (Gao and Sun, <CitationRef CitationID="CR14">2010</CitationRef>) in terms of the quality of solutions. Copyright Springer Science+Business Media New York 2013