Please wait a minute...
Big Data Mining and Analytics  2018, Vol. 01 Issue (04): 308-323    DOI: 10.26599/BDMA.2018.9020008
    
A Survey of Matrix Completion Methods for Recommendation Systems
Andy Ramlatchan, Mengyun Yang, Quan Liu, Min Li, Jianxin Wang, Yaohang Li*
Andy Ramlatchan is with NASA Langley Research Center, Hampton, VA 23666, USA and the Department of Computer Science, Old Dominion University, Norfolk, VA 23666, USA. E-mail: andy.ramlatchan@nasa.gov.
Mengyun Yang is with the Department of Computer Science, Central South University, Changsha 410083, China and the Department of Science, Shaoyang University, Shaoyang 422000, China. E-mail: yangmengyun@csu.edu.cn.
Quan Liu, Min Li, and Jianxin Wang are with the Department of Computer Science, Central South University, Changsha 410083, China. E-mail: liuquan@csu.edu.cn; limin@csu.edu.cn; jxwang@csu.edu.cn.
Yaohang Li is with the Department of Computer Science, Old Dominion University, Norfolk, VA 23529, USA.
Download: PDF (354 KB)      HTML  
Export: BibTeX | EndNote (RIS)      

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.



Key wordsmatrix completion      collaborative filtering      recommendation systems     
Received: 21 January 2018      Published: 13 January 2020
Corresponding Authors: Yaohang Li   
Cite this article:

Andy Ramlatchan, Mengyun Yang, Quan Liu, Min Li, Jianxin Wang, Yaohang Li. A Survey of Matrix Completion Methods for Recommendation Systems. Big Data Mining and Analytics, 2018, 01(04): 308-323.

URL:

http://bigdata.tsinghuajournals.com/10.26599/BDMA.2018.9020008     OR     http://bigdata.tsinghuajournals.com/Y2018/V01/I04/308

