×

A fast proximal iteratively reweighted nuclear norm algorithm for nonconvex low-rank matrix minimization problems. (English) Zbl 1492.65109

Summary: In this paper, we propose a fast proximal iteratively reweighted nuclear norm algorithm with extrapolation for solving a class of nonconvex low-rank matrix minimization problems. The proposed method incorporates two different extrapolation steps with respect to the previous iterations into the backward proximal step and the forward gradient step of the classic proximal iteratively reweighted method. We prove that the proposed method generates a convergent subsequence under general parameter constraints, and that any limit point is a stationary point of the problem. Furthermore, we prove that if the objective function satisfies the Kurdyka-Łojasiewicz property, the algorithm is globally convergent to a stationary point of the considered problem. Finally, we perform numerical experiments on a practical matrix completion problem with both synthetic and real data, the results of which demonstrate the efficiency and superior performance of the proposed algorithm.

MSC:

65F55 Numerical methods for low-rank matrix approximation; matrix compression
65K05 Numerical mathematical programming methods
90C26 Nonconvex programming, global optimization

Software:

iPiano
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Attouch, H.; Bolte, J.; Redont, P.; Soubeyran, A., Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-Łojasiewicz inequality, Math. Oper. Res., 35, 2, 438-457 (2010) · Zbl 1214.65036
[2] Attouch, H.; Bolte, J.; Svaiter, B. F., Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods, Math. Program., 137, 1-2, 91-129 (2013) · Zbl 1260.49048
[3] 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
[4] Bolte, J.; Sabach, S.; Teboulle, M., Proximal alternating linearized minimization for nonconvex and nonsmooth problems, Math. Program., 146, 1-2, 459-494 (2014) · Zbl 1297.90125
[5] Bot, R. I.; Csetnek, E. R.; László, S. C., An inertial forward-backward algorithm for the minimization of the sum of two nonconvex functions, EURO J. Comput. Optim., 4, 1, 3-25 (2016) · Zbl 1338.90311
[6] Cabral, R.; Torre, F. D.L.; Costeira, J. P.; Bernardino, A., Unifying nuclear norm and bilinear factorization approaches for low-rank matrix decomposition, (ICCV, Proceedings (2013)), 2488-2495
[7] Candès, E. J.; Wakin, M. B.; Boyd, S. P., Enhancing sparsity by reweighted \(l_1\) minimization, J. Fourier Anal. Appl., 14, 5-6, 877-905 (2008) · Zbl 1176.94014
[8] Candès, E. J.; Recht, B., Exact matrix completion via convex optimization, Found. Comput. Math., 9, 6, 717-772 (2009) · Zbl 1219.90124
[9] Chen, K.; Dong, H. B.; Chan, K. S., Reduced rank regression via adaptive nuclear norm penalization, Biometrika, 100, 4, 901-920 (2013) · Zbl 1279.62115
[10] Fan, J. Q.; Li, R. Z., Variable selection via nonconcave penalized likelihood and its oracle properties, J. Am. Stat. Assoc., 96, 456, 1348-1360 (2001) · Zbl 1073.62547
[11] Fazel, M., Matrix rank minimization with applications (2002), Ph.D. Dissertation
[12] Frank, L. L.E.; Friedman, J. H., A statistical view of some chemometrics regression tools, Technometrics, 35, 2, 109-135 (1993) · Zbl 0775.62288
[13] Friedman, J. H., Fast sparse regression and classification, Int. J. Forecast., 28, 3, 722-738 (2012)
[14] Gao, C. X.; Wang, N. Y.; Yu, Q.; Zhang, Z. H., A feasible nonconvex relaxation approach to feature selection, (AAAI, Proceedings (2011)), 356-361
[15] Geman, D.; Yang, C. D., Nonlinear image recovery with half-quadratic regularization, IEEE Trans. Image Process., 4, 7, 932-946 (1995)
[16] Gu, S. H.; Zhang, L.; Zuo, W. M.; Feng, X. C., Weighted nuclear norm minimization with application to image denoising, (CVPR, Proceedings (2014)), 2862-2869
[17] Guo, K.; Han, D. R., A note on the Douglas-Rachford splitting method for optimization problems involving hypoconvex functions, J. Glob. Optim., 72, 431-441 (2018) · Zbl 1412.90107
[18] Horst, R.; Thoai, N. V., DC programming: overview, J. Optim. Theory Appl., 103, 1-43 (1999) · Zbl 1073.90537
[19] Kurdyka, K., On gradients of functions definable in o-minimal structures, Ann. Inst. Fourier, 48, 3, 769-783 (1998) · Zbl 0934.32009
[20] Lafond, J.; Klopp, O.; Moulines, E.; Salmon, J., Probabilistic low-rank matrix completion on finite alphabets, (NeurIPS, Proceedings (2014))
[21] Lewis, A. S.; Sendov, H. S., Nonsmooth analysis of singular values. Part I: theory, Set-Valued Anal., 13, 3, 213-241 (2005) · Zbl 1129.49025
[22] Li, H.; Lin, Z. C., Accelerated proximal gradient methods for nonconvex programing, (NeurIPS, Proceedings (2015)), 377-387
[23] Li, Y. F.; Zhang, Y. J.; Huang, Z. H., A reweighted nuclear norm minimization algorithm for low rank matrix recovery, J. Comput. Appl. Math., 263, 338-350 (2014) · Zbl 1301.65049
[24] Lu, C. Y.; Tang, J. H.; Yan, S. C.; Lin, Z. C., Generalized nonconvex nonsmooth low-rank minimization, (CVPR, Proceedings (2014)), 4130-4137
[25] Lu, C. Y.; Tang, J. H.; Yan, S. C.; Lin, Z. C., Nonconvex nonsmooth low rank minimization via iteratively reweighted nuclear norm, IEEE Trans. Image Process., 25, 2, 829-839 (2015) · Zbl 1408.94866
[26] Lu, Z. S.; Zhang, Y., Schatten-p quasi-norm regularized matrix optimization via iterative reweighted singular value minimization (2015)
[27] Merino, D. I., Topics in Matrix Analysis (1992), Johns Hopkins University Press: Johns Hopkins University Press Baltimore
[28] Nesterov, Y., A method of solving a convex programming problem with convergence rate \(O(1 / k^2)\), Sov. Math. Dokl., 27, 3, 372-376 (1983) · Zbl 0535.90071
[29] Nesterov, Y., Introductory Lectures on Convex Optimization: A Basic Course (2013), Springer: Springer New York
[30] Ochs, P.; Chen, Y.; Brox, T.; Pock, T., iPiano: inertial proximal algorithm for nonconvex optimization, SIAM J. Imaging Sci., 7, 2, 1388-1419 (2014) · Zbl 1296.90094
[31] Phan, D. N.; Nguyen, T. N., An accelerated IRNN-Iteratively Reweighted Nuclear Norm algorithm for nonconvex nonsmooth low-rank minimization problems, J. Comput. Appl. Math., 396, 6, Article 113602 pp. (2021) · Zbl 1469.90114
[32] Polyak, B. T., Some methods of speeding up the convergence of iteration methods, USSR Comput. Math. Math. Phys., 4, 5, 1-17 (1964) · Zbl 0147.35301
[33] Recht, B.; Fazel, M.; Parrilo, P. A., Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev., 52, 3, 471-501 (2010) · Zbl 1198.90321
[34] Rockafellar, R. T., Convex Analysis (1970), Princeton University Press: Princeton University Press Princeton · Zbl 0193.18401
[35] Shen, Y.; Liu, X., An alternating minimization method for matrix completion problems, Discrete Contin. Dyn. Syst., 13, 6, 1757-1772 (2020) · Zbl 1441.15020
[36] Sun, T.; Jiang, H.; Cheng, L. Z., Convergence of proximal iteratively reweighted nuclear norm algorithm for image processing, IEEE Trans. Image Process., 26, 12, 5632-5644 (2017) · Zbl 1409.94567
[37] Toh, K. C.; Yun, S. W., An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems, Pac. J. Optim., 6, 3, 615-640 (2010) · Zbl 1205.90218
[38] Trzasko, J.; Manduca, A., Highly undersampled magnetic resonance image reconstruction via homotopic \(\ell_0\)-minimization, IEEE Trans. Med. Imaging, 28, 1, 106-121 (2009)
[39] Wen, B.; Chen, X. J.; Pong, T. K., Linear convergence of proximal gradient algorithm with extrapolation for a class of nonconvex nonsmooth minimization problems, SIAM J. Optim., 27, 1, 124-145 (2017) · Zbl 1359.90138
[40] Wen, Z. W.; Yin, W. T.; Zhang, Y., Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm, Math. Program. Comput., 4, 4, 333-361 (2012) · Zbl 1271.65083
[41] Wu, Z. M.; Li, M., General inertial proximal gradient method for a class of nonconvex nonsmooth optimization problems, Comput. Optim. Appl., 73, 4, 129-158 (2019) · Zbl 1420.90054
[42] Wu, Z. M.; Li, C. S.; Li, M.; Andrew, L., Inertial proximal gradient methods with Bregman regularization for a class of nonconvex optimization problems, J. Glob. Optim., 79, 617-644 (2021) · Zbl 1466.90081
[43] Xie, Y.; Gu, S. H.; Liu, Y.; Zuo, W. M.; Zhang, W. S.; Zhang, L., Weighted Schatten p-norm minimization for image denoising and background subtraction, IEEE Trans. Image Process., 25, 10, 4842-4857 (2016) · Zbl 1408.94731
[44] Yang, L., Proximal gradient method with extrapolation and line search for a class of nonconvex and nonsmooth problems (2018)
[45] Yao, Q. M.; Kwok, J. T.; Wang, T. F.; Liu, T. Y., Large-scale low-rank matrix learning with nonconvex regularizers, IEEE Trans. Pattern Anal. Mach. Intell., 41, 11, 2628-2643 (2019)
[46] Zhang, C. H., Nearly unbiased variable selection under minimax concave penalty, Ann. Stat., 38, 2, 894-942 (2010) · Zbl 1183.62120
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.