A novel nonconvex penalty method for a rank constrained matrix optimization problem and its applications

• Autorzy: Zhang Wenjuan , Yao Jiayi , Xiao Feng , Wang Yuping , Wu Yulian

Identyfikatory

DOI

10.61822/amcs-2025-0012

• Języki publikacji: EN

Abstrakty

EN

The rank constrained nonconvex nonsmooth matrix optimization problem is an important and challenging issue. To solve it, we first design a penalty model in which the penalty term can be expressed as a sum of specific functions defined on smallest singular values of the matrix in question. We prove that the global minimizers of this penalty model are the same as those of the original problem. Second, we propose a flexible factorization format for the penalty function, such that the model enjoys the merit of fast computation in a SVD-free manner. We further prove that the factorization format problem is equivalent to the penalty one. A Bregman proximal gradient (BPG) method is developed for optimizing the factorization model. Third, we use two application problems as examples to illustrate that the problem considered has a wide application. Finally, some numerical experiments are conducted, and their results indicates the effectiveness of the proposed method.

Słowa kluczowe

EN

low rank; penalty method; nonconvex optimization; nonsmooth optimization; Bregman proximal gradient

PL

optymalizacja niewypukła; optymalizacja niegładka; gradient Bregmana

• Wydawca: Oficyna Wydawnicza Uniwersytetu Zielonogórskiego
• Czasopismo: International Journal of Applied Mathematics and Computer Science
• Rocznik: 2025
• Tom: Vol. 35, no. 1
• Strony: 157--177
• Opis fizyczny: Bibliogr. 37 poz., rys., tab.

Twórcy

autor

Zhang Wenjuan

• School of Science, Xi’an Technological University, Xi’an, Shaanxi, 710021, China

autor

Yao Jiayi

• School of Science, Xi’an Technological University, Xi’an, Shaanxi, 710021, China

autor

Xiao Feng

• School of Computer Science, Xi’an Technological University, Xi’an, Shaanxi, 710021, China

autor

Wang Yuping

• School of Science, Xi’an Technological University, Xi’an, Shaanxi, 710021, China

autor

Wu Yulian

• Department of Health Management, Xi’an Medical University, Xi’an, Shaanxi, 710021, China

Bibliografia

• [1] Alain, R. (2013). Direct optimization of the dictionary learning problem, IEEE Transactions on Signal Processing 61(22): 5495-5506.
• [2] Atwood, C.L. (1969). Optimal and efficient designs of experiments, The Annals of Mathematical Statistics 40(5): 1570-1602.
• [3] Bauschke, H.H., Bolte, J. and Teboulle, M. (2016). A descent lemma beyond Lipschitz gradient continuity: First order methods revisited and applications, Mathematics of Operations Research 42(2): 330-348.
• [4] Bauschke, H.H. and Borwein, J.M. (1997). Legendre functions and the method of Bregman projections, Journal of Convex Analysis 4(1): 27-67.
• [5] Beck, A. and Eldar, Y. (2012). Sparsity constrained nonlinear optimization: Optimality conditions and algorithms, SIAM Journal on Optimization 23: 1480-1509.
• [6] Bertero, M., Boccacci, P., Desidera, G. and Vicidomini, G. (2009). Image deblurring with poisson data: From cells to galaxies, Inverse Problems 25(12): 123006.
• [7] Bhatia, R. (2011). Matrix Analysis, World Books Publishing Corporation, Beijing.
• [8] Bolte, J., Sabach, S. and M.Teboulle (2014). Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Mathematical Programming 146(1): 459-494.
• [9] Bolte, J., Sabach, S. and M. Teboulle (2018). First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems, SIAM Journal on Optimization 28(3): 2131-2151.
• [10] Candes, E.J., Wakin, M.B. and Boyd., S.P. (2008). Enhancing sparsity by reweighted ℓ1 minimization, Journal of Fourier Analysis and Applications 14(5): 877-905.
• [11] Censor, Y. and Zenios, S.A. (1992). Proximal minimization algorithm with d-functions, Journal of Optimization Theory and Applications 73(3): 451-464.
• [12] Chartrand, R. (2007). Exact reconstruction of sparse signals via nonconvex minimization, IEEE Signal Processing Letters 14(10): 707-710.
• [13] Chen, G. and Teboulle, M. (1993). Convergence analysis of a proximal-like minimization algorithm using Bregman functions, SIAM Journal on Optimization 3(3): 538-543.
• [14] Eckstein, J. (1993). Nonlinear proximal point algorithms using Bregman functions, with applications to convex programming, Mathematics of Operations Research 18(1): 202-226.
• [15] Fan, J. and Li, R. (2001). Variable selection via nonconcave penalized likelihood and its oracle properties, Journal of the American Statistical Association 96(456): 1348-1361.
• [16] Fazel, M., Hindi, H. and Boyd, S.P. (2003). Log-det heuristic for matrix rank minimization with applications to Hankel and Euclidean distance matrices, Proceedings of the 2003 American Control Conference, Denver, USA, pp. 2156-2162.
• [17] Gao, Y. and Sun, D. (2010). A majorized penalty approach for calibrating rank constrained correlation matrix problems, 2010 IEEE International Conference on Computing, Guiyang, Guizhou, China.
• [18] Horn, R.A. and Johnson, C.R. (1990). Matrix Analysis, Cambridge University Press, Cambridge.
• [19] Ji, S., Sze, K.-F., Zhou, Z., So, A. M.-C. and Ye, Y. (2013). Beyond convex relaxation: A polynomial-time non-convex optimization approach to network localization, 2013 Proceedings IEEE INFOCOM, Turin, Italy, pp. 2499-2507, DOI: 10.1109/INFCOM.2013.6567056.
• [20] Jia, X., Feng, X. and Wang, W. (2020). Generalized unitarily invariant gauge regularization for fast low-rank matrix recovery, IEEE Transactions on Neural Networks and Learning Systems 32(4): 1627-1641.
• [21] Li, J.-R. and White, J. (2001). Reduction of large circuit models via low rank approximate gramians, International Journal of Applied Mathematics and Computer Science 11(5): 1151-1171.
• [22] Liang, Z., Zeng, D. and Guo, S. (2022). A fusion representation for face learning by low-rank constrain and high-frequency texture components, Pattern Recognition Letters 155: 48-53, DOI:10.1016/j.patrec.2022.01.022.
• [23] Liu, T., Lu, Z. and Chen, X. (2020). An exact penalty method for semidefinite-box-constrained low-rank matrix optimization problems, IMA Journal of Numerical Analysis 40(1): 563-586.
• [24] Lu, Y., Zhang, L. and Wu, J. (2015a). A smoothing majorization method for matrix minimization, Optimization Methods and Software 30(1): 682-705.
• [25] Lu, Z., Zhang, Y. and Li, X. (2015b). Penalty decomposition methods for rank minimization, Optimization Methods and Software 30(3): 531-558.
• [26] Lu, Z., Zhang, Y. and Lu, J. (2017). ℓp Regularized low-rank approximation via iterative reweighted singular value minimization, Computational Optimization and Applications 68(3): 619-642.
• [27] Luke, D.R. (2017). Phase retrieval. What’s new?, SIAG/OPT Views and News 25(1): 1-5.
• [28] Nguyen, Q.V. (2017). Forward-backward splitting with Bregman distances, Vietnam Journal of Mathematics 45(3): 519-539.
• [29] Recht, B., Fazel, M. and Parrilo, P.A. (2010). Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Review 52(3): 471-501.
• [30] Recht, B., Xu, W. and Hassibi, B. (2011). Null space conditions and thresholds for rank minimization, Mathematical Programming 127: 175-202.
• [31] Sulaiman, I.M., Kaelo, P., Khalid, R. and Nawawi, M.K.M. (2024). A descent generalized RMIL spectral gradient algorithm for optimization problems, International Journal of Applied Mathematics and Computer Science 34(2): 225-233, DOI: 10.61822/amcs-2024-0016.
• [32] Teboulle, M. (1992). Entropic proximal mappings with application to nonlinear programming, Mathematics of Operations Research 17(3): 670-690.
• [33] Ülkü, I. and Kizgut, E. (2018). Large-scale hyperspectral image compression via sparse representations based on online learning, International Journal of Applied Mathematics and Computer Science 28(1): 197-207, DOI: 10.2478/amcs-2018-0015.
• [34] Wang, S., Xiao, S. and Zhu, W. (2022). Multi-view fuzzy clustering of deep random walk and sparse low-rank embedding, Information Sciences 586: 224-238.
• [35] Xu, Z., Chang, X., Xu, F. and Zhang, H. (2012). L1/2 regularization: A thresholding representation theory and a fast solver, IEEE Transactions on Neural Networks and Learning Systems 586(7): 1013-1027.
• [36] Yang, S., Tan, Y., Dong, R. and Tan, Q. (2023). Nonsmooth optimization control based on a sandwich model with hysteresis for piezo-positioning systems, International Journal of Applied Mathematics and Computer Science 33(3): 449-461, DOI: 10.34768/amcs-2023-0033.
• [37] Zhong, Y., Li, C., Li, Z. and Duan, X. (2022). A proximal based algorithm for piecewise sparse approximation with application to scattered data fitting, International Journal of Applied Mathematics and Computer Science 32(4): 671-682, DOI: 10.34768/amcs-2022-0046.

Uwagi

Opracowanie rekordu ze środków MNiSW, umowa nr POPUL/SP/0154/2024/02 w ramach programu "Społeczna odpowiedzialność nauki II" - moduł: Popularyzacja nauki (2025).