arrow
Volume 15, Issue 4
A Novel Nonconvex Rank Approximation with Application to the Matrix Completion

Jin-Liang Xiao, Ting-Zhu Huang, Zhong-Cheng Wu & Liang-Jian Deng

East Asian J. Appl. Math., 15 (2025), pp. 741-769.

Published online: 2025-06

Export citation
  • Abstract

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.

  • AMS Subject Headings

68U10, 65K10, 15A83

  • Copyright

COPYRIGHT: © Global Science Press

  • Email address
  • BibTex
  • RIS
  • TXT
@Article{EAJAM-15-741, author = {Xiao , Jin-LiangHuang , Ting-ZhuWu , Zhong-Cheng and Deng , Liang-Jian}, title = {A Novel Nonconvex Rank Approximation with Application to the Matrix Completion}, journal = {East Asian Journal on Applied Mathematics}, year = {2025}, volume = {15}, number = {4}, pages = {741--769}, abstract = {

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.

}, issn = {2079-7370}, doi = {https://doi.org/10.4208/eajam.2023-259.140824}, url = {http://global-sci.org/intro/article_detail/eajam/24195.html} }
TY - JOUR T1 - A Novel Nonconvex Rank Approximation with Application to the Matrix Completion AU - Xiao , Jin-Liang AU - Huang , Ting-Zhu AU - Wu , Zhong-Cheng AU - Deng , Liang-Jian JO - East Asian Journal on Applied Mathematics VL - 4 SP - 741 EP - 769 PY - 2025 DA - 2025/06 SN - 15 DO - http://doi.org/10.4208/eajam.2023-259.140824 UR - https://global-sci.org/intro/article_detail/eajam/24195.html KW - Rank minimization, low-rank matrix completion, rank approximation. AB -

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.

Xiao , Jin-LiangHuang , Ting-ZhuWu , Zhong-Cheng and Deng , Liang-Jian. (2025). A Novel Nonconvex Rank Approximation with Application to the Matrix Completion. East Asian Journal on Applied Mathematics. 15 (4). 741-769. doi:10.4208/eajam.2023-259.140824
Copy to clipboard
The citation has been copied to your clipboard