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, 2011) and the majorized penalty approach (Gao and Sun, 2010) in terms of the quality of solutions.