低秩稀疏矩阵优化问题的模型与算法

doi:10.15960/j.cnki.issn.1007-6093.2020.03.001

摘要/Abstract

摘要： 低秩稀疏矩阵优化问题是一类带有组合性质的非凸非光滑优化问题.由于零模与秩函数的重要性和特殊性，这类NP-难矩阵优化问题的模型与算法研究在过去十几年里取得了长足发展。本文从稀疏矩阵优化问题、低秩矩阵优化问题、低秩加稀疏矩阵优化问题、以及低秩张量优化问题四个方面来综述其研究现状；其中，对稀疏矩阵优化问题，主要以稀疏逆协方差矩阵估计和列稀疏矩阵优化问题为典例进行概述，而对低秩矩阵优化问题，主要从凸松弛和因子分解法两个角度来概述秩约束优化和秩（正则）极小化问题的模型与算法研究。最后，总结了低秩稀疏矩阵优化研究中的一些关键与挑战问题，并提出了一些可以探讨的问题。

关键词: 低秩稀疏矩阵优化, 凸松弛模型, 因子分解模型, 精确恢复条件, 收敛性

Abstract: Low-rank and sparse matrix optimization problem is a class of non-convex and non-smooth optimization problems with combinatorial properties. Due to the importance and special structure of the $\ell_0$-norm and rank functions, the models and algorithms of such NP-hard matrix optimization problems have been studied extensively in the past ten years with great success. This paper summarizes the progress from four aspects:sparse matrix optimization problem, low rank matrix optimization problems, low rank plus sparse matrix optimization problem, and low rank tensor optimization problems. For the sparse matrix optimization problem, we mainly focus on the sparse inverse covariance matrix estimation and column sparse matrix optimization problems as examples. For the low-rank matrix optimization problem, we mainly consider the convex relaxation methods and the matrix decomposition methods. Finally, we summarize a few challenging issues in low-rank and sparse matrix optimization, and disucss some interesting topics.

Key words: low-rank and sparse matrix optimization, convex relaxation models, factorization models, exact recovery conditions, convergence

中图分类号:

O221.2
O224

潘少华, 文再文. 低秩稀疏矩阵优化问题的模型与算法[J]. 运筹学学报, 2020, 24(3): 1-26.

PAN Shaohua, WEN Zaiwen. Models and algorithms for low-rank and sparse matrix optimization problems[J]. Operations Research Transactions, 2020, 24(3): 1-26.

参考文献

[1] Corless R M, Gianni P M, Trager B M, Watt S M. The singular value decomposition for polynomial systems[J]. Proceedings of the 1995 international symposium on Symbolic and algebraic computation. ACM, 1995, 195-207.
[2] Markovsky I. Recent progress on variable projection methods for structured low-rank approximation[J]. Signal Processing, 2014, 96:406-419.
[3] Fazel M. Matrix rank minimization with applications[D]. Stanford:Stanford University, 2002.
[4] Negahban S, Wainwright M J. Estimation of (near) low-rank matrices with noise and highdimensional scaling[J]. The Annals of Statistics, 2011, 39:1069-1097.
[5] Fazel M, Pong T K, Sun D F, Tseng P. Hankel matrix rank minimization with applications to system identification and realization[J]. SIAM Journal on Matrix Analysis and Applications, 2013, 34:946-977.
[6] Haeffele B D, Yang E, Vidal R. Structured low-rank matrix factorization:optimality, algorithm and applications to image processing[C]//Proceedings of the 31st International Conference on Machine Learning (ICML), 2014, 2007-2015.
[7] Srebro N. Learning with matrix factorizations[D]. Massachusetts:Massachusetts Institute of Technology, 2004.
[8] Gross D, Liu Y K, Flammia S T, Becker S, Eisert J. Quantum state tomography via compressed sensing[J]. Physical Review Letters, 2011, 105:150401.
[9] Pietersz R, Groenen P J F. Rank reduction of correlation matrices by majorization[J]. Quantitative Finance, 2004, 4:649-662.
[10] Tasissa A, Lai R J. Exact reconstruction of Euclidean distance geometry problem using lowrank matrix completion[J]. IEEE Transactions on Information Theory, 2019, 65:3124-3144.
[11] Rockafellar R T, Wets R J-B. Variational Analysis[M]. Springer, 1998.
[12] Mangasarian O L. Machine learning via polyhedral concave minimization[M]//Applied Mathematics and Parallel Computing-Festschrift for Klaus Ritter, 1996, 175-188.
[13] Le H Y. Generalized subdifferentials of the rank function[J]. Optimization Letters, 2013, 7:731-743.
[14] Bauschke H H, Luke D R, Phan H M, Wang X F. Restricted normal cones and sparsity optimization with affine constraints[J]. Foundations of Computational Mathematics, 2014, 14:63-83.
[15] Daniilidis A, Lewis A S, Malick J, Sendov H S. Prox-regularity of spectral functions and spectral sets[J]. Journal of Convex Analysis, 2008, 15:547-560.
[16] Lewis A S, Sendov H S. Nonsmooth analysis of singular values. Part I:Theory[J]. Set-Valued Analysis, 2005, 13:213-241.
[17] Lewis A S, Sendov H S. Nonsmooth analysis of singular values. Part Ⅱ:Applications[J]. Set-Valued Analysis, 2005, 13:243-264.
[18] Shalev-Shwartz S, Srebro N, Zhang T. Trading accuracy for sparsity in optimization problems with sparsity constraints[J]. SIAM Journal on Optimization, 2010, 20:2807-2832.
[19] Jain P, Tewari A, Kar P. On iterative hard thresholding methods for high-dimensional MEstimation[C]//Proceedings of the 27th International Conference on Neural Information Processing Systems, 2014, 1:685-693.
[20] Agarwal A, Negahban S, Wainwright M J. Fast global convergence of gradient methods for high-dimensional statistical recovery[J]. The Annals of Statistics, 2012, 40:2452-2482.
[21] Ding C. Variational analysis of the Ky Fan k-norm[J]. Set Valued & Variational Analysis, 2016, 25:265-296.
[22] Recht B, Fazel M, Parrilo P A. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization[J]. SIAM Review, 2010, 52:471-501.
[23] Candès E J, Recht B. Exact matrix completion via convex optimization[J]. Foundations of Computational Mathematics, 2009, 9:717-772.
[24] Chen Y D. Incoherence-optimal matrix completion[J]. IEEE Transactions on Information Theory, 2015, 60:2909-2923.
[25] Attouch H, Bolte J, Redont P, Soubeyran A. Proximal alternating minimization and projection methods for nonconvex problems:An approach based on the Kurdyka-Lojasiewicz inequality[J]. Mathematics of Operations Research, 2010, 35:438-457.
[26] Li G Y, Pong T K. Calculus of the exponent of Kurdyka-Lojasiewicz inequality and its applications to linear convergence of first-order methods[J]. Foundations of Computational Mathematics, 2018, 18:1199-1232.
[27] Yuan M, Lin Y. Model selection and estimation in the Gaussian graphical model[J]. Biometrika, 2007, 94:19-35.
[28] Friedman J, Hastie T, Tibshirani R. Sparse inverse covariance estimation with the graphical lasso[J]. Biostatistics, 2008, 9:432-441.
[29] Banerjee O, Ghaoui L E, ďaspremont A. Model selection through sparse maximum likelihood estimation for multivariate Gaussian or binary data[J]. Journal of Machine Learning Research, 2008, 9:485-516.
[30] Cai T, Liu W D, Luo X. A constrained $\ell_1$ minimization approach to sparse precision matrix estimation[J]. Journal of the American Statistical Association, 2011, 106:594-607.
[31] Ravikumar P, Wainwright M J, Raskutti G, Yu B. High-dimensional covariance estimation by minimizing $\ell_1$-penalized log-determinant divergence noise[J]. Electronic Journal of Statistics, 2011, 5:935-980.
[32] Hsieh C J, Sustik M A, Dhillon I S, Ravikumar P. QUIC:Quadratic approximation for sparse inverse covariance estimation[J]. Journal of Machine Learning Research, 2014, 15:2911-2947.
[33] Obozinski G, Wainwright M J, Jordan M I. Union support recovery in high-dimensional multivariate regression[J]. The Annals of Statistics, 2011, 39:1-47.
[34] Obozinski G, Taskar B, Jordan M I. Joint covariate selection and joint subspace selection for multiple classification problems[J]. Statistical Computing, 2010, 20:231-252.
[35] Zhang Y, Yang Q. An overview of multi-task learning[J]. National Science Review, 2018, 5:30-43.
[36] Attouch H, Cabot A. Convergence rate of inertial forward-backward algorithm[J]. SIAM Journal on Optimization, 2018, 28:849-874.
[37] Wright S J. Coordinate descent algorithmsm[J]. Mathematical Programming, 2015, 151:3-34.
[38] Gabay D, Mercier B. A dual algorithm for the solution of nonlinear variational problems via finite element approximation[J]. Computers and Mathematics with Applications, 1976, 2:17-40.
[39] Glowinski R. Lectures on numerical methods for nonlinear variational problems[M]//Tata Institute of Fundamental Research Lectures on Mathematics and Physics, 1980.
[40] Glowinski R. On alternating direction methods of multipliers:A historical perspective[M]//Modeling, Simulation and Optimization for Science and Technology, Netherlands:Springer, 2014:59-82.
[41] Chartrand R. Exact reconstruction of sparse signals via nonconvex minimization[J]. IEEE Signal Processing Letters, 2007, 14:707-710.
[42] Chen X J, Xu F M, Ye Y Y. Lower bound theory of nonzero entries in solutions of $\ell_2$-$\ell_p$ minimization[J]. SIAM Journal on Scientific Computing, 2010, 32:2832-2852.
[43] Hu Y H, Li C, Meng K W, Qin J, Yang X Q. Group sparse optimization via $\ell_p,q$ regularization[J]. Journal of Machine Learning Research, 2017, 18:1-52.
[44] Liu Y F, Dai Y H, Ma S Q. Joint power and admission control:Non-convex L_q approximation and an effective polynomial time deflation approach[J]. IEEE Transactions on Signal Processing, 2015, 63:3641-3655.
[45] Liu Y F, Ma S Q, Dai Y H, Zhang S Z. A smoothing SQP framework for a class of composite L q minimization over polyhedron[J]. Mathematical Programming, 2016, 158:467-500.
[46] Bradley P S, Mangasarian O L. Feature selection via concave minimization and support vector machines[C]//Proceeding of international conference on machine learning ICML, 1998, 82-90.
[47] Rinaldi F, Schoen F, Sciandrone M. Concave programming for minimizing the zero-norm over polyhedral sets[J]. Computation Optimization and Applications, 2010, 46:467-486.
[48] Weston J, Elisseef A, Schölkopf B, Tipping M. Use of the zero norm with linear models and kernel methods[J]. Journal of Machine Learning Research, 2003, 3:1439-1461.
[49] Fan J Q, Li R Z. Variable selection via nonconcave penalized likelihood and its oracle properties[J]. Journal of American Statistics Association, 2001, 96:1348-1360.
[50] Zhang C H. Nearly unbiased variable selection under minimax concave penalty[J]. Annals of Statistics, 2010, 38:894-942.
[51] Soubies E, Blang-Fraud L, Aubert G. A unified view of exact continuous penalities for $\ell_2$-$\ell_0$ minimization[J]. SIAM Journal on Optimization, 2017, 8:1067-1639.
[52] Liu Y L, Bi S J, Pan S H. Equivalent Lipschitz surrogates for zero-norm and rank optimization problems[J]. Journal of Global Optimization, 2018, 72:679-704.
[53] Candès E J, Plain Y. Tight oracle inequalities for low-rank matrix recovery from a minimal number of noisy random measurements[J]. IEEE Transactions on Information Theory, 2011, 57:2342-2359.
[54] Negahban S, Wainwright M J. Restricted strong convexity and weighted matrix completion:Optimal bounds with noise[J]. Journal of Machine Learning Research, 2012, 13:1665-1697.
[55] Liu Y L, Pan S H, Bi S J. Isolated calmness of solution mappings and exact recovery conditions for nuclear norm optimization problems[J]. Optimization, 2020, DOI:10.1080/02331934.2020.//1723584.
[56] Cai J F, Candès E J, Shen Z W. A singular value thresholding algorithm for matrix completion[J]. SIAM Journal on Optimization, 2010, 20:1956-1982.
[57] Liu Y J, Sun D F, Toh K C. An implementable proximal point algorithmic framework for nuclear norm minimization[J]. Mathematical Programming, 2012, 133:399-436.
[58] Yang J F, Yuan X M. Linearized augmented Lagrangian and alternating direction methods for nuclear norm minimization[J]. Mathematics of Computation, 2013, 80:301-329.
[59] Ma S Q, Goldfarb D, Chen L F. Fixed point and Bregman iterative methods for matrix rank minimization[J]. Mathematical Programming, 2011, 128:321-353.
[60] Toh K C, Yun S. An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems[J]. Pacific Journal of Optimization, 2010, 6:615-640.
[61] Drusvyatskiy D, Lewis A S. Error bounds, quadratic growth, and linear convergence of proximal methods[J]. Mathematics of Operations Research, 2018, 4:919-948.
[62] Zou Z R, So A M C. A unified approach to error bounds for structured convex optimization problems[J]. Mathematical Programming, 2017, 165:689-728.
[63] Kong L C, Xiu N H. Exact low-rank matrix recovery via nonconvex schatten p-minimization[J]. Asia-Pacific Journal of Operational Research, 2013, 30:1340010.
[64] Yue M C, So A M C. A perturbation inequality for concave functions of singular values and its applications in low-rank matrix recovery[J]. Applied and Computational Harmonic Analysis, 2016, 40:396-416.
[65] Rohde A, Tsybakov A B. Estimation of high-dimensional low-rank matrices[J]. The Annals of Statistics, 2011, 39:887-930.
[66] Fornasier M, Rauhut H, Ward R. Low-rank matrix recovery via iteratively reweighted least squares minimization[J]. SIAM Journal on Optimization, 2011, 21:1614-1640.
[67] Kümmerle C, Sigl J. Harmonic mean iteratively reweighted least squares for low-rank matrix recovery[J]. Journal of Machine Learning Research, 2018, 19:1-49.
[68] Lai M J, Xu Y Y, Yin W T. Improved iteratively reweighted least squares for unconstrained smoothed minimization[J]. SIAM Journal on Numerical Analysis, 2013, 51:927-957.
[69] Bi S J, Pan S H. Multistage convex relaxation approach to rank regularized minimization problems based on equivalent mathematical program with a generalized complementarity constraint[J]. SIAM Journal on Control and Optimization, 2017, 55:2493-2518.
[70] Liu T X, Pong T K, Takeda A. A refined convergence analysis of pDCAe with applications to simultatneous sparse recovery and outlier detection[J]. Computation Optimization and Applications, 2019, 73:69-100.
[71] Gao Y, Sun D F. A majorized penalty approach for calibrating rank constrained correlation matrix problems[R]. Singapore:National University of Singapore, 2010.
[72] Bi S J, Pan S H. Error bounds for rank constrained optimization problems and applications[J]. Operations Research Letters, 2016, 44:336-341.
[73] Burer S, Monteiro R D. A nonlinear programming algorithm for solving semidefinite programs with low-rank factorization[J]. Mathematical Programming, 2003, 95:329-357.
[74] Rennie J D M, Srebro N. Fast maximum margin matrix factorization for collaborative prediction[C]//Proceedings of the 22nd International Conference on Machine Learning, 2005, 713-719.
[75] Biswas P, Ye Y Y. Semidefinite programming for ad hoc wireless sensor network localization[C]Proceedings of the 3rd international symposium on Information Processing in Sensor Networks, 2004, 46-54.
[76] DeCoste D. Collaborative prediction using ensembles of maximum margin matrix factorizations[C]//Proceedings of the 23rd International Conference on Machine Learning, 2006, 249-256.
[77] Koren Y, Bell R, Volinsky C. Matrix factorization techniques for recommender systems[J]. Computer, 2009, 8:30-37.
[78] Park D, Kyrillidis A, Caramanis C, Sanghavi S. Non-square matrix sensing without spurious local minima via the Burer-Monteiro approach[C]//Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, 2017, 54:65-74.
[79] Ge R, Lee J D, Ma T. Matrix completion has no spurious local minimum[J]. Advances in Neural Information Processing Systems, 2016, 2973-2981
[80] Ge R, Jin C, Zheng Y. Matrix completion has no spurious local minimum[C]//Proceedings of the 34th International Conference on Machine Learning, 2017, 1233-1242.
[81] Bhojanapalli S, Neyshabur B, Srebro N. Global optimality of local search for low rank matrix recovery[J]. Advances in Neural Information Processing Systems, 2016, 3873-3881.
[82] Zhu Z H, Li Q W, Tang G G, Wakin M B. Global optimization in low-rank matrix optimization[J]. IEEE Transactions on Signal Processing, 2018, 66:3614-3628.
[83] Li Q W, Zhu Z H, Tang G G. The non-convex geometry of low-rank matrix optimization[J]. Information and Inference:A Journal of the IMA, 2018, 8:51-96.
[84] Jain P, Netrapalli P, Sanghavi S. Low-rank matrix completion using alternating minimization[J]. ACM Symposium on Theory of Computing, 2013, 665-674.
[85] Park D, Kyrillidis A, Caramanis C, Sanghavi S. Finding low-rank solution via non-convex matrix factorization efficiently and provably[J]. SIAM Journal on Imaging Sciences, 2018, 11:2165-2204.
[86] Sun R Y, Luo Z Q. Guaranteed matrix completion via non-convex factorization[J]. IEEE Transactions on Information Theory, 2016, 62:6535-6579.
[87] Tu S, Boczar R, Simchowitz M, Soltanolkotabi M, Recht B. Low-rank solution of linear matrix equations via procrustes flo[J]. International Conference on Machine Learning, 2016, 48:964-973.
[88] Zhao T, Wang Z R, Liu H. A nonconvex optimization framework for low rank matrix estimation[J]. Advances in Neural Information Processing Systems, 2015, 2:559-567.
[89] Zheng Q Q, Lafferty J. A convergent gradient descent algorithm for rank minimization and semidefinite programming from random linear measurements[J]. Advances in Neural Information Processing Systems, 2015, 109-117.
[90] Wen Z W, Yin W T, Zhang Y. Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm[J]. Mathematical Programming Computation, 2012, 4:333-361.
[91] Zhang X, Wang L X, Yu Y D, Gu Q Q. A primal-dual analysis of global optimality in nonconvex low-rank matrix recovery[C]//Proceedings of the 35th International Conference on Machine Learning, 2018, 5862-5871.
[92] Chen Y X, Chi Y J, Fan J Q, Ma C, Yan Y L. Noisy matrix completion:Understanding statistical guarantees for convex relaxation via nonconvex optimization[R]. arXiv:1902.07698v2, 2019.
[93] Lee D, Seung H. Learning the parts of objects by non-negative matrix factorization[J]. Nature, 1999, 401:788-791.
[94] Fu X, Huang K J, Sidiropoulos N D. On identifiability of nonnegative matrix factorization[J]. IEEE Transactions on Signal Processing, 2018, 25:2306-2320.
[95] Fu X, Huang K J, Sidiropoulos N D, Ma W K. Nonnegative matrix factorization for signal and data analytics:Identifiability, algorithms, and applications[J]. IEEE Signal Processing Magazine, 2019, 36:59-80.
[96] Kim J G, He Y L, Park H. Algorithms for nonnegative matrix and tensor factorizations:A unified view based on block coordinate descent framework[J]. Journal of Global Optimization, 2014, 58:285-319.
[97] Donoho D, Stodden V. When does non-negative matrix factorization give a correct decomposition into parts[J]. Proceedings of Advances in Neural Information Processing Systems, 2004, 1141-1148.
[98] Laurberg H, Christensen M G, Plumbley M D, Hansen L K, Jensen S. Theorems on positive data:On the uniqueness of NMF[J]. Computational Intelligence and Neuroscience, 2008, 764206, 1-9.
[99] Huang K J, Sidiropoulos N, Swami A. Non-negative matrix factorization revisited:uniqueness and algorithm for symmetric decomposition[J]. IEEE Transactions on Signal Processing, 2014, 62:211-224.
[100] Agarwal A, Negahban S, Wainwright M J. Noisy matrix decomposition via convex relaxation:Optimal rates in high dimensions[J]. The Annals of Statistics, 2012, 40:1171-1197.
[101] Min K R, Zhang Z D, Wright J, Ma Y. Decomposing background topics from keywords by principal component pursuit[C]//Proceedings of the 19th ACM international conference on Information and Knowledge Management, 2010, 269-278.
[102] Chandrasekaran V, Sanghavi S, Parrilo P A, Willsky A S. Rank-sparsity incoherence for matrix decomposition[J]. SIAM Journal on Optimization, 2009, 21:572-596.
[103] Candès E J, Li X D, Ma Y, Wright J. Robust principal component analysis[J]. Journal of the ACM, 2009, 58:1-37.
[104] Zhou Z H, Li X D, Wright J, Candès E J, Ma Y. Stable principal component pursuit[J]. IEEE International Symposium on Information Theory, 2010, 1518-1522.
[105] Hsu D, Kakade S M, Zhang T. Robust matrix decomposition with sparse corruptions[J]. IEEE Transactions on Information Theory, 2011, 57:7221-7234.
[106] Han L, Bi S J, Pan S H. Two-stage convex relaxation approach to least squares loss constrained low-rank plus sparsity optimization problems[J]. Computational Optimization and Applications, 2016, 64:119-148.
[107] Li X D, Sun D F, Toh K C. A Schur complement based semi-proximal ADMM for convex quadratic conic programming and extensions[J]. Mathematical Programming, 2016, 155:333-373.
[108] Chen L, Sun D F, Toh K C. An effcient inexact symmetric Gauss-Seidel based majorized ADMM for high-dimensional convex composite conic programming[J]. Mathematical Programming, 2017, 161:237-270.
[108] Gu Q Q, Wang Z R, Li H. Low-rank and sparse structure pursuit via alternating minimization[C]//Proceedings of the 19th International Conference on Artificial Intelligence and Statistics, 2016, 51:600-609.
[109] Netrapalli P, Niranjan U N, Sanghavi S, Anandkumar A. Provable non-convex robust PCA[C]Proceedings of the 27th International Conference on Neural Information Processing Systems, 2014, 1107-1115.
[110] Friedland S, Lim L H. Nuclear norm of higher-order tensors[J]. Mathematics of Computation, 2018, 87:1255-1281.
[111] Tomioka R, Suzuki T, Hayashi K, Kashima H. Statistical performance of convex tensor decomposition[J]. Advances in Neural Information Processing Systems, 2011, 972-980.
[112] Raskutti G, Yuan M, Chen H. Convex regularization for high-dimensional multi-response tensor regression[J]. The Annals of Statistics, 2019, 47:1554-1584.
[113] Phien H N, Tuan H D, Bengua J A, Do M J. Efficient tensor completion:Low-rank tensor train[J]. arXiv:1601.01083, 2016.
[114] Zhang Z, Aeron S. Exact tensor completion using t-SVD[J]. IEEE Transcations on Signal Processing, 2017, 65:1511-1526.
[115] Cichocki A, Lee N, Oseledets I V, Phan A H, Zhao Q B, Mandic D P. Tensor networks for dimensionality reduction and large-scale optimization problems:Part 1 Low-rank tensor decomposition[J]. Foundations and Trends in Machine Learing, 2016, 9:249-429.
[116] Xu Y Y, Yin W T. A block coordinate descent method for regularized multiconvex optimization with applications to nonnegative tensor factorization and completion[J]. SIAM Journal on Imaging Science, 2013, 3:1758-1789.
[117] Oymak S, Jalali A, Fazel M, Eldar Y C, Hassibi B. Simultaneously structured models with application to sparse and low-rank matrices[J]. IEEE Transactions on Information Theory, 2015, 61:2886-2908.
[118] Tibshirani R, Saunders M, Rosset S, Zhu J, Knight K. Sparsity and smoothness via the fused lasso[J]. Journal of the Royal Statistical Society, 2005, 67:91-108.
[119] Yuan L, Liu J, Ye J P. Sparsity and smoothness via the fused lasso[J]. IEEE Transactions on Pattern Analysis and Machine Intelligence, 2013, 35:2104-2116.
[120] Attouch H, Bolte J, Redont P, Soubeyran A. Proximal alternating minimization and projection methods for nonconvex problems:An approach based on the Kurdyka-Lojasiewicz inequality[J]. Mathematics of Operations Research, 2010, 35:438-457.
[121] Attouch H, Bolte J, Svaiter B F. Convergence of descent methods for semi-algebraic and tame problems:Proximal algorithms, forward-backward splitting, and reguarlized Gauss-Seidel methods[J]. Mathematical Programming, 2013, 137:91-129.
[122] Bertsimas D, Copenhaver M S. Characterization of the equivalence of robustification and regularization in linear and matrix regression[J]. European Journal of Operational Research, 2018, 270:931-942.
[123] Hastie T, Mazumder R, Lee J D, Zadeh R. Matrix completion and low-rank SVD via fast alternating least squares[J]. Journal of Machine Learning Research, 2015, 16:3367-3402.