On linear convergence of projected gradient method for a class of affine rank minimization problems

Previous Article
Optimal asset portfolio with stochastic volatility under the mean-variance utility with state-dependent risk aversion
JIMO Home
This Issue
Next Article
Differential optimization in finite-dimensional spaces

October 2016, 12(4): 1507-1519. doi: 10.3934/jimo.2016.12.1507

On linear convergence of projected gradient method for a class of affine rank minimization problems

Yu-Ning Yang ^1, and Su Zhang ^2,

1.	School of Mathematical Sciences and LPMC, Nankai University, Tianjin 300071, China
2.	Business School and China Academy of Corporate Governance, Nankai University, Tianjin 300071, China

Received June 2015 Revised October 2015 Published January 2016

Abstract
Related Papers

The affine rank minimization problem is to find a low-rank matrix satisfying a set of linear equations, which includes the well-known matrix completion problem as a special case and draws much attention in recent years. In this paper, a new model for affine rank minimization problem is proposed. The new model not only enhances the robustness of affine rank minimization problem, but also leads to high nonconvexity. We show that if the classical projected gradient method is applied to solve our new model, the linear convergence rate can be established under some conditions. Some preliminary experiments have been conducted to show the efficiency and effectiveness of our method.

Keywords: Linear convergence, affine rank minimization problems., projected gradient method.

Mathematics Subject Classification: Primary: 90C30, 49M37; Secondary: 65K0.

Citation: Yu-Ning Yang, Su Zhang. On linear convergence of projected gradient method for a class of affine rank minimization problems. Journal of Industrial and Management Optimization, 2016, 12 (4) : 1507-1519. doi: 10.3934/jimo.2016.12.1507

References:

[1]	A. Beck and M. Teboulle, A linearly convergent algorithm for solving a class of nonconvex/affine feasibility problems, In Fixed-Point Algorithms for Inverse Problems in Science and Engineering, Springer, 49 (2011), 33-48. doi: 10.1007/978-1-4419-9569-8_3.
[2]	J.-F. Cai, E. J. Candès and Z. Shen, A singular value thresholding algorithm for matrix completion, SIAM Journal on Optimization, 20 (2010), 1956-1982. doi: 10.1137/080738970.
[3]	E. J. Candès, X. Li, Y. Ma and J. Wright, Robust principal component analysis?, Journal of the ACM (JACM), 58 (2011), Art. 11, 37 pp. doi: 10.1145/1970392.1970395.
[4]	E. J. Candès and B. Recht, Exact matrix completion via convex optimization, Foundations of Computational mathematics, 9 (2009), 717-772. doi: 10.1007/s10208-009-9045-5.
[5]	M. Fazel, H. Hindi and S. P. Boyd, A rank minimization heuristic with application to minimum order system approximation, In American Control Conference, 2001. Proceedings of the 2001, IEEE, 6 (2001), 4734-4739. doi: 10.1109/ACC.2001.945730.
[6]	D. Goldfarb and S. Ma, Convergence of fixed-point continuation algorithms for matrix rank minimization, Foundations of Computational Mathematics, 11 (2011), 183-210. doi: 10.1007/s10208-011-9084-6.
[7]	P. J. Huber, Robust statistics, Springer, 2011.
[8]	P. Jain, R. Meka and I. S. Dhillon, Guaranteed rank minimization via singular value projection, In NIPS, 23 (2010), 937-945.
[9]	L. Kong, J. Sun and N. Xiu, S-semigoodness for low-rank semidefinite matrix recovery, Pacific Journal of Optimization, 10 (2014), 73-83.
[10]	L. Kong, J. Sun, J. Tao and N. Xiu, Sparse recovery on Euclidean Jordan algebras, Linear Algebra and Applications, 465 (2015), 65-87. doi: 10.1016/j.laa.2014.09.018.
[11]	Z. Lin, M. Chen and Y. Ma, The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices, arXiv:1009.5055, 2010.
[12]	N. Linial, E. London and Y. Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica, 15 (1995), 215-245. doi: 10.1007/BF01200757.
[13]	Z. Liu and L. Vandenberghe, Interior-point method for nuclear norm approximation with application to system identification, SIAM Journal on Matrix Analysis and Applications, 31 (2009), 1235-1256. doi: 10.1137/090755436.
[14]	N. Natarajan and I. S. Dhillon, Inductive matrix completion for predicting gene-disease associations, Bioinformatics, 30 (2014), i60-i68. doi: 10.1093/bioinformatics/btu269.
[15]	B. Recht, M. Fazel and P. A. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Review, 52 (2010), 471-501. doi: 10.1137/070697835.
[16]	K.-C. Toh and S. Yun, An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems, Pacific Journal of Optimization, 6 (2010), 615-640.
[17]	X. Yuan and J. Yang, Sparse and low-rank matrix decomposition via alternating direction methods, Pac. J. Optim., 9 (2013), 167-180.
[18]	S. Zhang, J. Ang and J. Sun, An alternating direction method for solving convex nonlinear semidefinite programming problems, Optimization, 62 (2013), 527-543. doi: 10.1080/02331934.2011.611883.

