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, 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]

Tao Wu, Yu Lei, Jiao Shi, Maoguo Gong. An evolutionary multiobjective method for low-rank and sparse matrix decomposition. Big Data & Information Analytics, 2017, 2 (1) : 23-37. doi: 10.3934/bdia.2017006
[2]

Manfred Einsiedler, Elon Lindenstrauss. On measures invariant under diagonalizable actions: the Rank-One case and the general Low-Entropy method. Journal of Modern Dynamics, 2008, 2 (1) : 83-128. doi: 10.3934/jmd.2008.2.83
[3]

Luke Finlay, Vladimir Gaitsgory, Ivan Lebedev. Linear programming solutions of periodic optimization problems: approximation of the optimal control. Journal of Industrial & Management Optimization, 2007, 3 (2) : 399-413. doi: 10.3934/jimo.2007.3.399
[4]

Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149
[5]

Deren Han, Zehui Jia, Yongzhong Song, David Z. W. Wang. An efficient projection method for nonlinear inverse problems with sparsity constraints. Inverse Problems & Imaging, 2016, 10 (3) : 689-709. doi: 10.3934/ipi.2016017
[6]

Petra Csomós, Hermann Mena. Fourier-splitting method for solving hyperbolic LQR problems. Numerical Algebra, Control & Optimization, 2018, 8 (1) : 17-46. doi: 10.3934/naco.2018002
[7]

Christina Surulescu, Nicolae Surulescu. Modeling and simulation of some cell dispersion problems by a nonparametric method. Mathematical Biosciences & Engineering, 2011, 8 (2) : 263-277. doi: 10.3934/mbe.2011.8.263
[8]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069
[9]

Gelasio Salaza, Edgardo Ugalde, Jesús Urías. Master--slave synchronization of affine cellular automaton pairs. Discrete & Continuous Dynamical Systems - A, 2005, 13 (2) : 491-502. doi: 10.3934/dcds.2005.13.491
[10]

Tuan Hiep Pham, Jérôme Laverne, Jean-Jacques Marigo. Stress gradient effects on the nucleation and propagation of cohesive cracks. Discrete & Continuous Dynamical Systems - S, 2016, 9 (2) : 557-584. doi: 10.3934/dcdss.2016012
[11]

Matthias Erbar, Jan Maas. Gradient flow structures for discrete porous medium equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1355-1374. doi: 10.3934/dcds.2014.34.1355
[12]

J. Frédéric Bonnans, Justina Gianatti, Francisco J. Silva. On the convergence of the Sakawa-Shindo algorithm in stochastic control. Mathematical Control & Related Fields, 2016, 6 (3) : 391-406. doi: 10.3934/mcrf.2016008
[13]

Fernando P. da Costa, João T. Pinto, Rafael Sasportes. On the convergence to critical scaling profiles in submonolayer deposition models. Kinetic & Related Models, 2018, 11 (6) : 1359-1376. doi: 10.3934/krm.2018053
[14]

Alberto Bressan, Carlotta Donadello. On the convergence of viscous approximations after shock interactions. Discrete & Continuous Dynamical Systems - A, 2009, 23 (1&2) : 29-48. doi: 10.3934/dcds.2009.23.29
[15]

Caifang Wang, Tie Zhou. The order of convergence for Landweber Scheme with $\alpha,\beta$-rule. Inverse Problems & Imaging, 2012, 6 (1) : 133-146. doi: 10.3934/ipi.2012.6.133
[16]

Armin Lechleiter, Tobias Rienmüller. Factorization method for the inverse Stokes problem. Inverse Problems & Imaging, 2013, 7 (4) : 1271-1293. doi: 10.3934/ipi.2013.7.1271
[17]

Andrea Cianchi, Adele Ferone. Improving sharp Sobolev type inequalities by optimal remainder gradient norms. Communications on Pure & Applied Analysis, 2012, 11 (3) : 1363-1386. doi: 10.3934/cpaa.2012.11.1363
[18]

Diana Keller. Optimal control of a linear stochastic Schrödinger equation. Conference Publications, 2013, 2013 (special) : 437-446. doi: 10.3934/proc.2013.2013.437
[19]

Guillaume Bal, Wenjia Jing. Homogenization and corrector theory for linear transport in random media. Discrete & Continuous Dynamical Systems - A, 2010, 28 (4) : 1311-1343. doi: 10.3934/dcds.2010.28.1311
[20]

Qiang Guo, Dong Liang. An adaptive wavelet method and its analysis for parabolic equations. Numerical Algebra, Control & Optimization, 2013, 3 (2) : 327-345. doi: 10.3934/naco.2013.3.327

2019 Impact Factor: 1.366

Tools

Metrics

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

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences