This paper is concerned with the model of column $ \ell_{2, 0} $-regularized factorization for inductive matrix completion. The column $ \ell_{2, 0} $-norm is an exact variational characterization of the rank function, promoting low-rank structure through column sparsity of the matrix. We established that the stationary points between the $ \ell_{2, 0} $-norm regularized factorization model and the rank regularized model are equivalent. Under a suitable assumption, an error bound to the true matrix was obtained for the stationary points with rank not more than that of the true matrix. For this nonconvex discontinuous optimization problem, we developed a proximal alternating minimization (PAM) algorithm with subspace correction and showed that the whole sequence globally converges to a stationary point of the rank regularized model. Numerical experiments conducted with examples of both synthetic and real data demonstrated the effectiveness of the proposed method.
Citation: Ting Tao, Lianghai Xiao, Zetian Chen, Xijie Lin. Column $ \ell_{2, 0} $-norm regularized factorization model for inductive matrix completion[J]. AIMS Mathematics, 2025, 10(8): 17602-17622. doi: 10.3934/math.2025786
This paper is concerned with the model of column $ \ell_{2, 0} $-regularized factorization for inductive matrix completion. The column $ \ell_{2, 0} $-norm is an exact variational characterization of the rank function, promoting low-rank structure through column sparsity of the matrix. We established that the stationary points between the $ \ell_{2, 0} $-norm regularized factorization model and the rank regularized model are equivalent. Under a suitable assumption, an error bound to the true matrix was obtained for the stationary points with rank not more than that of the true matrix. For this nonconvex discontinuous optimization problem, we developed a proximal alternating minimization (PAM) algorithm with subspace correction and showed that the whole sequence globally converges to a stationary point of the rank regularized model. Numerical experiments conducted with examples of both synthetic and real data demonstrated the effectiveness of the proposed method.
| [1] |
H. Attouch, J. Bolte, P. Redont, A. Soubeyran, Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kerdyka-Łojasiewicz inequality, Math. Oper. Res., 35 (2010), 438–457. https://doi.org/10.1287/moor.1100.0449 doi: 10.1287/moor.1100.0449
|
| [2] |
S. Burer, R. D. C. Monteiro, A nonlinear programming algorithm for solving semidefinite programs with low-rank factorization, Math. Program., 95 (2003), 329–357. https://doi.org/10.1007/s10107-002-0352-8 doi: 10.1007/s10107-002-0352-8
|
| [3] |
E. J. Candès, B. Recht, Exact matrix completion via convex optimization, Found. Comput. Math., 9 (2009), 717–772. https://doi.org/10.1007/s10208-009-9045-5 doi: 10.1007/s10208-009-9045-5
|
| [4] |
X. Chen, L. Wang, J. Qu, N.-N. Guan, J.-Q. Li, Predicting miRNA-disease association based on inductive matrix completion, Bioinformatics, 34 (2018), 4256–4265. https://doi.org/10.1093/bioinformatics/bty503 doi: 10.1093/bioinformatics/bty503
|
| [5] | K.-Y. Chiang, I. S. Dhillon, C.-J. Hsieh, Using side information to reliably learn low-rank matrices from missing and corrupted observations, J. Mach. Learn. Res., 19 (2018), 1–35. |
| [6] | J. Hannon, M. Bennett, B. Smyth, Recommending twitter users to follow using content and collaborative filtering approaches, In: RecSys '10: Proceedings of the fourth ACM conference on Recommender systems, 2010,199–206. https://doi.org/10.1145/1864708.1864746 |
| [7] | K. A. Johnson, J. A. Becker, The whole brain atlas, In: neural information processing systems, 26 2013. Accessed on: July, 2019. https://www.med.harvard.edu/aanlib/home.html. |
| [8] |
Y. Koren, R. Bell, C. Volinsky, Matrix factorization techniques for recommender systems, Computer, 42 (2009), 30–37. https://doi.org/10.1109/MC.2009.263 doi: 10.1109/MC.2009.263
|
| [9] |
A. S. Lewis, H. S. Sendov, Nonsmooth analysis of singular values. Part Ⅱ: applications, Set-Valued Anal., 13 (2005), 243–264. https://doi.org/10.1007/s11228-004-7198-6 doi: 10.1007/s11228-004-7198-6
|
| [10] |
C. Q. Lu, M. Y. Yang, F. Luo, F. X. Wu, M. Li, Y. Pan, et al., Prediction of lncRNA-disease associations based on inductive matrix completion, Bioinformatics, 34 (2018), 3357–3364. https://doi.org/10.1093/bioinformatics/bty327 doi: 10.1093/bioinformatics/bty327
|
| [11] | A. K. Menon, C. Elkan, Link prediction via matrix factorization, In: Machine learning and knowledge discovery in databases, Berlin, Heidelberg: Springer, 2011,437–452. https://doi.org/10.1007/978-3-642-23783-6_28 |
| [12] |
N. Natarajan, I. S. Dhillon, Inductive matrix completion for predicting gene-disease associations, Bioinformatics, 30 (2014), i60–i68. https://doi.org/10.1093/bioinformatics/btu269 doi: 10.1093/bioinformatics/btu269
|
| [13] | I. Nazaro, B. Shirokik, M. Burkin, G. Fedoni, M. Pano, Sparse group inductive matrix completion, arXiv: 1804.10653, 2018. https://doi.org/10.48550/arXiv.1804.10653 |
| [14] | S. Negahban, M. J. Wainwright, Restricted strong convexity and weighted matrix completion: Optimal bounds with noise, J. Mach. Learn. Res., 13 (2012), 1665–1697. |
| [15] | J. Nocedal, S. J. Wright, Numerical optimization, 2 Eds., New York: Springer, 2006. https://doi.org/10.1007/978-0-387-40065-5 |
| [16] | R. T. Rockafellar, R. J.-B. Wets, Variational analysis, 1 Eds., Berlin: Springer, 1998. http://doi.org/10.1007/978-3-642-02431-3 |
| [17] |
T. Tao, S. H. Pan, S. J. Bi, Error bound of critical points and KL property of exponent $1/2$ for squared F-norm regularized factorization, J. Glob. Optim., 81 (2021), 991–1017. https://doi.org/10.1007/s10898-021-01077-0 doi: 10.1007/s10898-021-01077-0
|
| [18] |
T. Tao, Y. T. Qian, S. H. Pan, Column $\ell_{2, 0}$-norm regularized factorization model of low-rank matrix recovery and its computation, SIAM J. Optim., 32 (2022), 959–988. https://doi.org/10.1137/20M136205X doi: 10.1137/20M136205X
|
| [19] |
T. Tao, Y. T. Qian, S. H. Pan, Convergence of the majorized PAM method with subspace correction for low-rank composite factorization model, Comput. Optim. Appl., 91 (2025), 1–37. https://doi.org/10.1007/s10589-025-00708-6 doi: 10.1007/s10589-025-00708-6
|
| [20] | M. Xu, R. Jin, Z. H. Zhou, Speedup matrix completion with side information: application to multi-label learning, In: NIPS'13: Proceedings of the 27th international conference on neural information processing systems, 2(2013), 2301–2309. |
| [21] |
K. F. Yi, H. W. Hu, Y. Yu, W. Hao, Regularized matrix completion with partial side information, Neurocomputing, 383 (2020), 151–164. https://doi.org/10.1016/j.neucom.2019.12.021 doi: 10.1016/j.neucom.2019.12.021
|
| [22] | X. Zhang, S. S. Du, Q. Q. Gu, Fast and sample efficient inductive matrix completion via multi-phase procrustes flow, In: Proceedings of the 35th international conference on machine learning, 10–15 July 2018, Stockholmsmässan, Stockholm, Sweden, 5756–5765. |
| [23] |
Z. H. Zhu, Q. W. Li, G. G. Tang, M. B. Wakin, The global optimization geometry in low-rank matrix optimization, IEEE Trans. Inform. Theory, 67 (2021), 1308–1331. https://doi.org/10.1109/TIT.2021.3049171 doi: 10.1109/TIT.2021.3049171
|
| [24] | P. Zilber, B. Nadler, Inductive matrix completion: no bad local minima and a fast algorithm, In: Proceedings of the 39th international conference on machine learning, 17–23 July 2022, Baltimore, Maryland, USA, 27671–27692. |
Figures(3) / Tables(4)
Ting Tao, Lianghai Xiao, Zetian Chen, Xijie Lin. Column $ \ell_{2, 0} $-norm regularized factorization model for inductive matrix completion[J]. AIMS Mathematics, 2025, 10(8): 17602-17622. doi: 10.3934/math.2025786
DownLoad: