×
Zhang, Jie; Yang, Xinmin

Smoothing fast proximal gradient algorithm for the relaxation of matrix rank regularization problem. (English) Zbl 1527.90165

Appl. Numer. Math. 190, 303-320 (2023).
Summary: This paper proposes a general inertial smoothing proximal gradient algorithm for solving the Capped-\(\ell_1\) exact continuous relaxation regularization model proposed by Q. Yu and X. Zhang [Comput. Optim. Appl. 81, No. 2, 519–538 (2022; Zbl 1490.65083)]. The proposed algorithm incorporates different extrapolations into the gradient and proximal steps. It is proved that, under some general parameter constraints, the singular values of any accumulation point of the sequence generated by the proposed algorithm have the common support set, and the zero singular values can be achieved in a finite number of iterations. Furthermore, any accumulation point is a lifted stationary point of the relaxation model. Numerical experiments illustrate the efficiency of the proposed algorithm on synthetic and real data, respectively.

MSC:

90C25 Convex programming
49J52 Nonsmooth analysis
65K10 Numerical optimization and variational techniques

Keywords:

convex nonsmooth loss function; matrix rank regularization problem; smoothing approximation; inertial proximal gradient algorithm

Citations:

Zbl 1490.65083

Software:

iPiano
Cite Review PDF
Full Text: DOI

References:

[1] Argyriou, A.; Evgeniou, T.; Pontil, M., Convex multi-task feature learning, Mach. Learn., 73, 243-272 (2008) · Zbl 1470.68073
[2] Beck, A.; Teboulle, M., A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2, 1, 183-202 (2009) · Zbl 1175.94009
[3] Bian, W., Smoothing accelerated algorithm for constrained nonsmooth convex optimization problems, Sci. Sin., Math., 50, 1651-1666 (2020), (in Chinese) · Zbl 1499.90151
[4] Bian, W.; Chen, X., A smoothing proximal gradient algorithm for nonsmooth convex regression with cardinality penalty, SIAM J. Numer. Anal., 58, 1, 858-883 (2020)
[5] Cai, J.; Candes, E.; Shen, Z., A singular value thresholding algorithm for matrix completion, SIAM J. Optim., 20, 4, 1956-1982 (2008) · Zbl 1201.90155
[6] Chen, X., Smoothing methods for nonsmooth, nonconvex minimization, Math. Program., 134, 71-99 (2012) · Zbl 1266.90145
[7] Fan, J.; Li, R., Variable selection via nonconcave penalized likelihood and its oracle properties, J. Am. Stat. Assoc., 96, 456, 1348-1360 (2001) · Zbl 1073.62547
[8] Ge, Z.; Zhang, X.; Wu, Z., A fast proximal iteratively reweighted nuclear norm algorithm for nonconvex low-rank matrix minimization problems, Appl. Numer. Math., 179, 66-86 (2022) · Zbl 1492.65109
[9] He, Y.; Wang, F.; Li, Y.; Qin, J.; Chen, B., Robust matrix completion via maximum correntropy criterion and half-quadratic optimization, IEEE Trans. Signal Process., 68, 181-195 (2020) · Zbl 1543.15022
[10] Ji, S.; Ye, J., An accelerated gradient method for trace norm minimization, (Proceedings of the 26th Annual International Conference on Machine Learning (2009)), 457-464
[11] Kulis, B.; Sustik, M. A.; Dhillon, I. S., Low-rank Kernel learning with Bregman matrix divergences, J. Mach. Learn. Res., 10, 2 (2009) · Zbl 1235.68166
[12] Lai, M.; Xu, Y.; Yin, W., Improved iteratively reweighted least squares for unconstrained smoothed \(\ell_q\) minimization, SIAM J. Numer. Anal., 51, 2, 927-957 (2013) · Zbl 1268.49038
[13] Lewis, A. S.; Sendov, H. S., Nonsmooth analysis of singular values. Part II: applications, Set-Valued Anal., 13, 243-264 (2005) · Zbl 1129.49026
[14] Lu, C.; Tang, J.; Yan, S.; Lin, Z., Generalized nonconvex nonsmooth low-rank minimization, (Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (2014)), 4130-4137
[15] Lu, Z.; Zhang, Y.; Lu, J., \( \ell_p\) regularized low-rank approximation via iterative reweighted singular value minimization, Comput. Optim. Appl., 68, 3, 619-642 (2017) · Zbl 1388.90096
[16] Ma, S.; Goldfarb, D.; Chen, L., Fixed point and Bregman iterative methods for matrix rank minimization, Math. Program., 128, 1-2, 321-353 (2011) · Zbl 1221.65146
[17] Nesterov, Y., Introductory Lectures on Convex Programming (2004), Kluwer Academic Publisher: Kluwer Academic Publisher Dordrecht · Zbl 1086.90045
[18] Ochs, P.; Chen, Y.; Brox, T.; Pock iPiano, T., Inertial proximal algorithm for nonconvex optimization, SIAM J. Imaging Sci., 7, 2, 1388-1419 (2014) · Zbl 1296.90094
[19] Parikh, N.; Boyd, S., Proximal algorithms, Found. Trends Mach. Learn., 1, 3, 127-239 (2014)
[20] Polyak, B. T., Some methods of speeding up the convergence of iteration methods, USSR Comput. Math. Math., 4, 5, 1-17 (1964) · Zbl 0147.35301
[21] Recht, B.; Fazel, M.; Parrilo, P., Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 3, 471-501 (2010) · Zbl 1198.90321
[22] Stewart, G. W., Perturbation theory for the singular value decomposition (1998)
[23] Teboulle, M., A simplified view of first order methods for optimization, Math. Program., 170, 1, 67-96 (2018) · Zbl 1391.90482
[24] Toh, K. C.; Yun, S., An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems, Pac. J. Optim., 6, 615-640, 615-640 (2010) · Zbl 1205.90218
[25] Wu, F.; Bian, W.; Xue, X., Smoothing fast iterative hard thresholding algorithm for \(\ell_0\) regularized nonsmooth convex regression problem (2021)
[26] Wu, Z.; Li, M., General inertial proximal gradient method for a class of nonconvex nonsmooth optimization problems, Comput. Optim. Appl., 73, 129-158 (2019) · Zbl 1420.90054
[27] Wu, Z.; Li, C.; Li, M.; Lim, A., Inertial proximal gradient methods with Bregman regularization for a class of nonconvex optimization problems, J. Glob. Optim., 79, 617-644 (2021) · Zbl 1466.90081
[28] Xu, H.; Caramanis, C.; Sanghavi, S., Robust PCA via outlier pursuit, IEEE Trans. Inf. Theory, 58, 3047-3064 (2012) · Zbl 1365.62228
[29] Yu, Q.; Zhang, X., A smoothing proximal gradient algorithm for matrix rank minimization problem, Comput. Optim. Appl., 1, 20 (2022) · Zbl 1490.65083
[30] Zhang, C.; Chen, X., Smoothing projected gradient method and its application to stochastic linear complementarity problems, SIAM J. Optim., 20, 2, 627-649 (2009) · Zbl 1204.65073
[31] Zhang, J.; Yang, X.; Li, G.; Zhang, K., A smoothing proximal gradient algorithm with extrapolation for the relaxation of \(\ell_0\) regularization problem, Comput. Optim. Appl., 1, 24 (2023) · Zbl 1516.90103
[32] Zhao, Q.; Meng, D.; Xu, Z.; Yan, Y., \( L_1\)-norm low-rank matrix factorization by variational Bayesian method, IEEE Trans. Neural Netw. Learn., 26, 4, 825-839 (2015)
[33] Zheng, Y.; Liu, G.; Sugimoto, S.; Yan, S.; Okutomi, M., Practical low-rank matrix approximation under robust L1-norm, (2012 IEEE Conference on Computer Vision and Pattern Recognition (2012)), 1410-1417
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.