Modified nonmonotonic projection Barzilai-Borwein gradient method for nonnegative matrix factorization

Xiaoping Xu; Jinxuan Liu; Wenbo Li; Yuhan Xu; Fuxiao Li; Xiaoping Xu; Jinxuan Liu; Wenbo Li; Yuhan Xu; Fuxiao Li

doi:10.3934/math.20241073

AIMS Mathematics

2024, Volume 9, Issue 8: 22067-22090. doi: 10.3934/math.20241073

Previous Article Next Article

Research article

Modified nonmonotonic projection Barzilai-Borwein gradient method for nonnegative matrix factorization

1.
School of Sciences, Xi'an University of Technology, Xi'an 710054, China
2.
School of Electrical and Control Engineering, Shaanxi University of Science and Technology, Xi'an 710021, China

Received: 24 November 2023 Revised: 09 April 2024 Accepted: 23 April 2024 Published: 15 July 2024
MSC : 15A23, 65F30

In this paper, an active set recognition technique is suggested, and then a modified nonmonotonic line search rule is presented to enhance the efficiency of the nonmonotonic line search rule, in which we introduce a new parameter formula to attempt to control the nonmonotonic degree of the line search, and thus improve the chance of discovering the global minimum. By using a modified linear search and an active set recognition technique, a global convergence gradient solution for nonnegative matrix factorization (NMF) based on an alternating nonnegative least squares framework is proposed. We used a Barzilai-Borwein step size and greater step-size tactics to speed up the convergence. Finally, a large number of numerical experiments were carried out on synthetic and image datasets, and the results showed that our presented method was effective in calculating the speed and solution quality.
- active set,
- projected Barzilai-Borwein method,
- nonmonotonic line search,
- alternating nonnegative least squares,
- greater step size
Citation: Xiaoping Xu, Jinxuan Liu, Wenbo Li, Yuhan Xu, Fuxiao Li. Modified nonmonotonic projection Barzilai-Borwein gradient method for nonnegative matrix factorization[J]. AIMS Mathematics, 2024, 9(8): 22067-22090. doi: 10.3934/math.20241073

Related Papers:

Abstract

In this paper, an active set recognition technique is suggested, and then a modified nonmonotonic line search rule is presented to enhance the efficiency of the nonmonotonic line search rule, in which we introduce a new parameter formula to attempt to control the nonmonotonic degree of the line search, and thus improve the chance of discovering the global minimum. By using a modified linear search and an active set recognition technique, a global convergence gradient solution for nonnegative matrix factorization (NMF) based on an alternating nonnegative least squares framework is proposed. We used a Barzilai-Borwein step size and greater step-size tactics to speed up the convergence. Finally, a large number of numerical experiments were carried out on synthetic and image datasets, and the results showed that our presented method was effective in calculating the speed and solution quality.

References

