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
DOI: https://doi.org/10.19139/soic.v4i2.201
Keywords: Matrix nuclear norm minimization, Matrix completion, Proximal gradient algorithm, Singular value decomposition

Abstract

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.

References

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 http://pages.cs.wisc.edu/ 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.

Published
2016-06-01
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. https://doi.org/10.19139/soic.v4i2.201
Issue
Vol 4 No 2 (2016)
Section
Research Articles
Authors who publish with this journal agree to the following terms:

    1. Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
    2. Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
    3. Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).