AI Chat Paper
Note: Please note that the following content is generated by AMiner AI. SciOpen does not take any responsibility related to this content.
{{lang === 'zh_CN' ? '文章概述' : 'Summary'}}
{{lang === 'en_US' ? '中' : 'Eng'}}
Chat more with AI
Powered by AMiner. Clicking this button will take you away from SciOpen.
Home Big Data Mining and Analytics Article
PDF (354 KB)
Cite
EndNote(RIS) BibTeX
Collect
Submit Manuscript AI Chat Paper
Show Outline
Outline
Show full outline
Hide outline
Outline
Show full outline
Hide outline
Open Access

A Survey of Matrix Completion Methods for Recommendation Systems

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.
Show Author Information

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 completioncollaborative filteringrecommendation systems

References

[1]
T. Hofmann, Latent semantic models for collaborative filtering, ACM Trans. Inf. Syst., vol. 22, no. 1, pp. 89-115, 2004.
Crossref Google Scholar
[2]
T. Hofmann, Unsupervised learning by probabilistic latent semantic analysis, Mach. Learn., vol. 42, nos. 1&2, pp. 177-196, 2001.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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, .
Crossref Google Scholar
[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.
Crossref Google Scholar
[11]
J. Bobadilla, F. Ortega, A. Hernando, and A. Gutiérrez, Recommender systems survey, Knowl. Based Syst., vol. 46, pp. 109-132, 2013.
Crossref Google Scholar
[12]
M. Kunaver and T. Požrl, Diversity in recommender systems — A survey, Knowl. Based Syst., vol. 123, pp. 154-162, 2017.
Crossref Google Scholar
[13]
R. Burke, Hybrid recommender systems: Survey and experiments, User Model. User-Adapt. Interact., vol. 12, no. 4, pp. 331-370, 2002.
Crossref Google Scholar
[14]
C. Desrosiers and G. Karypis, A comprehensive survey of neighborhood-based recommendation methods, in Recommender Systems Handbook. Springer, 2010, pp. 107-144.
Crossref
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[23]
Y. Koren, R. Bell, and C. Volinsky, Matrix factorization techniques for recommender systems, Computer, vol. 42, no. 8, pp. 30-37, 2009.
Crossref Google Scholar
[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.
Crossref
[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.
Crossref
[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.
Crossref Google Scholar
[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.
Crossref
[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.
Crossref Google Scholar
[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.
Crossref
[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.
Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref
[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.
Crossref
[41]
D. M. Blei, A. Y. Ng, and M. I. Jordan, Latent Dirichlet allocation, J. Mach. Learn. Res., vol. 3, pp. 993-1022, 2003.
Google Scholar
[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.
Crossref
[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.
Crossref
[44]
F. F. Xu and P. Pan, A new algorithm for positive semidefinite matrix completion, J. Appl. Math., vol. 2016, p. 1659019, 2016.
Crossref Google Scholar
[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.
Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[52]
R. Glowinski, Numerical Methods for Nonlinear Variational Problems. Springer, 1984.
Crossref
[53]
R. Glowinski and P. Le Tallec, Augmented Lagrangian and Operator Splitting Methods in Nonlinear Mechanics. Philadelphia, PA, USA: SIAM, 1989, pp. 9.
Crossref
[54]
F. Xu and G. He, New algorithms for nonnegative matrix completion, Pac. J. Optim., vol. 11, no. 3, pp. 459-469, 2015.
Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref
[66]
C. B. Do and S. Batzoglou, What is the expectation maximization algorithm? Nat. Biotechnol., vol. 26, no. 8, pp. 897-899, 2008.
Crossref Google Scholar
[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.
Google Scholar
[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.
Crossref Google Scholar
[71]
A. Kapur, K. Marwah, and G. Alterovitz, Gene expression prediction using low-rank matrix completion, BMC Bioinform., vol. 17, pp. 243, 2016.
Crossref Google Scholar
[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.
Crossref
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[76]
K. Deb, Multi-objective optimization. in Search Methodologies, E. K. Burke and G. Kendall, eds. Springer, 2005.
Crossref
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
[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.
Crossref Google Scholar
Big Data Mining and Analytics
Volume 1 Issue 4,
December 2018
Pages 308-323
DOI: 10.26599/BDMA.2018.9020008
Cite this article:
Ramlatchan A, Yang M, Liu Q, et al. A Survey of Matrix Completion Methods for Recommendation Systems. Big Data Mining and Analytics, 2018, 1(4): 308-323. https://doi.org/10.26599/BDMA.2018.9020008

2014

Views

182

Downloads

108

Crossref

91

Web of Science

103

Scopus

0

CSCD

Altmetrics
Received: 21 January 2018
Accepted: 20 March 2018
Published: 02 July 2018
© The author(s) 2018
Return