Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm | Mathematical Programming Computation Skip to main content
Springer Nature Link
Log in

Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm

  • Full Length Paper
  • Published:
Mathematical Programming Computation Aims and scope Submit manuscript

Abstract

The matrix completion problem is to recover a low-rank matrix from a subset of its entries. The main solution strategy for this problem has been based on nuclear-norm minimization which requires computing singular value decompositions—a task that is increasingly costly as matrix sizes and ranks increase. To improve the capacity of solving large-scale problems, we propose a low-rank factorization model and construct a nonlinear successive over-relaxation (SOR) algorithm that only requires solving a linear least squares problem per iteration. Extensive numerical experiments show that the algorithm can reliably solve a wide range of problems at a speed at least several times faster than many nuclear-norm minimization algorithms. In addition, convergence of this nonlinear SOR algorithm to a stationary point is analyzed.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Japan)

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. Beck A., Teboulle M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2, 183–202 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  2. Candès E., Plan Y.: Matrix completion with noise. Proc. IEEE 98, 925–936 (2010)

    Article  Google Scholar 

  3. Candès, E.J., Recht, B.: Exact matrix completion via convex optimization. Found. Comput. Math. (2009)

  4. Candès E.J., Tao T.: The power of convex relaxation near-optimal matrix completion. IEEE Trans. Inf. Theory 56, 2053–2080 (2010)

    Article  Google Scholar 

  5. Chan T.F.: Rank revealing QR factorizations. Linear Algebra Appl. 88(89), 67–82 (1987)

    MathSciNet  Google Scholar 

  6. Chan T.F., Hansen P.C.: Low-rank revealing QR factorizations. Numer. Linear Algebra Appl. 1, 33–44 (1994)

    Article  MathSciNet  MATH  Google Scholar 

  7. Dai, W., Milenkovic, O.: Set an algorithm for consistent matrix completion CoRR. abs/0909.2705 (2009)

  8. Eldén L.: Matrix Methods in Data Mining and Pattern Recognition (Fundamentals of Algorithms). Society for Industrial and Applied Mathematics, Philadelphia (2007)

    Book  Google Scholar 

  9. Goldberg K., Roeder T., Gupta D., Perkins C.: Eigentaste A constant time collaborative filtering algorithm. Inf. Retr. 4, 133–151 (2001)

    Article  MATH  Google Scholar 

  10. Goldfarb, D., Ma, S., Wen, Z.: Solving low-rank matrix completion problems efficiently. In: Proceedings of the 47th Annual Allerton Conference on Communication, Control, and Computing, Allerton’09, pp. 1013–1020 (2009)

  11. Golub G.H., Van Loan C.F.: Matrix computations. In: Johns Hopkins Studies in the Mathematical Sciences, 3rd edn. Johns Hopkins University Press, Baltimore (1996)

    Google Scholar 

  12. Grippo L., Sciandrone M.: On the convergence of the block nonlinear Gauss–Seidel method under convex constraints. Oper. Res. Lett. 26, 127–136 (2000)

    Article  MathSciNet  MATH  Google Scholar 

  13. Gross, D.: Recovering low-rank matrices from few coefficients in any basis, tech. rep. Leibniz University (2009)

  14. Herlocker, J.L., Konstan, J.A., Borchers, A., Riedl, J.: An algorithmic framework for performing collaborative filtering. In: SIGIR ’99: Proceedings of the 22nd annual international ACM SIGIR Conference on Research and Development in Information Retrieval, pp. 230–237. ACM, New York (1999)

  15. Jian-Feng C., Candes E.J., Zuowei S.: A singular value thresholding algorithm for matrix completion export. SIAM J. Optim. 20, 1956–1982 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  16. Keshavan R.H., Montanari A., Oh S.: Matrix completion from a few entries. IEEE Trans. Inform. Theory 56, 2980–2998 (2010)

    Article  MathSciNet  Google Scholar 

  17. Keshavan R.H., Montanari A., Oh S.: Matrix completion from noisy entries. J. Mach. Learn. Res. 99, 2057–2078 (2010)

    MathSciNet  Google Scholar 

  18. Keshavan, R.H., Oh, S.: A gradient descent algorithm on the grassman manifold for matrix completion, tech. rep., Dept. of Electrical Engineering, Stanford University (2009)

  19. Larsen, R.M.: PROPACK Software for large and sparse svd calculations. http://soi.stanford.edu/rmunk/PROPACK

  20. Lee K., Bresler Y.: Admira atomic decomposition for minimum rank approximation. IEEE Trans. Inf. Theor. 56, 4402–4416 (2010)

    Article  MathSciNet  Google Scholar 

  21. Liu Y.-J., Sun D., Toh K.-C.: An implementable proximal point algorithmic framework for nuclear norm minimization. Math. Program. 133(1–2), 399–436 (2011)

    MathSciNet  Google Scholar 

  22. Liu Z., Vandenberghe L.: Interior-point method for nuclear norm approximation with application to system identification. SIAM J. Matrix Anal. Appl. 31, 1235–1256 (2009)

    Article  MathSciNet  Google Scholar 

  23. Luo Q.Z., Tseng P.: On the convergence of the coordinate descent method for convex differentiable minimization. J. Optim. Theory Appl. 72, 7–35 (1992)

    Article  MathSciNet  MATH  Google Scholar 

  24. Ma S., Goldfarb D., Chen L.: Fixed point and bregman iterative methods for matrix rank minimization. Math. Program. 128(1–2), 321–353 (2009)

    MathSciNet  Google Scholar 

  25. Mazumder R., Hastie T., Tibshirani R.: Regularization methods for learning incomplete matrices. Stanford University, tech. rep. (2009)

    Google Scholar 

  26. Meka, R., Jain, P., Dhillon, I.S.: Guaranteed rank minimization via singular value projection. CoRR, abs/0909.5457 (2009)

  27. Morita T., Kanade T.: A sequential factorization method for recovering shape and motion from image streams. IEEE Trans. Pattern Anal. Mach. Intell. 19, 858–867 (1997)

    Article  Google Scholar 

  28. Nocedal J., Wright S.J.: Numerical Optimization. Springer Series in Operations Research and Financial Engineering. Springer, Berlin (2006)

    Google Scholar 

  29. Recht, B.: A simpler approach to matrix completion. J. Mach. Learn. Res. (2010)

  30. Recht B., Fazel M., Parrilo P.A.: Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization. SIAM Rev. 52, 471–501 (2010)

    Article  MathSciNet  MATH  Google Scholar 

  31. Shen, Y., Wen, Z., Zhang, Y.: Augmented lagrangian alternating direction method for matrix separation based on low-rank factorization, tech. rep. Rice University (2010)

  32. Stewart G.W.: On the continuity of the generalized inverse. SIAM J. Appl. Math. 17, 33–45 (1969)

    Article  MathSciNet  MATH  Google Scholar 

  33. Toh K.-C., Yun S.: An accelerated proximal gradient algorithm for nuclear norm regularized least squares problems. Pacific J. Optim. 6, 615–640 (2010)

    MathSciNet  MATH  Google Scholar 

  34. Tomasi C., Kanade T.: Shape and motion from image streams under orthography: a factorization method. Int. J. Comput. Vis. 9, 137–154 (1992)

    Article  Google Scholar 

  35. Tseng P.: Dual ascent methods for problems with strictly convex costs and linear constraints: a unified approach. SIAM J. Control Optim. 28, 214–242 (1990)

    Article  MathSciNet  MATH  Google Scholar 

  36. Tseng P.: Convergence of a block coordinate descent method for nondifferentiable minimization. J. Optim. Theory Appl. 109, 475–494 (2001)

    Article  MathSciNet  MATH  Google Scholar 

  37. Xu, Y., Yin, W., Wen, Z., Zhang, Y.: An alternating direction algorithm for matrix completion with nonnegative factors. tech. rep., Shanghai Jiaotong University (2011)

  38. Yang, J., Yuan, X.: An inexact alternating direction method for trace norm regularized least squares problem. tech. rep., Dept. of Mathematics. Nanjing University (2010)

  39. Yuan, X., Yang, J.: Sparse and low-rank matrix decomposition via alternating direction methods. tech. rep. Dept. of Mathematics, Hong Kong Baptist University (2009)

  40. Zhang, Y.: LMaFit Low-rank matrix fitting (2009). http://www.caam.rice.edu/optimization/L1/LMaFit/

  41. Zhang, Y.: An alternating direction algorithm for nonnegative matrix factorization. tech. rep. Rice University (2010)

  42. Zhu, Z., So, A.M.-C., Ye, Y.: Fast and near-optimal matrix completion via randomized basis pursuit, tech. rep. Stanford University (2009)

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics and Institute of Natural Sciences, Shanghai Jiaotong University, Shanghai, China

    Zaiwen Wen

  2. Department of Computational and Applied Mathematics, Rice University, Houston, TX, 77005, USA

    Wotao Yin & Yin Zhang

Authors
  1. Zaiwen Wen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Wotao Yin
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Yin Zhang
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Zaiwen Wen.

Additional information

Z. Wen’s research was supported in part by NSF DMS-0439872 through UCLA IPAM and the NSFC grant 11101274.

W. Yin’s research was supported in part by NSF CAREER Award DMS-07-48839, ONR Grant N00014-08-1-1101, and an Alfred P. Sloan Research Fellowship.

Y. Zhang’s research was supported in part by NSF grants DMS-0405831 and DMS-0811188 and ONR grant N00014-08-1-1101.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Wen, Z., Yin, W. & Zhang, Y. Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm. Math. Prog. Comp. 4, 333–361 (2012). https://doi.org/10.1007/s12532-012-0044-1

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s12532-012-0044-1

Keywords

Mathematics Subject Classification (2000)

Search

Navigation