A Novel Nonconvex Rank Approximation with Application to the Matrix Completion

The matrix rank approximation has shown high effectiveness in the matrix rank minimization (MRM) problem, which aims to recover the underlying low-rank structure from the observed matrix by imposing the rank constraint. The nuclear norm, serving as a convex surrogate of matrix rank, is employed in the MRM problem by shrinking singular values of the observed entry. However, this substitution treats each singular value equally, which is virtually $ℓ_1$-norm penalty of the singular value vector. Theoretically, the rank function of the matrix can be considered as $ℓ_0$-norm of its singular values. Consequently, minimizing the nuclear norm frequently results in biased solutions in various applications. In this article, we first propose a novel nonconvex rank approximation, named tight and flexible rank (TFR) approximation, to describe rank function effectively. Specifically, the TFR approximation can more tightly approach the rank function and exhibit greater flexibility in handling diverse singular values, as compared to existing nonconvex rank approximations. Furthermore, we apply TFR approximation to matrix completion and develop a solving algorithm with guaranteed convergence based on the framework of proximal alternating minimization. Extensive experiments reveal that the proposed matrix completion model with TFR approximation outperforms several existing state-of-the-art convex and nonconvex methods.