Two-Step Proximal Gradient Algorithm for Low-Rank Matrix Completion

  • Qiuyu Wang Henan University
  • Wenjiao Cao Henan University
  • Zhengfen Jin Henan University of Science and Technology
Keywords: Matrix nuclear norm minimization, Matrix completion, Proximal gradient algorithm, Singular value decomposition


In this paper, we  propose a two-step proximal gradient algorithm to solve nuclear norm regularized least squares for the purpose of recovering low-rank data matrix from sampling of its entries. Each iteration generated by the proposed algorithm is a combination of the latest three points, namely, the previous point, the current iterate, and its proximal gradient point. This algorithm preserves the computational simplicity of classical proximal gradient algorithm where a singular value decomposition in proximal operator is involved. Global convergence is followed directly in the literature. Numerical results are reported to show the efficiency of the algorithm.


L. Vandenberghe and S. Boyd, Semidefinite programming, SIAM Review, vol.38,pp.49–95,1996.

B. Recht, M. Fazel, and PA. Parrilo, Guaranteed minimum rank solutions of matrix equations via nuclear norm minimization, SIAM Review,vol.52,pp.471–501,2010.

J.F. Cai, E.J. Candès, and Z. Shen, A singular value thresholding algorithm for matrix completion, preprint, SIAM J. Optim., vol.20, pp.1956–1982,2010.

E.J. Candès and B. Recht, Exact matrix completion via convex optimization, Foundations of Computational Mathematics, vol.9, pp.717–772,2009.

K.C. Toh, and S.W. Yun, An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems, Pacific J. Optim., vol.6, pp.615–640, 2010.

A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imag. Sci., vol.2, pp.183–202, 2009.

R.-P. Wen, X.-H. Yan, A new gradient projection method for matrix completion, App. Math. Comput., vol.258, pp.537–544, 2015.

H. Zhang, L.Z. Cheng, Projected Landweber iteration for matrix completion, J. Comput. Appl. Math., vol.235, pp.593–601,2010.

Y.-F. Li, Y.-J. Zhang, and Z.-H. Huang, A reweighted nuclear norm minimization algorithm for low rank matrix recovery, J. Comput. Appl. Math., vol.263, pp.338–350, 2014.

Y. Xiao, S.-Y. Wu, D.-H. Li, Splitting and linearizing augmented Lagrangian algorithm for subspace recovery from corrupted observations, Adv. Comput. Math., vol.38 , pp.837–858, 2013.

S. Ma, D. Goldfarb, and L. Chen, Fixed point and Bregman iterative methods for matrix rank minimization, Math. Program., vol.128, pp.321–353, (2011).

E.T. Hale, W. Yin, and Y. Zhang, Fixed-point continuation for ℓ1-minimization: methodology and convergence, SIAM J. Optim., vol.19, pp.1107–1130, 2008.

Y.J. Liu, D. Sun, and K.C. Toh, An implementable proximal point algorithmic frameword for nuclear norm minimization, Math. Program., vol.133 , pp.399–436,2012.

J.M. Bioucas-Dias and M. Figueiredo, A new TwIST: Two-step iterative shrinkage/thresholding algorithms for image restoratin, IEEE Trans. Image. Proces., vol.16, pp.2992–3004, 2007.

M. Elad, B. Matalon, and M. Zibulevsky, Subspace optimization methods for linear least squares with non-quadratic regularization, Appl. Comput. Harmon. Anal., vol.23, pp.346–367, 2007.

Y. Nesterov, Gradient methods for minimizing composite objective function, CORE Discussion Paper, Catholic University of Louvain, vol.76, 2007.

P. Tseng, On accelerated proximal gradient methods for convex-concave optimization, SIAM J. Optim., available at brecht/cs726docs/Tseng.APG.pdf

B. O’Donoghue and E. Candès, Adaptive restart for accelerated gradient schemes, Found. Comput. Math., vol.15, pp.715–732, 2015.

O. Axelsson, Iterative Solution Methods, Cambridge University Press, New York, 1996.

Z.-F. Jin, Z. Wan, Y. Jiao, and X. Lu, An alternating direction method with continuation for nonconvex low rank minimization, J. Sci. Comput., doi: 10.1007/s10915-015-0045-0.

How to Cite
Wang, Q., Cao, W., & Jin, Z. (2016). Two-Step Proximal Gradient Algorithm for Low-Rank Matrix Completion. Statistics, Optimization & Information Computing, 4(2), 174-182.
Research Articles