show all references

References:

[1]	A. Beck and M. Teboulle, A linearly convergent algorithm for solving a class of nonconvex/affine feasibility problems, In Fixed-Point Algorithms for Inverse Problems in Science and Engineering, Springer, 49 (2011), 33-48. doi: 10.1007/978-1-4419-9569-8_3.
[2]	J.-F. Cai, E. J. Candès and Z. Shen, A singular value thresholding algorithm for matrix completion, SIAM Journal on Optimization, 20 (2010), 1956-1982. doi: 10.1137/080738970.
[3]	E. J. Candès, X. Li, Y. Ma and J. Wright, Robust principal component analysis?, Journal of the ACM (JACM), 58 (2011), Art. 11, 37 pp. doi: 10.1145/1970392.1970395.
[4]	E. J. Candès and B. Recht, Exact matrix completion via convex optimization, Foundations of Computational mathematics, 9 (2009), 717-772. doi: 10.1007/s10208-009-9045-5.
[5]	M. Fazel, H. Hindi and S. P. Boyd, A rank minimization heuristic with application to minimum order system approximation, In American Control Conference, 2001. Proceedings of the 2001, IEEE, 6 (2001), 4734-4739. doi: 10.1109/ACC.2001.945730.
[6]	D. Goldfarb and S. Ma, Convergence of fixed-point continuation algorithms for matrix rank minimization, Foundations of Computational Mathematics, 11 (2011), 183-210. doi: 10.1007/s10208-011-9084-6.
[7]	P. J. Huber, Robust statistics, Springer, 2011.
[8]	P. Jain, R. Meka and I. S. Dhillon, Guaranteed rank minimization via singular value projection, In NIPS, 23 (2010), 937-945.
[9]	L. Kong, J. Sun and N. Xiu, S-semigoodness for low-rank semidefinite matrix recovery, Pacific Journal of Optimization, 10 (2014), 73-83.
[10]	L. Kong, J. Sun, J. Tao and N. Xiu, Sparse recovery on Euclidean Jordan algebras, Linear Algebra and Applications, 465 (2015), 65-87. doi: 10.1016/j.laa.2014.09.018.
[11]	Z. Lin, M. Chen and Y. Ma, The augmented lagrange multiplier method for exact recovery of corrupted low-rank matrices, arXiv:1009.5055, 2010.
[12]	N. Linial, E. London and Y. Rabinovich, The geometry of graphs and some of its algorithmic applications, Combinatorica, 15 (1995), 215-245. doi: 10.1007/BF01200757.
[13]	Z. Liu and L. Vandenberghe, Interior-point method for nuclear norm approximation with application to system identification, SIAM Journal on Matrix Analysis and Applications, 31 (2009), 1235-1256. doi: 10.1137/090755436.
[14]	N. Natarajan and I. S. Dhillon, Inductive matrix completion for predicting gene-disease associations, Bioinformatics, 30 (2014), i60-i68. doi: 10.1093/bioinformatics/btu269.
[15]	B. Recht, M. Fazel and P. A. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Review, 52 (2010), 471-501. doi: 10.1137/070697835.
[16]	K.-C. Toh and S. Yun, An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems, Pacific Journal of Optimization, 6 (2010), 615-640.
[17]	X. Yuan and J. Yang, Sparse and low-rank matrix decomposition via alternating direction methods, Pac. J. Optim., 9 (2013), 167-180.
[18]	S. Zhang, J. Ang and J. Sun, An alternating direction method for solving convex nonlinear semidefinite programming problems, Optimization, 62 (2013), 527-543. doi: 10.1080/02331934.2011.611883.

