×

An ADMM-factorization algorithm for low rank matrix completion. (English) Zbl 1433.65112

Summary: In this paper, we propose an Alternating Direction Method of Multipliers (ADMM) based algorithm that is taking advantage of factorization for the fixed rank matrix completion problem. The convergence of the proposed algorithm to the KKT point is discussed. Finally, on several classes of test problems, its efficiency is compared with several efficient algorithms from the literature.

MSC:

65K05 Numerical mathematical programming methods
15A83 Matrix completion problems
15A18 Eigenvalues, singular values, and eigenvectors
90C25 Convex programming

Software:

MovieLens
PDFBibTeX XMLCite
Full Text: Link

References:

[1] Argyriou, A., Evgeniou, T. and Pontil, M. (2008). Convex multi-task feature learning, Machine Learning, Vol. 73, No. 3, pp. 243-272. · Zbl 1470.68073
[2] Cai, J., Candes, E. J. and Shen, Z. (2010). A singular value thresholding algorithm for matrix completion, SIAM Journal on Optimization, Vol. 20, No. 4, pp. 1956-1982. · Zbl 1201.90155
[3] Candès, E. J. and Recht, B. (2009). Exact matrix completion via convex optimization, Foundations of Computational Mathematics, Vol. 9, No. 6, pp. 717-772. · Zbl 1219.90124
[4] Candès, E. J. and Tao, T. (2010). Exact matrix completion via convex optimization, IEEE Transactions on Information Theory, Vol. 56, No. 5, pp. 2053-2080. · Zbl 1366.15021
[5] Eldèn, L. (2007).Matrix methods in data mining and pattern recognition, SIAM. · Zbl 1120.68092
[6] Harper, F. M. and Konstan, J. A. (2016). The movielens datasets: History and context, ACM Transactions on Interactive Intelligent Systems, Vol. 5, No. 4, pp. 19.
[7] Huang, S. and Wolkowicz, H. (2018). Low-rank matrix completion using nuclear norm minimization and facial reduction, Journal of Global Optimization, Vol. 72, No. 1, pp. 5-26. · Zbl 1475.65036
[8] Keshavan, R. H., Montanari, A. and Oh, S. (2010). Matrix completion from a few entries, IEEE Transactions on Information Theory, Vol. 56, No. 6, pp. 2980-2998. · Zbl 1366.62111
[9] Liu, Z. and Vandenberghe, L. (2009). Interior-point method for nuclear norm approximation with application to system identification, SIAM Journal on Matrix Analysis and Applications, Vol. 31, No. 3, pp. 1235-1256. · Zbl 1201.90151
[10] Ma, S., Goldfarb, D. and Chen, L. (2011). Fixed point and Bregman iterative methods for matrix rank minimization, Mathematical Programming, Vol. 128, No. 1-2, pp. 321-353. · Zbl 1221.65146
[11] Ng, M. K., Weiss, P. and Yuan, X. (2010). Solving constrained total-variation image restoration and reconstruction problems via alternating direction methods, SIAM Journal on Scientific Computing, Vol. 32, No. 5, pp. 2710-2736. · Zbl 1217.65071
[12] Ngo, T. and Saad, Y. (2012). Scaled gradients on Grassmann manifolds for matrix completion, Advances in Neural Information Processing Systems, pp. 1412-1420.
[13] Obozinski, G., Taskar, B. and Jordan, M. I. (2010). Joint covariate selection and joint subspace selection for multiple classification problems, Statistics and Computing, Vol. 20, No. 2, pp. 231-252.
[14] Rennie, J. and Srebro, N. (2005). Fast maximum margin matrix factorization for collaborative prediction, Proceedings of the 22nd International Conference on Machine Learning, pp. 713- 719.
[15] Ruchansky, N. (2016).Matrix Completion with Structure, Ph.D. thesis, Boston University.
[16] Salahi, M. and Taati, A. (2017). Alternating direction method of multipliers for the extended trust region subproblem, Iranian Journal of Numerical Analysis and Optimization, Vol. 7, No. 1, pp. 107-117. · Zbl 1372.65182
[17] Steidl, G. and Teuber, T. (2010). Removing multiplicative noise by Douglas-Rachford splitting methods, Journal of Mathematical Imaging and Vision, Vol. 36, No. 2, pp. 168-184. · Zbl 1287.94016
[18] Tanner, J. and Wei, K. (2016). Low rank matrix completion by alternating steepest descent methods, Applied and Computational Harmonic Analysis, Vol. 40, No. 2, pp. 417-429. · Zbl 1336.65047
[19] Taleghani, R. and Salahi, M. (2018). Low rank matrix completion problem by alternating direction method of multipliers, Advanced Modeling and Optimization, Vol. 20, No. 2, pp. 419-428. · Zbl 1438.15065
[20] Toh, K. and Yun, S. (2010). An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems, Pacific Journal of Optimization, Vol. 6, No. 15, pp. 615-640. · Zbl 1205.90218
[21] Vandenberghe, L. and Boyd, S. (1996). Semidefinite programming, SIAM Review, Vol. 38, No. 1, pp. 49-95. · Zbl 0845.65023
[22] Vandereycken, B. (2013). Low-rank matrix completion by Riemannian optimization, SIAM Journal on Optimization, Vol. 23, No. 2, pp. 1214-1236. · Zbl 1277.15021
[23] Wang, C. and Li, C. (2015). A mean value algorithm for Toeplitz matrix completion, Applied Mathematics Letters, Vol. 41, pp. 35-40. · Zbl 1312.15037
[24] Wang, Q., Cao, W. and Jin, Z. (2015). Two-Step Proximal Gradient Algorithm for Low-Rank Matrix Completion, Statistics, Optimization & Information Computing, Vol. 4, No. 2, pp. 174-182.
[25] Wen, Z., Yin, W. and Zhang, Y. (2012). Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm, Mathematical Programming Computation, Vol. 4, No. 4, pp. 333-361. · Zbl 1271.65083
[26] Xiao, Y., Wu, S. and Li, D. (2013). Splitting and linearizing augmented Lagrangian algorithm for subspace recovery from corrupted observations, Advances in Computational Mathematics, Vol. 38, No. 4, pp. 837-858. · Zbl 1269.65057
[27] Xu, Y., Yin, W., Wen, Z. and Zhang, Y. (2012). An alternating direction algorithm for matrix completion with nonnegative factors, Frontiers of Mathematics in China, Vol. 7, No. 2, pp. 365-384. · Zbl 1323.65044
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.