[1]	M. Ahookhosh, K. Amini, S. Bahrami, A class of nonmonotone Armijo-type line search method for unconstrained optimization, Optimization, 61 (2012), 387–404. https://doi.org/10.1080/02331934.2011.641126 doi: 10.1080/02331934.2011.641126
[2]	E. G. Birgin, J. M. Mart$\acute{I}$nez, M. Raydan, Nonmonotone spectral projected gradient methods on convex sets, SIAM J. Optimiz., 10 (2000), 1196–1211. https://doi.org/10.1137/S1052623497330963 doi: 10.1137/S1052623497330963
[3]	J. Barzilai, J. M. Borwein, Two-point step size gradient methods, IMA J. Numer. Anal., 8 (1988), 141–148. https://doi.org/10.1093/imanum/8.1.141 doi: 10.1093/imanum/8.1.141
[4]	S. Bonettini, Inexact block coordinate descent methods with application to non-negative matrix factorization, IMA J. Numer. Anal., 31 (2011), 1431–1452. https://doi.org/10.1093/imanum/drq024 doi: 10.1093/imanum/drq024
[5]	A. Cichocki, R. Zdunek, S. Amari, Hierarchical ALS algorithms for nonnegative matrix and 3D tensor factorization, In: Independent Component Analysis and Signal Separation, Heidelberg: Springer, 2007,169–176. https://doi.org/10.1007/978-3-540-74494-8_22
[6]	A. Cristofari, M. D. Santis, S. Lucidi, F. Rinaldi, A two-stage active-set algorithm for bound-constrained optimization, J. Optim. Theory Appl., 172 (2017), 369–401. https://doi.org/10.1007/s10957-016-1024-9 doi: 10.1007/s10957-016-1024-9
[7]	Y. H. Dai, On the nonmonotone line search, J. Optim. Theory Appl., 112 (2002), 315–330. https://doi.org/10.1023/A:1013653923062 doi: 10.1023/A:1013653923062
[8]	Y. H. Dai, L. Z. Liao, R-Linear convergence of the Barzilai-Borwein gradient method, IMA J. Numer. Anal., 22 (2002), 1–10. https://doi.org/10.1093/imanum/22.1.1 doi: 10.1093/imanum/22.1.1
[9]	P. Deng, T. R. Li, H. J. Wang, D. X. Wang, S. J. Horng, R. Liu, Graph regularized sparse non-negative matrix factorization for clustering, IEEE Transactions on Computational Social Systems, 10 (2023), 910–921. https://doi.org/10.1109/TCSS.2022.3154030 doi: 10.1109/TCSS.2022.3154030
[10]	P. Deng, F. Zhang, T. R. Li, H. J. Wang, S. J. Horng, Biased unconstrained non-negative matrix factorization for clustering, Knowl.-Based Syst., 239 (2022), 108040. https://doi.org/10.1016/j.knosys.2021.108040 doi: 10.1016/j.knosys.2021.108040
[11]	N. Gillis, The why and how of nonnegative matrix factorization, 2014, arXiv: 1401.5226. https://doi.org/10.48550/arXiv.1401.5226
[12]	R. Glowinski, Numerical methods for nonlinear variational problems, Heidelberg: Springer, 1984. https://doi.org/10.1007/978-3-662-12613-4
[13]	P. H. Gong, C. S. Zhang, Efficient nonnegative matrix factorization via projected Newton method, Pattern Recogn., 45 (2012), 3557–3565. https://doi.org/10.1016/j.patcog.2012.02.037 doi: 10.1016/j.patcog.2012.02.037
[14]	N. Z. Gu, J. T. Mo Incorporating nonmonotone strategies into the trust region method for unconstrained optimization, Comput. Math. Appl., 55 (2008), 2158–2172. https://doi.org/10.1016/j.camwa.2007.08.038
[15]	N. Y. Guan, D. C. Tao, Z. G. Luo, B. Yuan NeNMF: An optimal gradient method for nonnegative matrix factorization, IEEE T. Signal Proces., 60 (2012), 2882–2898. https://doi.org/10.1109/TSP.2012.2190406
[16]	L. X. Han, M. Neumann, U. Prasad, Alternating projected Barzilai-Borwein methods for nonnegative matrix factorization, Electronic Transactions on Numerical Analysis, 36 (2009), 54–82. https://doi.org/10.1007/978-0-8176-4751-3_16 doi: 10.1007/978-0-8176-4751-3_16
[17]	G. Hu, B. Du, X. F. Wang, G. Wei, An enhanced black widow optimization algorithm for feature selection, Knowl.-Based Syst., 235 (2022), 107638. https://doi.org/10.1016/j.knosys.2021.107638 doi: 10.1016/j.knosys.2021.107638
[18]	G. Hu, J. Y. Zhong, G. Wei, SaCHBA_PDN: Modified honey badger algorithm with multi-strategy for UAV path planning, Expert Syst. Appl., 223 (2023), 119941. https://doi.org/10.1016/j.eswa.2023.119941 doi: 10.1016/j.eswa.2023.119941
[19]	G. Hu, J. Y. Zhong, G. Wei, C. T. Chang, DTCSMO: An efficient hybrid starling murmuration optimizer for engineering applications, Comput. Method. Appl. M., 405 (2023), 115878. https://doi.org/10.1016/j.cma.2023.115878 doi: 10.1016/j.cma.2023.115878
[20]	G. Hu, J. Wang, M. Li, A. G. Hussien, M. Abbas, EJS: Multi-strategy enhanced jellyfish search algorithm for engineering applications, Mathematics, 11 (2023), 851. https://doi.org/10.3390/math11040851 doi: 10.3390/math11040851
[21]	G. Hu, R. Yang, X. Q. Qin, G. Wei, MCSA: Multi-strategy boosted chameleon-inspired optimization algorithm for engineering applications, Comput. Method. Appl. M., 403 (2022), 115676. https://doi.org/10.1016/j.cma.2022.115676 doi: 10.1016/j.cma.2022.115676
[22]	G. Hu, X. N. Zhu, G. Wei, C. Chang, An marine predators algorithm for shape optimization of developable Ball surfaces, Eng. Appl. Artif. Intel., 105 (2021), 104417. https://doi.org/10.1016/j.engappai.2021.104417 doi: 10.1016/j.engappai.2021.104417
[23]	Y. K. Huang, H. W. Liu, S. S. Zhou, Quadratic regularization projected alternating Barzilai-Borwein method for nonnegative matrix factorization, Data Min. Knowl. Disc., 29 (2015), 1665–1684. https://doi.org/10.1007/s10618-014-0390-x doi: 10.1007/s10618-014-0390-x
[24]	Y. K. Huang, H. W. Liu, S. Zhou, An efficint monotone projected Barzilai-Borwein method for nonnegative matrix factorization, Appl. Math. Lett., 45 (2015), 12–17. https://doi.org/10.1016/j.aml.2015.01.003 doi: 10.1016/j.aml.2015.01.003
[25]	D. D. Lee, H. S. Seung, Learning the parts of objects by non-negative matrix factorization, Nature, 401 (1999), 788–791. https://doi.org/10.1038/44565 doi: 10.1038/44565
[26]	D. D. Lee, H. S. Seung, Algorithms for non-negative matrix factorization, Advances in Neural Processing Information Systems, 13 (2001), 556–562.
[27]	X. L. Li, H. W. Liu, X. Y. Zheng, Non-monotone projection gradient method for non-negative matrix factorization, Comput. Optim. Appl., 51 (2012), 1163–1171. https://doi.org/10.1007/s10589-010-9387-6 doi: 10.1007/s10589-010-9387-6
[28]	H. W. Liu, X. L. Li, Modified subspace Barzilai-Borwein gradient method for non-negative matrix factorization, Comput. Optim. Appl., 55 (2013), 173–196. https://doi.org/10.1007/s10589-012-9507-6 doi: 10.1007/s10589-012-9507-6
[29]	C. J. Lin, Projected gradient methods for non-negative matrix factorization, Neural Comput., 19 (2007), 2756–2779. https://doi.org/10.1162/neco.2007.19.10.2756 doi: 10.1162/neco.2007.19.10.2756
[30]	H. Nosratipour, A. H. Borzabadi, O. S. Fard, On the nonmonotonicity degree of nonmonotone line searches, Calcolo, 54 (2017), 1217–1242. https://doi.org/10.1007/s10092-017-0226-3 doi: 10.1007/s10092-017-0226-3
[31]	D. Kim, S. Sra, I. S. Dhillon, Fast Newton-type methods for the least squares nonnegative matrix approximation problem, SIAM International Conference on Data Mining, 1 (2007), 343–354. https://doi.org/10.1137/1.9781611972771.31 doi: 10.1137/1.9781611972771.31
[32]	P. Paatero, U. Tapper, Positive matrix factorization: A non-negative factor model with optimal utilization of error estimates of data values, Environmetrics, 5 (1994), 111–126. https://doi.org/10.1002/env.3170050203 doi: 10.1002/env.3170050203
[33]	M. Raydan, On the Barzilai-Borwein choice of steplength for the gradient method, IMA J. Numer. Anal., 13 (1993), 321–326. https://doi.org/10.1093/imanum/13.3.321 doi: 10.1093/imanum/13.3.321
[34]	M. Raydan, The Barzilai and Borwein gradient method for the large-scale unconstrained minimization problem, SIAM J. Optimiz., 7 (1997), 26–33. https://doi.org/10.1137/S1052623494266365 doi: 10.1137/S1052623494266365
[35]	D. X. Wang, T. R. Li, P. Deng, J. Liu, W. Huang, F. Zhang, A generalized deep learning algorithm based on NMF for multi-view clustering, IEEE T. Big Data, 9 (2023), 328–340. https://doi.org/10.1109/TBDATA.2022.3163584 doi: 10.1109/TBDATA.2022.3163584
[36]	D. X. Wang, T. R. Li, P. Deng, F. Zhang, W. Huang, P. F. Zhang, et al., A generalized deep learning clustering algorithm based on non-negative matrix factorization, ACM T. Knowl. Discov. D., 17 (2023), 1–20. https://doi.org/10.1145/3584862 doi: 10.1145/3584862
[37]	D. X. Wang, T. R. Li, W. Huang, Z. P. Luo, P. Deng, P. F. Zhang, et al., A multi-view clustering algorithm based on deep semi-NMF, Inform. Fusion, 99 (2023), 101884. https://doi.org/10.1016/j.inffus.2023.101884 doi: 10.1016/j.inffus.2023.101884
[38]	Z. J. Wang, Z. S. Chen, L. Xiao, Q. Su, K. Govindan, M. J. Skibniewski, Blockchain adoption in sustainable supply chains for Industry 5.0: A multistakeholder perspective, J. Innov. Knowl., 8 (2023), 100425. https://doi.org/10.1016/j.jik.2023.100425 doi: 10.1016/j.jik.2023.100425
[39]	Z. J. Wang, Z. S. Chen, S. Qin, K. S. Chin, P. Witold, M. J. Skibniewski, Enhancing the sustainability and robustness of critical material supply in electrical vehicle market: An AI-powered supplier selection approach, Ann. Oper. Res., 2023 (2023), 102690. https://doi.org/10.1007/s10479-023-05698-4 doi: 10.1007/s10479-023-05698-4
[40]	Z. J. Wang, Y. Y. Sun, Z. S. Chen, G. Z. Feng, Q. Su, Optimal versioning strategy of enterprise software considering the customer cost-acceptance level, Kybernetes, 52 (2023), 997–1026. https://doi.org/10.1108/K-04-2021-0339 doi: 10.1108/K-04-2021-0339
[41]	Z. J. Wang, Y. Y. Sun, Q. Su, M. Deveci, K. Govindan, M. J. Skibniewski, et al., Smart contract application in resisting extreme weather risks for the prefabricated construction supply chain: prototype exploration and assessment, Group Decis. Negot., (2024). https://doi.org/10.1007/s10726-024-09877-x
[42]	Y. H. Xiao, Q. J. Hu, Subspace Barzilai-Borwein gradient method for large-scale bound constrained optimization, Appl. Math. Optim., 58 (2008), 275–290. https://doi.org/10.1007/s00245-008-9038-9 doi: 10.1007/s00245-008-9038-9
[43]	Y. H. Xiao, Q. J. Hu, Z. X. Wei, Modified active set projected spectral gradient method for bound constrained optimization, Appl. Math. Model., 35 (2011), 3117–3127. https://doi.org/10.1016/j.apm.2010.09.011 doi: 10.1016/j.apm.2010.09.011
[44]	Y. Y. Xu, W. T. Yin, A block coordinate descent method for regularized multi-convex optimization with applications to nonnegative tensor factorization and completion, SIAM J. Imaging Sci., 6 (2013), 1758–1789. https://doi.org/10.1137/120887795 doi: 10.1137/120887795
[45]	H. C. Zhang, W. W. Hager, A nonmonotone line search technique and its application to unconstrained optimization, SIAM J. Optimiz., 14 (2004), 1043–1056. https://doi.org/10.1137/S1052623403428208 doi: 10.1137/S1052623403428208
[46]	R. Zdunek, A. Cichocki, Fast nonnegative matrix factorization algorithms using projected gradient approaches for large-scale problems, Comput. Intel. Neurosc., 2008 (2008), 939567. https://doi.org/10.1155/2008/939567 doi: 10.1155/2008/939567

Reader Comments

Your name:*

Email:*
© 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)