Article Contents
Article Contents

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

• 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.
Mathematics Subject Classification: Primary: 90C30, 49M37; Secondary: 65K05.

 Citation:

•  [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.