American Institute of Mathematical Sciences

Advanced
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

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 & 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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

P. J. Huber, Robust statistics, Springer, 2011. Google Scholar

[8]

P. Jain, R. Meka and I. S. Dhillon, Guaranteed rank minimization via singular value projection, In NIPS, 23 (2010), 937-945. Google Scholar

[9]

L. Kong, J. Sun and N. Xiu, S-semigoodness for low-rank semidefinite matrix recovery, Pacific Journal of Optimization, 10 (2014), 73-83.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

X. Yuan and J. Yang, Sparse and low-rank matrix decomposition via alternating direction methods, Pac. J. Optim., 9 (2013), 167-180.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

P. J. Huber, Robust statistics, Springer, 2011. Google Scholar

[8]

P. Jain, R. Meka and I. S. Dhillon, Guaranteed rank minimization via singular value projection, In NIPS, 23 (2010), 937-945. Google Scholar

[9]

L. Kong, J. Sun and N. Xiu, S-semigoodness for low-rank semidefinite matrix recovery, Pacific Journal of Optimization, 10 (2014), 73-83.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[17]

X. Yuan and J. Yang, Sparse and low-rank matrix decomposition via alternating direction methods, Pac. J. Optim., 9 (2013), 167-180.  Google Scholar

[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.  Google Scholar

[1]

Xing Li, Chungen Shen, Lei-Hong Zhang. A projected preconditioned conjugate gradient method for the linear response eigenvalue problem. Numerical Algebra, Control & 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 & Optimization, 2020, 10 (4) : 425-437. doi: 10.3934/naco.2020042
[3]

Stefan Kindermann. Convergence of the gradient method for ill-posed problems. Inverse Problems & Imaging, 2017, 11 (4) : 703-720. doi: 10.3934/ipi.2017033
[4]

Rouhollah Tavakoli, Hongchao Zhang. A nonmonotone spectral projected gradient method for large-scale topology optimization problems. Numerical Algebra, Control & Optimization, 2012, 2 (2) : 395-412. doi: 10.3934/naco.2012.2.395
[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 & Management Optimization, 2016, 12 (1) : 389-402. doi: 10.3934/jimo.2016.12.389
[6]

Zhengshan Dong, Jianli Chen, Wenxing Zhu. Homotopy method for matrix rank minimization based on the matrix hard thresholding method. Numerical Algebra, Control & Optimization, 2019, 9 (2) : 211-224. doi: 10.3934/naco.2019015
[7]

Wei-Zhe Gu, Li-Yong Lu. The linear convergence of a derivative-free descent method for nonlinear complementarity problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 531-548. doi: 10.3934/jimo.2016030
[8]

Sari Lasanen. Non-Gaussian statistical inverse problems. Part II: Posterior convergence for approximated unknowns. Inverse Problems & Imaging, 2012, 6 (2) : 267-287. doi: 10.3934/ipi.2012.6.267
[9]

Tianxiao Wang. Characterizations of equilibrium controls in time inconsistent mean-field stochastic linear quadratic problems. I. Mathematical Control & Related Fields, 2019, 9 (2) : 385-409. doi: 10.3934/mcrf.2019018
[10]

Yuan Shen, Xin Liu. An alternating minimization method for matrix completion problems. Discrete & Continuous Dynamical Systems - S, 2020, 13 (6) : 1757-1772. doi: 10.3934/dcdss.2020103
[11]

Audric Drogoul, Gilles Aubert. The topological gradient method for semi-linear problems and application to edge detection and noise removal. Inverse Problems & Imaging, 2016, 10 (1) : 51-86. doi: 10.3934/ipi.2016.10.51
[12]

Yanmei Sun, Yakui Huang. An alternate gradient method for optimization problems with orthogonality constraints. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021003
[13]

C.Y. Wang, M.X. Li. Convergence property of the Fletcher-Reeves conjugate gradient method with errors. Journal of Industrial & Management Optimization, 2005, 1 (2) : 193-200. doi: 10.3934/jimo.2005.1.193
[14]

Jahnabi Chakravarty, Ashiho Athikho, Manideepa Saha. Convergence of interval AOR method for linear interval equations. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021006
[15]

Yves Bourgault, Damien Broizat, Pierre-Emmanuel Jabin. Convergence rate for the method of moments with linear closure relations. Kinetic & Related Models, 2015, 8 (1) : 1-27. doi: 10.3934/krm.2015.8.1
[16]

Luchuan Ceng, Qamrul Hasan Ansari, Jen-Chih Yao. Extragradient-projection method for solving constrained convex minimization problems. Numerical Algebra, Control & Optimization, 2011, 1 (3) : 341-359. doi: 10.3934/naco.2011.1.341
[17]

Zhenwei Zhang, Xue Li, Yuping Duan, Ke Yin, Xue-Cheng Tai. An efficient multi-grid method for TV minimization problems. Inverse Problems & Imaging, , () : -. doi: 10.3934/ipi.2021034
[18]

Guanghui Zhou, Qin Ni, Meilan Zeng. A scaled conjugate gradient method with moving asymptotes for unconstrained optimization problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 595-608. doi: 10.3934/jimo.2016034
[19]

El-Sayed M.E. Mostafa. A nonlinear conjugate gradient method for a special class of matrix optimization problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 883-903. doi: 10.3934/jimo.2014.10.883
[20]

Leyu Hu, Xingju Cai. Convergence of a randomized Douglas-Rachford method for linear system. Numerical Algebra, Control & Optimization, 2020, 10 (4) : 463-474. doi: 10.3934/naco.2020045

2020 Impact Factor: 1.801

Tools

Metrics

  • PDF downloads (117)
  • HTML views (0)
  • Cited by (1)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences