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

Yu-Ning  Yang; Su  Zhang

doi:10.3934/jimo.2016.12.1507

Article Contents

2016, Volume 12, Issue 4: 1507-1519. Doi: 10.3934/jimo.2016.12.1507

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

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
2.
Business School and China Academy of Corporate Governance, Nankai University, Tianjin 300071

Received: May 31, 2015

Revised: September 30, 2015

Published: September 2016

Abstract Related Papers Cited by

Abstract

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:

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

Citation:

Related Papers

Cited by

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.