[1]	Xing Li, Chungen Shen, Lei-Hong Zhang. A projected preconditioned conjugate gradient method for the linear response eigenvalue problem. Numerical Algebra, Control and Optimization, 2018, 8 (4) : 389-412. doi: 10.3934/naco.2018025
[2]	Wanbin Tong, Hongjin He, Chen Ling, Liqun Qi. A nonmonotone spectral projected gradient method for tensor eigenvalue complementarity problems. Numerical Algebra, Control and Optimization, 2020, 10 (4) : 425-437. doi: 10.3934/naco.2020042
[3]	Rouhollah Tavakoli, Hongchao Zhang. A nonmonotone spectral projected gradient method for large-scale topology optimization problems. Numerical Algebra, Control and Optimization, 2012, 2 (2) : 395-412. doi: 10.3934/naco.2012.2.395
[4]	Stefan Kindermann. Convergence of the gradient method for ill-posed problems. Inverse Problems and Imaging, 2017, 11 (4) : 703-720. doi: 10.3934/ipi.2017033
[5]	Sanming Liu, Zhijie Wang, Chongyang Liu. On convergence analysis of dual proximal-gradient methods with approximate gradient for a class of nonsmooth convex minimization problems. Journal of Industrial and Management Optimization, 2016, 12 (1) : 389-402. doi: 10.3934/jimo.2016.12.389
[6]	Yadan Chen, Yuan Shen, Shanshan Liu. Trace minimization method via penalty for linear response eigenvalue problems. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021206
[7]	Zhengshan Dong, Jianli Chen, Wenxing Zhu. Homotopy method for matrix rank minimization based on the matrix hard thresholding method. Numerical Algebra, Control and Optimization, 2019, 9 (2) : 211-224. doi: 10.3934/naco.2019015
[8]	Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030
[9]	Sari Lasanen. Non-Gaussian statistical inverse problems. Part II: Posterior convergence for approximated unknowns. Inverse Problems and Imaging, 2012, 6 (2) : 267-287. doi: 10.3934/ipi.2012.6.267
[10]	Tianxiao Wang. Characterizations of equilibrium controls in time inconsistent mean-field stochastic linear quadratic problems. I. Mathematical Control and Related Fields, 2019, 9 (2) : 385-409. doi: 10.3934/mcrf.2019018
[11]	Yuan Shen, Xin Liu. An alternating minimization method for matrix completion problems. Discrete and Continuous Dynamical Systems - S, 2020, 13 (6) : 1757-1772. doi: 10.3934/dcdss.2020103
[12]	Audric Drogoul, Gilles Aubert. The topological gradient method for semi-linear problems and application to edge detection and noise removal. Inverse Problems and Imaging, 2016, 10 (1) : 51-86. doi: 10.3934/ipi.2016.10.51
[13]	Yanmei Sun, Yakui Huang. An alternate gradient method for optimization problems with orthogonality constraints. Numerical Algebra, Control and Optimization, 2021, 11 (4) : 665-676. doi: 10.3934/naco.2021003
[14]	C.Y. Wang, M.X. Li. Convergence property of the Fletcher-Reeves conjugate gradient method with errors. Journal of Industrial and Management Optimization, 2005, 1 (2) : 193-200. doi: 10.3934/jimo.2005.1.193
[15]	Luchuan Ceng, Qamrul Hasan Ansari, Jen-Chih Yao. Extragradient-projection method for solving constrained convex minimization problems. Numerical Algebra, Control and Optimization, 2011, 1 (3) : 341-359. doi: 10.3934/naco.2011.1.341
[16]	Zhenwei Zhang, Xue Li, Yuping Duan, Ke Yin, Xue-Cheng Tai. An efficient multi-grid method for TV minimization problems. Inverse Problems and Imaging, 2021, 15 (5) : 1199-1221. doi: 10.3934/ipi.2021034
[17]	Yves Bourgault, Damien Broizat, Pierre-Emmanuel Jabin. Convergence rate for the method of moments with linear closure relations. Kinetic and Related Models, 2015, 8 (1) : 1-27. doi: 10.3934/krm.2015.8.1
[18]	Jahnabi Chakravarty, Ashiho Athikho, Manideepa Saha. Convergence of interval AOR method for linear interval equations. Numerical Algebra, Control and Optimization, 2022, 12 (2) : 293-308. doi: 10.3934/naco.2021006
[19]	Hong Seng Sim, Chuei Yee Chen, Wah June Leong, Jiao Li. Nonmonotone spectral gradient method based on memoryless symmetric rank-one update for large-scale unconstrained optimization. Journal of Industrial and Management Optimization, 2021 doi: 10.3934/jimo.2021143
[20]	Guanghui Zhou, Qin Ni, Meilan Zeng. A scaled conjugate gradient method with moving asymptotes for unconstrained optimization problems. Journal of Industrial and Management Optimization, 2017, 13 (2) : 595-608. doi: 10.3934/jimo.2016034

2020 Impact Factor: 1.801

Tools

Metrics

Other articles
by authors

on AIMS
Yu-Ning Yang Su Zhang
on Google Scholar
Yu-Ning Yang Su Zhang

[Back to Top]