Journal Home > Volume 1 , issue 4

In recent years, the recommendation systems have become increasingly popular and have been used in a broad variety of applications. Here, we investigate the matrix completion techniques for the recommendation systems that are based on collaborative filtering. The collaborative filtering problem can be viewed as predicting the favorability of a user with respect to new items of commodities. When a rating matrix is constructed with users as rows, items as columns, and entries as ratings, the collaborative filtering problem can then be modeled as a matrix completion problem by filling out the unknown elements in the rating matrix. This article presents a comprehensive survey of the matrix completion methods used in recommendation systems. We focus on the mathematical models for matrix completion and the corresponding computational algorithms as well as their characteristics and potential issues. Several applications other than the traditional user-item association prediction are also discussed.


menu
Abstract
Full text
Outline
About this article

A Survey of Matrix Completion Methods for Recommendation Systems

Show Author's information Andy RamlatchanMengyun YangQuan LiuMin LiJianxin WangYaohang Li( )
NASA Langley Research Center, Hampton, VA 23666, USA and the Department of Computer Science, Old Dominion University, Norfolk, VA 23666, USA.
Department of Computer Science, Central South University, Changsha 410083, China and the Department of Science, Shaoyang University, Shaoyang 422000, China.
Department of Computer Science, Central South University, Changsha 410083, China.
Department of Computer Science, Old Dominion University, Norfolk, VA 23529, USA.

Abstract

In recent years, the recommendation systems have become increasingly popular and have been used in a broad variety of applications. Here, we investigate the matrix completion techniques for the recommendation systems that are based on collaborative filtering. The collaborative filtering problem can be viewed as predicting the favorability of a user with respect to new items of commodities. When a rating matrix is constructed with users as rows, items as columns, and entries as ratings, the collaborative filtering problem can then be modeled as a matrix completion problem by filling out the unknown elements in the rating matrix. This article presents a comprehensive survey of the matrix completion methods used in recommendation systems. We focus on the mathematical models for matrix completion and the corresponding computational algorithms as well as their characteristics and potential issues. Several applications other than the traditional user-item association prediction are also discussed.

Keywords:

