Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm. (English) Zbl 1271.65083

The matrix completion problem is to recover a low-rank matrix from a subset of its entries. The authors propose a low-rank factorization model and construct a nonlinear succesive over-relaxation algorithm that only requires solving a linear least squares problem per iteration. Numerical experiments show that the algorithm can reliable solve a wide range of problems.


65F30 Other matrix algorithms (MSC2010)
15A83 Matrix completion problems
15A23 Factorization of matrices
65F10 Iterative numerical methods for linear systems
65F20 Numerical solutions to overdetermined systems, pseudoinverses
Full Text: DOI


[1] Beck A., Teboulle M.: A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2, 183–202 (2009) · Zbl 1175.94009
[2] Candès E., Plan Y.: Matrix completion with noise. Proc. IEEE 98, 925–936 (2010)
[3] Candès, E.J., Recht, B.: Exact matrix completion via convex optimization. Found. Comput. Math. (2009) · Zbl 1219.90124
[4] Candès E.J., Tao T.: The power of convex relaxation near-optimal matrix completion. IEEE Trans. Inf. Theory 56, 2053–2080 (2010) · Zbl 1366.15021
[5] Chan T.F.: Rank revealing QR factorizations. Linear Algebra Appl. 88(89), 67–82 (1987) · Zbl 0624.65025
[6] Chan T.F., Hansen P.C.: Low-rank revealing QR factorizations. Numer. Linear Algebra Appl. 1, 33–44 (1994) · Zbl 0804.65027
[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) · Zbl 1120.68092
[9] Goldberg K., Roeder T., Gupta D., Perkins C.: Eigentaste A constant time collaborative filtering algorithm. Inf. Retr. 4, 133–151 (2001) · Zbl 0989.68052
[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) · Zbl 0865.65009
[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) · Zbl 0955.90128
[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) · Zbl 1201.90155
[16] Keshavan R.H., Montanari A., Oh S.: Matrix completion from a few entries. IEEE Trans. Inform. Theory 56, 2980–2998 (2010) · Zbl 1242.62069
[17] Keshavan R.H., Montanari A., Oh S.: Matrix completion from noisy entries. J. Mach. Learn. Res. 99, 2057–2078 (2010) · Zbl 1242.62069
[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) · Zbl 1366.94112
[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) · Zbl 1262.90125
[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) · Zbl 1201.90151
[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) · Zbl 0795.90069
[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) · Zbl 1221.65146
[25] Mazumder R., Hastie T., Tibshirani R.: Regularization methods for learning incomplete matrices. Stanford University, tech. rep. (2009) · Zbl 1242.68237
[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) · Zbl 05112142
[28] Nocedal J., Wright S.J.: Numerical Optimization. Springer Series in Operations Research and Financial Engineering. Springer, Berlin (2006)
[29] Recht, B.: A simpler approach to matrix completion. J. Mach. Learn. Res. (2010) · Zbl 1280.68141
[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) · Zbl 1198.90321
[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) · Zbl 0172.03801
[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) · Zbl 1205.90218
[34] Tomasi C., Kanade T.: Shape and motion from image streams under orthography: a factorization method. Int. J. Comput. Vis. 9, 137–154 (1992)
[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) · Zbl 0692.49025
[36] Tseng P.: Convergence of a block coordinate descent method for nondifferentiable minimization. J. Optim. Theory Appl. 109, 475–494 (2001) · Zbl 1006.65062
[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)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.