Fig. 1 Heterogeneous drugs-diseases network.
Fig. 2 Association matrix.
Fig. 3 Game matrix of 364 NCAA division I basketball teams. The <i>x</i>- and <i>y</i>-axes represent the NCAA teams and each point indicates there is a match between the two team during the regular season.
[1]   Hofmann T., Latent semantic models for collaborative filtering, ACM Trans. Inf. Syst., vol. 22, no. 1, pp. 89-115, 2004.
[2]   Hofmann T., Unsupervised learning by probabilistic latent semantic analysis, Mach. Learn., vol. 42, nos. 1&2, pp. 177-196, 2001.
[3]   Charalambous C. D. and Logothetis A., 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]   Dempster A. P., Laird N. M., and Rubin D. B., 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]   Neal R. M. and Hinton G. E., A View of the EM Algorithm That Justifies Incremental, Sparse, and Other Variants. Norwell, MA, USA: Kluwer, 1998.
[6]   Zhu H. T., Khondker Z., Lu Z. H., and Ibrahim J. G., 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]   Wood S. N., Low-rank scale-invariant tensor product smooths for generalized additive mixed models, Biometrics, vol. 62, no. 4, pp. 1025-1036, 2006.
[8]   Luo H. M., Li M., Wang S. K., Liu Q., Li Y. H., and Wang J. X., Computational drug repositioning using low-rank matrix approximation and randomized algorithms, Bioinformatics, vol. 34, no. 11, 1904-1912, 2018.
[9]   Lu C. Q., Yang M. Y., Luo F., Wu F. X., Li M., Pan Y., Li Y. H., and Wang J. X., Prediction of lncRNA-disease associations based on inductive matrix completion, Bioinformatics, doi:10.1093/bioinformatics/bty327.
[10]   Liang Y., Wu D. L., Liu G. R., Li Y. H., Gao C. L., Ma Z. J., and Wu W. D., Big data-enabled multiscale serviceability analysis for aging bridges, Digit. Commun. Netw., vol. 2, no. 3, pp. 97-107, 2016.
[11]   Bobadilla J., Ortega F., Hernando A., and Gutiérrez A., Recommender systems survey, Knowl. Based Syst., vol. 46, pp. 109-132, 2013.
[12]   Kunaver M. and Po?rl T., Diversity in recommender systems — A survey, Knowl. Based Syst., vol. 123, pp. 154-162, 2017.
[13]   Burke R., Hybrid recommender systems: Survey and experiments, User Model. User-Adapt. Interact., vol. 12, no. 4, pp. 331-370, 2002.
[14]   Desrosiers C. and Karypis G., A comprehensive survey of neighborhood-based recommendation methods, in Recommender Systems Handbook. Springer, 2010, pp. 107-144.
[15]   He C., Parra D., and Verbert K., 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]   Campos P. G., Díez F., and Cantador I., 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]   Yang X. W., Guo Y., Liu Y., and Steck H., A survey of collaborative filtering based social recommender systems, Comput. Commun., vol. 41, pp. 1-10, 2014.
[18]   Kla?nja-Milicevic A., Ivanovic M., and Nanopoulos A., 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]   Yera R. and Martínez L., Fuzzy tools in recommender systems: A survey, Int. J. Comput. Intell. Syst., vol. 10, no. 1, pp. 776-803, 2017.
[20]   Kotkov D., Wang S. Q., and Veijalainen J., A survey of serendipity in recommender systems, Knowl. Based Syst., vol. 111, pp. 180-192, 2016.
[21]   Candes E. J. and Tao T., The power of convex relaxation: Near-optimal matrix completion, IEEE Trans. Inf. Theory, vol. 56, no. 5, pp. 2053-2080, 2010.
[22]   Udell M., Horn C., Zadeh R., and Boyd S., Generalized low rank models, Found. Trends? Mach. Learn., vol. 9, no. 1, pp. 1-118, 2016.
[23]   Koren Y., Bell R., and Volinsky C., Matrix factorization techniques for recommender systems, Computer, vol. 42, no. 8, pp. 30-37, 2009.
[24]   Sarwar B. M., Karypis G., Konstan J. A., and Riedl J. T., Application of dimensionality reduction in recommender system-a case study, in Proc. ACM WebKDD Web Mining for E-Commerce Workshop, 2000.
[25]   Sarwar B., Karypis G., Konstan J., and Riedl J., Incremental singular value decomposition algorithms for highly scalable recommender systems, in Proc. 6th Int. Conf. on Computers and Information Technology, 2002.
[26]   Billsus D. and Pazzani M. J., Learning collaborative information filters, in Proc. 15th Int. Conf. on Machine Learning, San Francisco, CA, USA: ACM, 1998.
[27]   Paterek A., Improving regularized singular value decomposition for collaborative filtering, in Proc. KDD and Workshop, San Jose, CA, USA, 2007.
[28]   Rennie J. D. M. and Srebro N., Fast maximum margin matrix factorization for collaborative prediction, in Proc. 22nd Int. Conf. on Machine Learning, Bonn, Germany, 2005.
[29]   Vozalis M. G. and Margaritis K. G., Using SVD and demographic data for the enhancement of generalized collaborative filtering, Inf. Sci., vol. 177, no. 15, pp. 3017-3037, 2007.
[30]   Koren Y., 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]   Hallinan B. and Striphas T., Recommended for you: The NETflix prize and the production of algorithmic culture, New Media Soc., vol. 18, no. 1, pp. 117-137, 2016.
[32]   Ji Y. C., Hong W. X., Shangguan Y. L., Wang H., and Ma J., Regularized singular value decomposition in news recommendation system, in Proc. 11th Int. Conf. on Computer Science & Education, Nagoya, Japan, 2016, pp. 621-626.
[33]   Mazumder R., Hastie T., and Tibshirani R., Spectral regularization algorithms for learning large incomplete matrices, J. Mach. Learn. Res., vol. 11, pp. 2287-2322, 2010.
[34]   Kagie M., van der Loos M., and van Wezel M., Including item characteristics in the probabilistic latent semantic analysis model for collaborative filtering, AI Commun., vol. 22, no. 4, pp. 249-265, 2009.
[35]   Cai J. F., Candes E. J., and Shen Z. W., A singular value thresholding algorithm for matrix completion, SIAM J. Optim., vol. 20, no. 4, pp. 1956-1982, 2010.
[36]   Candès E. and Recht B., Simple bounds for recovering low-complexity models, Math. Program., vol. 141, nos. 1&2, pp. 577-589, 2013.
[37]   Recht B., Fazel M., and Parrilo P. A., Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, SIAM Rev, vol. 52, no. 3, pp. 471-501, 2010.
[38]   Wen Z. W., Yin W. T., and Zhang Y., 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]   Salakhutdinov R. and Mnih A., Bayesian probabilistic matrix factorization using Markov chain Monte Carlo, in Proc. 25th Int. Conf. on Machine Learning, Helsinki, Finland, 2008.
[40]   Agarwal D. and Chen B. C., Regression-based latent factor models, in Proc. 15th ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining, Paris, France, 2009.
[41]   Blei D. M., Ng A. Y., and Jordan M. I., Latent Dirichlet allocation, J. Mach. Learn. Res., vol. 3, pp. 993-1022, 2003.
[42]   Canny J., 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]   Salakhutdinov R. R., Mnih A., and Hinton G. E., Restricted boltzmann machines for collaborative filtering, in Proc. 24th Int. Conf. on Machine Learning, Corvallis, OR, USA, 2007.
[44]   Xu F. F. and Pan P., A new algorithm for positive semidefinite matrix completion, J. Appl. Math., vol. 2016, p. 1659019, 2016.
[45]   Hastie T., Mazumder R., Lee J. D., and Zadeh R., Matrix completion and low-rank svd via fast alternating least squares, J. Mach. Learn. Res., vol. 16, no. 1, pp. 3367-3402, 2015.
[46]   Cai J. F., Chan R. H., and Shen Z. W., A framelet-based image inpainting algorithm, Appl. Computat. Harmon. Anal., vol. 24, no. 2, pp. 131-149, 2008.
[47]   Combettes P. L. and Wajs V. R., Signal recovery by proximal forward-backward splitting, Multiscale Model. Simul., vol. 4, no. 4, pp. 1168-1200, 2005.
[48]   Daubechies I., Defrise M., and De Mol C., 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]   Hale E. T., Yin W. T., and Zhang Y., Fixed-point continuation for ℓ1-minimization: Methodology and convergence, SIAM J Optim., vol. 19, no. 3, pp. 1107-1130, 2008.
[50]   He B. S., Yang H., and Wang S. L., 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]   Gabay D. and Mercier B., 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]   Glowinski R., Numerical Methods for Nonlinear Variational Problems. Springer, 1984.
[53]   Glowinski R. and Le Tallec P., Augmented Lagrangian and Operator Splitting Methods in Nonlinear Mechanics. Philadelphia, PA, USA: SIAM, 1989, pp. 9.
[54]   Xu F. and He G., New algorithms for nonnegative matrix completion, Pac. J. Optim., vol. 11, no. 3, pp. 459-469, 2015.
[55]   Xu Y. Y., Yin W. T., Wen Z. W., and Zhang Y., An alternating direction algorithm for matrix completion with nonnegative factors, Front. Math. China, vol. 7, no. 2, pp. 365-384, 2012.
[56]   Chen C. H., He B. S., and Yuan X. M., Matrix completion via an alternating direction method, IMA J. Numer. Anal., vol. 32, no. 1, pp. 227-245, 2012.
[57]   Cai J. F. and Osher S., Fast singular value thresholding without singular value decomposition, Methods Appl. Anal., vol. 20, no. 4, pp. 335-352, 2013.
[58]   Halko N., Martinsson P. G., and Tropp J. A., Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions, SIAM Rev., vol. 53, no. 2, pp. 217-288, 2011.
[59]   Ji H., Yu W. J., and Li Y. H., A rank revealing randomized singular value decomposition (R3SVD) algorithm for low-rank matrix approximations, arXiv: 1605.08134, 2016.
[60]   Yu W. J., Gu Y., Li J., Liu S. H., and Li Y. H., Single-pass PCA of large high-dimensional data, in Proc. 26th Int. Joint Conf. on Artificial Intelligence, Catalina Island, CA, USA, 2010.
[61]   Li Y. H. and Yu W. J., A fast implementation of singular value thresholding algorithm using recycling rank revealing randomized singular value decomposition, arXiv: 1704.05528, 2017.
[62]   Toh K. C. and Yun S., 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]   Ma S. Q., Goldfarb D., and Chen L. F., Fixed point and bregman iterative methods for matrix rank minimization, Math. Program., vol. 128, no. 1-2, pp. 321-353, 2011.
[64]   Koren Y. and Bell R., Advances in collaborative filtering, in Recommender Systems Handbook, Ricci F., Rokach L., Shapira B., and Kantor P. B., eds. Springer, 2011.
[65]   Takács G., Pilászy I., Németh B., and Tikk D., 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]   Do C. B. and Batzoglou S., What is the expectation maximization algorithm? Nat. Biotechnol., vol. 26, no. 8, pp. 897-899, 2008.
[67]   Ji H., O’Saben E., Boudion A., and Li Y. H., March madness prediction: A matrix completion approach, in Proc. Modeling, Simulation, and Visualization Student Capstone Conf., Suffolk, UA, USA, 2015.
[68]   Ji H., O’Saben E., Lambi R., and Li Y. H., 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]   Zhang X. R. and Wang H. S., Study on recommender systems for business-to-business electronic commerce, Commun. IIMA, vol. 5, no. 4, pp. 53-61, 2005.
[70]   Exarchos T. P., Papaloukas C., Lampros C., and Fotiadis D. I., Mining sequential patterns for protein fold recognition, J. Biomed. Inf., vol. 41, no. 1, pp. 165-179, 2008.
[71]   Kapur A., Marwah K., and Alterovitz G., Gene expression prediction using low-rank matrix completion, BMC Bioinform., vol. 17, pp. 243, 2016.
[72]   Shin D., Cetintas S., Lee K. C., and Dhillon I. S., Tumblr blog recommendation with boosted inductive matrix completion, in Proc. 24th ACM Int. on Conf. on Information and Knowledge Management, Melbourne, Australia, 2015.
[73]   Mikolov T., Chen K., Corrado G., and Dean J., Efficient estimation of word representations in vector space, in Proc. Workshop at Int. Conf. on Learning Representations, Scottsdale, AZ, USA, 2013.
[74]   Liu J., Musialski P., Wonka P., and Ye J. P., Tensor completion for estimating missing values in visual data, IEEE Trans. Pattern Anal. Mach. Intell., vol. 35, no. 1, pp. 208-220, 2013.
[75]   Cui L. Z., Ou P., Fu X. H., Wen Z. K., and Lu N., A novel multi-objective evolutionary algorithm for recommendation systems, J. Parallel Distrib. Comput., vol. 103, pp. 53-63, 2017.
[76]   Deb K., Multi-objective optimization. in Search Methodologies, Burke E. K. and Kendall G., eds. Springer, 2005.
[77]   Li Y. H., 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]   Zhu W. H., Yaseen A., and Li Y. H., 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]   Recht B. and Ré C., Parallel stochastic gradient algorithms for large-scale matrix completion, Math. Program. Comput., vol. 5, no. 2, pp. 201-226, 2013.
[80]   Xu Y. Y., Hao R. R., Yin W. T., and Su Z. X., Parallel matrix factorization for low-rank tensor completion, Inverse Probl. Imaging, vol. 9, no. 2, pp. 601-624, 2015.
[1] Yu Liu, Shuai Wang, M. Shahrukh Khan, Jieyu He. A Novel Deep Hybrid Recommender System Based on Auto-encoder with Neural Collaborative Filtering[J]. Big Data Mining and Analytics, 2018, 01(03): 211-221.