matrix completion, collaborative filtering, recommendation systems
Received: 21 January 2018 Accepted: 20 March 2018 Published: 02 July 2018 Issue date: December 2018
References(80)
[1]
T. Hofmann, Latent semantic models for collaborative filtering, ACM Trans. Inf. Syst., vol. 22, no. 1, pp. 89-115, 2004.
[2]
T. Hofmann, Unsupervised learning by probabilistic latent semantic analysis, Mach. Learn., vol. 42, nos. 1&2, pp. 177-196, 2001.
[3]
C. D. Charalambous and A. Logothetis, Maximum likelihood parameter estimation from incomplete data via the sensitivity equations: The continuous-time case, IEEE Trans. Automat. Control, vol. 45, no. 5, pp. 928-934, 2000.
[4]
A. P. Dempster, N. M. Laird, and D. B. Rubin, Maximum likelihood from incomplete data via the EM algorithm, J. Roy. Stat. Soc. Ser B Methodol., vol. 39, no. 1, pp. 1-38, 1977.
[5]
R. M. Neal and G. E. Hinton, A View of the EM Algorithm That Justifies Incremental, Sparse, and Other Variants. Norwell, MA, USA: Kluwer, 1998.
[6]
H. T. Zhu, Z. Khondker, Z. H. Lu, and J. G. Ibrahim, Bayesian generalized low rank regression models for neuroimaging phenotypes and genetic markers, J. Am. Stat. Assoc., vol. 109, no. 507, pp. 977-990, 2014.
[7]
S. N. Wood, Low-rank scale-invariant tensor product smooths for generalized additive mixed models, Biometrics, vol. 62, no. 4, pp. 1025-1036, 2006.
[8]
H. M. Luo, M. Li, S. K. Wang, Q. Liu, Y. H. Li, and J. X. Wang, Computational drug repositioning using low-rank matrix approximation and randomized algorithms, Bioinformatics, vol. 34, no. 11, 1904-1912, 2018.
[9]
C. Q. Lu, M. Y. Yang, F. Luo, F. X. Wu, M. Li, Y. Pan, Y. H. Li, and J. X. Wang, Prediction of lncRNA-disease associations based on inductive matrix completion, Bioinformatics, .
[10]
Y. Liang, D. L. Wu, G. R. Liu, Y. H. Li, C. L. Gao, Z. J. Ma, and W. D. Wu, Big data-enabled multiscale serviceability analysis for aging bridges, Digit. Commun. Netw., vol. 2, no. 3, pp. 97-107, 2016.
[11]
J. Bobadilla, F. Ortega, A. Hernando, and A. Gutiérrez, Recommender systems survey, Knowl. Based Syst., vol. 46, pp. 109-132, 2013.
[12]
M. Kunaver and T. Požrl, Diversity in recommender systems — A survey, Knowl. Based Syst., vol. 123, pp. 154-162, 2017.
[13]
R. Burke, Hybrid recommender systems: Survey and experiments, User Model. User-Adapt. Interact., vol. 12, no. 4, pp. 331-370, 2002.
[14]
C. Desrosiers and G. Karypis, A comprehensive survey of neighborhood-based recommendation methods, in Recommender Systems Handbook. Springer, 2010, pp. 107-144.
[15]
C. He, D. Parra, and K. Verbert, Interactive recommender systems: A survey of the state of the art and future research challenges and opportunities, Expert Syst. Appl., vol. 56, pp. 9-27, 2016.
[16]
P. G. Campos, F. Díez, and I. Cantador, Time-aware recommender systems: A comprehensive survey and analysis of existing evaluation protocols, User Model. User-Adapt. Interact., vol. 24, no. 1-2, pp. 67-119, 2014.
[17]
X. W. Yang, Y. Guo, Y. Liu, and H. Steck, A survey of collaborative filtering based social recommender systems, Comput. Commun., vol. 41, pp. 1-10, 2014.
[18]
A. Klašnja-Milicevic, M. Ivanovic, and A. Nanopoulos, Recommender systems in e-learning environments: A survey of the state-of-the-art and possible extensions, Artif. Intell. Rev., vol. 44, no. 4, pp. 571-604, 2015.
[19]
R. Yera and L. Martínez, Fuzzy tools in recommender systems: A survey, Int. J. Comput. Intell. Syst., vol. 10, no. 1, pp. 776-803, 2017.
[20]
D. Kotkov, S. Q. Wang, and J. Veijalainen, A survey of serendipity in recommender systems, Knowl. Based Syst., vol. 111, pp. 180-192, 2016.
[21]
E. J. Candes and T. Tao, The power of convex relaxation: Near-optimal matrix completion, IEEE Trans. Inf. Theory, vol. 56, no. 5, pp. 2053-2080, 2010.
[22]
M. Udell, C. Horn, R. Zadeh, and S. Boyd, Generalized low rank models, Found. Trends® Mach. Learn., vol. 9, no. 1, pp. 1-118, 2016.
[23]
Y. Koren, R. Bell, and C. Volinsky, Matrix factorization techniques for recommender systems, Computer, vol. 42, no. 8, pp. 30-37, 2009.
[24]
B. M. Sarwar, G. Karypis, J. A. Konstan, and J. T. Riedl, Application of dimensionality reduction in recommender system-a case study, in Proc. ACM WebKDD Web Mining for E-Commerce Workshop, 2000.
[25]
B. Sarwar, G. Karypis, J. Konstan, and J. Riedl, Incremental singular value decomposition algorithms for highly scalable recommender systems, in Proc. 6th Int. Conf. on Computers and Information Technology, 2002.
[26]
D. Billsus and M. J. Pazzani, Learning collaborative information filters, in Proc. 15th Int. Conf. on Machine Learning, San Francisco, CA, USA: ACM, 1998.
[27]
A. Paterek, Improving regularized singular value decomposition for collaborative filtering, in Proc. KDD and Workshop, San Jose, CA, USA, 2007.
[28]
J. D. M. Rennie and N. Srebro, Fast maximum margin matrix factorization for collaborative prediction, in Proc. 22nd Int. Conf. on Machine Learning, Bonn, Germany, 2005.
[29]
M. G. Vozalis and K. G. Margaritis, Using SVD and demographic data for the enhancement of generalized collaborative filtering, Inf. Sci., vol. 177, no. 15, pp. 3017-3037, 2007.
[30]
Y. Koren, Factorization meets the neighborhood: A multifaceted collaborative filtering model, in Proc. 14th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, Las Vegas, NV, USA, 2008.
[31]
B. Hallinan and T. Striphas, Recommended for you: The NETflix prize and the production of algorithmic culture, New Media Soc., vol. 18, no. 1, pp. 117-137, 2016.
[32]
Y. C. Ji, W. X. Hong, Y. L. Shangguan, H. Wang, and J. Ma, Regularized singular value decomposition in news recommendation system, in Proc. 11th Int. Conf. on Computer Science & Education, Nagoya, Japan, 2016, pp. 621-626.
[33]
R. Mazumder, T. Hastie, and R. Tibshirani, Spectral regularization algorithms for learning large incomplete matrices, J. Mach. Learn. Res., vol. 11, pp. 2287-2322, 2010.
[34]
M. Kagie, M. van der Loos, and M. van Wezel, Including item characteristics in the probabilistic latent semantic analysis model for collaborative filtering, AI Commun., vol. 22, no. 4, pp. 249-265, 2009.
[35]
J. F. Cai, E. J. Candes, and Z. W. Shen, A singular value thresholding algorithm for matrix completion, SIAM J. Optim., vol. 20, no. 4, pp. 1956-1982, 2010.
[36]
E. Candès and B. Recht, Simple bounds for recovering low-complexity models, Math. Program., vol. 141, nos. 1&2, pp. 577-589, 2013.
[37]
B. Recht, M. Fazel, and P. A. Parrilo, Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev, vol. 52, no. 3, pp. 471-501, 2010.
[38]
Z. W. Wen, W. T. Yin, and Y. Zhang, Solving a low-rank factorization model for matrix completion by a nonlinear successive over-relaxation algorithm, Math. Program. Comput., vol. 4, no. 4, pp. 333-361, 2012.
[39]
R. Salakhutdinov and A. Mnih, Bayesian probabilistic matrix factorization using Markov chain Monte Carlo, in Proc. 25th Int. Conf. on Machine Learning, Helsinki, Finland, 2008.
[40]
D. Agarwal and B. C. Chen, Regression-based latent factor models, in Proc. 15th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, Paris, France, 2009.
[41]
D. M. Blei, A. Y. Ng, and M. I. Jordan, Latent Dirichlet allocation, J. Mach. Learn. Res., vol. 3, pp. 993-1022, 2003.
[42]
J. Canny, Collaborative filtering with privacy via factor analysis, in Proc. 25th Annu. Int. ACM SIGIR Conf. on Research and Development in Information Retrieval, Tampere, Finland, 2002.
[43]
R. R. Salakhutdinov, A. Mnih, and G. E. Hinton, Restricted boltzmann machines for collaborative filtering, in Proc. 24th Int. Conf. on Machine Learning, Corvallis, OR, USA, 2007.
[44]
F. F. Xu and P. Pan, A new algorithm for positive semidefinite matrix completion, J. Appl. Math., vol. 2016, p. 1659019, 2016.
[45]
T. Hastie, R. Mazumder, J. D. Lee, and R. Zadeh, Matrix completion and low-rank svd via fast alternating least squares, J. Mach. Learn. Res., vol. 16, no. 1, pp. 3367-3402, 2015.
[46]
J. F. Cai, R. H. Chan, and Z. W. Shen, A framelet-based image inpainting algorithm, Appl. Computat. Harmon. Anal., vol. 24, no. 2, pp. 131-149, 2008.
[47]
P. L. Combettes and V. R. Wajs, Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul., vol. 4, no. 4, pp. 1168-1200, 2005.
[48]
I. Daubechies, M. Defrise, and C. De Mol, An iterative thresholding algorithm for linear inverse problems with a sparsity constraint, Commun. Pure Appl. Math., vol. 57, no. 11, pp. 1413-1457, 2004.
[49]
E. T. Hale, W. T. Yin, and Y. Zhang, Fixed-point continuation for ℓ1-minimization: Methodology and convergence, SIAM J Optim., vol. 19, no. 3, pp. 1107-1130, 2008.
[50]
B. S. He, H. Yang, and S. L. Wang, Alternating direction method with self-adaptive penalty parameters for monotone variational inequalities, J. Optim. Theory Appl., vol. 106, no. 2, pp. 337-356, 2000.
[51]
D. Gabay and B. Mercier, A dual algorithm for the solution of nonlinear variational problems via finite element approximation, Comput. Math. Appl., vol. 2, no. 1, pp. 17-40, 1976.
[52]
R. Glowinski, Numerical Methods for Nonlinear Variational Problems. Springer, 1984.
[53]
R. Glowinski and P. Le Tallec, Augmented Lagrangian and Operator Splitting Methods in Nonlinear Mechanics. Philadelphia, PA, USA: SIAM, 1989, pp. 9.
[54]
F. Xu and G. He, New algorithms for nonnegative matrix completion, Pac. J. Optim., vol. 11, no. 3, pp. 459-469, 2015.
[55]
Y. Y. Xu, W. T. Yin, Z. W. Wen, and Y. Zhang, An alternating direction algorithm for matrix completion with nonnegative factors, Front. Math. China, vol. 7, no. 2, pp. 365-384, 2012.
[56]
C. H. Chen, B. S. He, and X. M. Yuan, Matrix completion via an alternating direction method, IMA J. Numer. Anal., vol. 32, no. 1, pp. 227-245, 2012.
[57]
J. F. Cai and S. Osher, Fast singular value thresholding without singular value decomposition, Methods Appl. Anal., vol. 20, no. 4, pp. 335-352, 2013.
[58]
N. Halko, P. G. Martinsson, and J. A. Tropp, Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, SIAM Rev., vol. 53, no. 2, pp. 217-288, 2011.
[59]
H. Ji, W. J. Yu, and Y. H. Li, A rank revealing randomized singular value decomposition (R3SVD) algorithm for low-rank matrix approximations, arXiv: 1605.08134, 2016.
[60]
W. J. Yu, Y. Gu, J. Li, S. H. Liu, and Y. H. Li, Single-pass PCA of large high-dimensional data, in Proc. 26th Int. Joint Conf. on Artificial Intelligence, Catalina Island, CA, USA, 2010.
[61]
Y. H. Li and W. J. Yu, A fast implementation of singular value thresholding algorithm using recycling rank revealing randomized singular value decomposition, arXiv: 1704.05528, 2017.
[62]
K. C. Toh and S. Yun, An accelerated proximal gradient algorithm for nuclear norm regularized linear least squares problems, Pac. J. Optim., vol. 6, no. 3, pp. 615-640, 2010.
[63]
S. Q. Ma, D. Goldfarb, and L. F. Chen, Fixed point and bregman iterative methods for matrix rank minimization, Math. Program., vol. 128, no. 1-2, pp. 321-353, 2011.
[64]
Y. Koren and R. Bell, Advances in collaborative filtering, in Recommender Systems Handbook, F. Ricci, L. Rokach, B. Shapira, and P. B. Kantor, eds. Springer, 2011.
[65]
G. Takács, I. Pilászy, B. Németh, and D. Tikk, Matrix factorization and neighbor based algorithms for the NETflix prize problem, in Proc. 2008 ACM Conf. on Recommender Systems, Lausanne, Switzerland, 2008, pp. 267-274.
[66]
C. B. Do and S. Batzoglou, What is the expectation maximization algorithm? Nat. Biotechnol., vol. 26, no. 8, pp. 897-899, 2008.
[67]
H. Ji, E. O’Saben, A. Boudion, and Y. H. Li, March madness prediction: A matrix completion approach, in Proc. Modeling, Simulation, and Visualization Student Capstone Conf., Suffolk, UA, USA, 2015.
[68]
H. Ji, E. O’Saben, R. Lambi, and Y. H. Li, Matrix completion based model v2.0: Predicting the winning probabilities of march madness matches, in Proc. Modeling, Simulation, and Visualization Student Capstone Conf., Suffolk, VA, USA, 2016.
[69]
X. R. Zhang and H. S. Wang, Study on recommender systems for business-to-business electronic commerce, Commun. IIMA, vol. 5, no. 4, pp. 53-61, 2005.
[70]
T. P. Exarchos, C. Papaloukas, C. Lampros, and D. I. Fotiadis, Mining sequential patterns for protein fold recognition, J. Biomed. Inf., vol. 41, no. 1, pp. 165-179, 2008.
[71]
A. Kapur, K. Marwah, and G. Alterovitz, Gene expression prediction using low-rank matrix completion, BMC Bioinform., vol. 17, pp. 243, 2016.
[72]
D. Shin, S. Cetintas, K. C. Lee, and I. S. Dhillon, Tumblr blog recommendation with boosted inductive matrix completion, in Proc. 24th ACM Int. on Conf. on Information and Knowledge Management, Melbourne, Australia, 2015.
[73]
T. Mikolov, K. Chen, G. Corrado, and J. Dean, Efficient estimation of word representations in vector space, in Proc. Workshop at Int. Conf. on Learning Representations, Scottsdale, AZ, USA, 2013.
[74]
J. Liu, P. Musialski, P. Wonka, and J. P. Ye, Tensor completion for estimating missing values in visual data, IEEE Trans. Pattern Anal. Mach. Intell., vol. 35, no. 1, pp. 208-220, 2013.
[75]
L. Z. Cui, P. Ou, X. H. Fu, Z. K. Wen, and N. Lu, A novel multi-objective evolutionary algorithm for recommendation systems, J. Parallel Distrib. Comput., vol. 103, pp. 53-63, 2017.
[76]
K. Deb, Multi-objective optimization. in Search Methodologies, E. K. Burke and G. Kendall, eds. Springer, 2005.
[77]
Y. H. Li, MOMCMC: An efficient Monte Carlo method for multi-objective sampling over real parameter space, Comput. Math. Appl., vol. 64, no. 11, pp. 3542-3556, 2012.
[78]
W. H. Zhu, A. Yaseen, and Y. H. Li, DEMCMC-GPU: An efficient multi-objective optimization method with GPU acceleration on the fermi architecture, New Generat. Comput., vol. 29, no. 2, pp. 163-184, 2011.
[79]
B. Recht and C. Ré, Parallel stochastic gradient algorithms for large-scale matrix completion, Math. Program. Comput., vol. 5, no. 2, pp. 201-226, 2013.
[80]
Y. Y. Xu, R. R. Hao, W. T. Yin, and Z. X. Su, Parallel matrix factorization for low-rank tensor completion, Inverse Probl. Imaging, vol. 9, no. 2, pp. 601-624, 2015.
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Received: 21 January 2018
Accepted: 20 March 2018
Published: 02 July 2018
Issue date: December 2018

Copyright

© The author(s) 2018

Acknowledgements

This work was supported in part by the National Natural Science Foundation of China (Nos. 61728211 and 1066471).

Rights and permissions

Reprints and Permission requests may be sought directly from editorial office.

Return