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

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.
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, 49 (2011), 33.  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.  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).  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.  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, 6 (2001), 4734.  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.  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.   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.   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.  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,, , (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.  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.  doi: 10.1137/090755436.  Google Scholar

[14]

N. Natarajan and I. S. Dhillon, Inductive matrix completion for predicting gene-disease associations,, Bioinformatics, 30 (2014).  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.  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.   Google Scholar

[17]

X. Yuan and J. Yang, Sparse and low-rank matrix decomposition via alternating direction methods,, Pac. J. Optim., 9 (2013), 167.   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.  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, 49 (2011), 33.  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.  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).  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.  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, 6 (2001), 4734.  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.  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.   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.   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.  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,, , (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.  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.  doi: 10.1137/090755436.  Google Scholar

[14]

N. Natarajan and I. S. Dhillon, Inductive matrix completion for predicting gene-disease associations,, Bioinformatics, 30 (2014).  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.  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.   Google Scholar

[17]

X. Yuan and J. Yang, Sparse and low-rank matrix decomposition via alternating direction methods,, Pac. J. Optim., 9 (2013), 167.   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.  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]

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

[3]

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

[4]

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

[5]

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

[6]

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

[7]

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

[8]

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

[9]

Yuan Shen, Xin Liu. An alternating minimization method for matrix completion problems. Discrete & Continuous Dynamical Systems - S, 2018, 0 (0) : 0-0. doi: 10.3934/dcdss.2020103

[10]

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

[11]

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

[12]

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

[13]

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

[14]

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

[15]

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

[16]

H. D. Scolnik, N. E. Echebest, M. T. Guardarucci. Extensions of incomplete oblique projections method for solving rank-deficient least-squares problems. Journal of Industrial & Management Optimization, 2009, 5 (2) : 175-191. doi: 10.3934/jimo.2009.5.175

[17]

Nora Merabet. Global convergence of a memory gradient method with closed-form step size formula. Conference Publications, 2007, 2007 (Special) : 721-730. doi: 10.3934/proc.2007.2007.721

[18]

Xiaojiao Tong, Shuzi Zhou. A smoothing projected Newton-type method for semismooth equations with bound constraints. Journal of Industrial & Management Optimization, 2005, 1 (2) : 235-250. doi: 10.3934/jimo.2005.1.235

[19]

Frank Blume. Minimal rates of entropy convergence for rank one systems. Discrete & Continuous Dynamical Systems - A, 2000, 6 (4) : 773-796. doi: 10.3934/dcds.2000.6.773

[20]

Raffaele D’Ambrosio, Giuseppe De Martino, Beatrice Paternoster. A symmetric nearly preserving general linear method for Hamiltonian problems. Conference Publications, 2015, 2015 (special) : 330-339. doi: 10.3934/proc.2015.0330

2018 Impact Factor: 1.025

Metrics

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

Other articles
by authors

[Back to Top]