×

Collective matrix completion. (English) Zbl 1446.62140

Summary: Matrix completion aims to reconstruct a data matrix based on observations of a small number of its entries. Usually in matrix completion a single matrix is considered, which can be, for example, a rating matrix in recommendation system. However, in practical situations, data is often obtained from multiple sources which results in a collection of matrices rather than a single one. In this work, we consider the problem of collective matrix completion with multiple and heterogeneous matrices, which can be count, binary, continuous, etc. We first investigate the setting where, for each source, the matrix entries are sampled from an exponential family distribution. Then, we relax the assumption of exponential family distribution for the noise. In this setting, we do not assume any specific model for the observations. The estimation procedures are based on minimizing the sum of a goodness-of-fit term and the nuclear norm penalization of the whole collective matrix. We prove that the proposed estimators achieve fast rates of convergence under the two considered settings and we corroborate our results with numerical experiments.

MSC:

62H12 Estimation in multivariate analysis
62M20 Inference from stochastic processes and prediction
PDFBibTeX XMLCite
Full Text: arXiv Link

References:

[1] D. Agarwal, L. Zhang, and R. Mazumder. Modeling itemitem similarities for personalized recommendations on yahoo! front page.Ann. Appl. Stat., 5(3):1839-1875, 2011. · Zbl 1231.62207
[2] P. Alquier, V. Cottet, and G. Lecu´e. Estimation bounds and sharp oracle inequalities of regularized procedures with Lipschitz loss functions.arXiv:1702.01402, 2017.
[3] M.G. Armentano, D. Godoy, and A. A. Amandi. Followee recommendation based on text analysis of micro-blogging activity.Information Systems, 38(8):1116 - 1127, 2013. ISSN 0306-4379.
[4] A. S. Bandeira and R. van Handel. Sharp nonasymptotic bounds on the norm of random matrices with independent entries.Ann. Probab., 44(4):2479-2506, 2016. · Zbl 1372.60004
[5] A. Banerjee, S. Merugu, I. S. Dhillon, and J. Ghosh. Clustering with bregman divergences. J. Mach. Learn. Res., 6:1705-1749, 2005. · Zbl 1190.62117
[6] P. L. Bartlett, M. I. Jordan, and J. D. Mcauliffe. Large margin classifiers: Convex loss, low noise, and convergence rates. In S. Thrun, L. K. Saul, and B. Sch¨olkopf, editors,Advances in Neural Information Processing Systems 16, pages 1173-1180. MIT Press, 2004.
[7] Amir Beck and Marc Teboulle. A fast iterative shrinkage-thresholding algorithm for linear inverse problems.SIAM J. Img. Sci., 2(1):183-202, 2009. · Zbl 1175.94009
[8] J. Bobadilla, F. Ortega, A. Hernando, and A. Guti´errez. Recommender systems survey. Know.-Based Syst., 46:109-132, 2013.
[9] G. Bouchard, D. Yin, and S. Guo. Convex collective matrix factorization. InAISTATS, volume 31 ofJMLR Workshop and Conference Proceedings, pages 144-152. JMLR.org, 2013.
[10] O. Bousquet. A bennett concentration inequality and its application to suprema of empirical processes.Comptes Rendus Mathematique, 334(6):495 - 500, 2002. · Zbl 1001.60021
[11] S. Boyd and L. Vandenberghe.Convex Optimization. Cambridge University Press, New York, NY, USA, 2004. · Zbl 1058.90049
[12] L.M. Bregman. The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming.USSR Computational Mathematics and Mathematical Physics, 7(3):200 - 217, 1967. · Zbl 0186.23807
[13] P. B¨uhlmann and S. van de Geer.Statistics for High-Dimensional Data: Methods, Theory and Applications. Springer Series in Statistics. Springer Berlin Heidelberg, 2011. · Zbl 1273.62015
[14] J.-F. Cai., E. J. Cands, and Z. Shen. A singular value thresholding algorithm for matrix completion.SIAM Journal on Optimization, 20(4):1956-1982, 2010. · Zbl 1201.90155
[15] T. Cai and W. X. Zhou. A max-norm constrained minimization approach to 1-bit matrix completion.J. Mach. Learn. Res., 14(1):3619-3647, 2013. · Zbl 1318.62172
[16] T. Tony Cai and Wen-Xin Zhou. Matrix completion via max-norm constrained optimization. Electron. J. Statist., 10(1):1493-1525, 2016. · Zbl 1342.62091
[17] E. J. Cand‘es and B. Recht. Exact matrix completion via convex optimization.Foundations of Computational Mathematics, 9(6):717, 2009. · Zbl 1219.90124
[18] E. J. Candes and T. Tao. The power of convex relaxation: Near-optimal matrix completion. IEEE Transactions on Information Theory, 56(5):2053-2080, 2010. · Zbl 1366.15021
[19] I. Cantador, I. Fern´andez-Tob´ıas, Shlomo Berkovsky, and P. Cremonesi.Cross-Domain Recommender Systems, pages 919-959. Springer US, Boston, MA, 2015.
[20] Y. Censor and S.A. Zenios.Parallel Optimization: Theory, Algorithms, and Applications. Oxford University Press, USA, 1997. · Zbl 0945.90064
[21] K.-Y. Chiang, C.-J. Hsieh, and I. S. Dhillon. Matrix completion with noisy side information. InProceedings of the 28th International Conference on Neural Information Processing Systems - Volume 2, NIPS’15, pages 3447-3455, Cambridge, MA, USA, 2015. MIT Press.
[22] K.-Y. Chiang, I. S. Dhillon, and C.-J. Hsieh. Using side information to reliably learn lowrank matrices from missing and corrupted observations.Journal of Machine Learning Research, 19(76):1-35, 2018. · Zbl 1476.68226
[23] M. A. Davenport, Y. Plan, E. van den Berg, and M. Wootters. 1-bit matrix completion. Information and Inference: A Journal of the IMA, 3(3):189, 2014. · Zbl 1309.62124
[24] P. Drineas, A. Javed, M. Magdon-Ismail, G. Pandurangant, R. Virrankoski, and A. Savvides. Distance matrix reconstruction from incomplete distance information for sensor network localization. In2006 3rd Annual IEEE Communications Society on Sensor and Ad Hoc Communications and Networks, volume 2, pages 536-544, 2006.
[25] A. Elsener and S. van de Geer. Robust low-rank matrix estimation.Ann. Statist., 46(6B): 3481-3509, 12 2018. · Zbl 1412.62068
[26] M. Fazel.Matrix Rank Minimization with Applications. PhD thesis, Stanford University, 2002.
[27] M. Fazel, H. Hindi, and S. P. Boyd. A rank minimization heuristic with application to minimum order system approximation. InProceedings of the 2001 American Control Conference. (Cat. No.01CH37148), volume 6, pages 4734-4739 vol.6, 2001.
[28] W. Fithian and R. Mazumder. Flexible low-rank statistical modeling with missing data and side information.Statist. Sci., 33(2):238-260, 2018. · Zbl 1397.62180
[29] D. Goldberg, D. Nichols, B. M. Oki, and D. Terry. Using collaborative filtering to weave an information tapestry.Commun. ACM, 35(12):61-70, 1992.
[30] S. Gunasekar, P. Ravikumar, and J. Ghosh. Exponential family matrix completion under structural constraints. InProceedings of the 31st International Conference on International Conference on Machine Learning - Volume 32, ICML’14, pages II-1917-II-1925. JMLR.org, 2014.
[31] S. Gunasekar, M. Yamada, D. Yin, and Y. Chang. Consistent collective matrix completion under joint low rank structure. InAISTATS, 2015.
[32] S. Gunasekar, J. C. Ho, J. Ghosh, S. Kreml, A. N. Kho, J. C Denny, B. A. Malin, and J. Sun. Phenotyping using structured collective matrix factorization of multi-source ehr data.preprint arXiv:1609.04466, 2016.
[33] N. Halko, P. Martinsson, and J. Tropp. Finding structure with randomness: Probabilistic algorithms for constructing approximate matrix decompositions.SIAM Review, 53(2): 217-288, 2011. · Zbl 1269.65043
[34] J. Hannon, M. Bennett, and B. Smyth. Recommending twitter users to follow using content and collaborative filtering approaches. InProceedings of the Fourth ACM Conference on Recommender Systems, RecSys ’10, pages 199-206, New York, NY, USA, 2010. ACM. ISBN 978-1-60558-906-0.
[35] S. Horii, T. Matsushima, and S. Hirasawa. A note on the correlated multiple matrix completion based on the convex optimization method. In2014 IEEE International Conference on Systems, Man, and Cybernetics (SMC), pages 1618-1623, 2014.
[36] Y. Hu, D. Zhang, J. Ye, X. Li, and X. He. Fast and accurate matrix completion via truncated nuclear norm regularization.IEEE Transactions on Pattern Analysis and Machine Intelligence, 35(9):2117-2130, 2013.
[37] P. Jain and I. S. Dhillon. Provable inductive matrix completion.CoRR, abs/1306.0626, 2013.
[38] M. Jamali and M. Ester.A matrix factorization technique with trust propagation for recommendation in social networks. InProceedings of the Fourth ACM Conference on Recommender Systems, RecSys ’10, pages 135-142, New York, NY, USA, 2010. ACM. ISBN 978-1-60558-906-0.
[39] S. Ji and J. Ye. An accelerated gradient method for trace norm minimization. InProceedings of the 26th Annual International Conference on Machine Learning, ICML ’09, pages 457- 464, New York, NY, USA, 2009a. ACM.
[40] S. Ji and J. Ye. An accelerated gradient method for trace norm minimization. InProceedings of the 26th Annual International Conference on Machine Learning, ICML ’09, pages 457- 464, New York, NY, USA, 2009b. ACM.
[41] O. Klopp. Noisy low-rank matrix completion with general sampling distribution.Bernoulli, 20(1):282-303, 2014. · Zbl 1400.62115
[42] O. Klopp. Matrix completion by singular value thresholding: Sharp bounds.Electron. J. Statist., 9(2):2348-2369, 2015. · Zbl 1323.62047
[43] O. Klopp, J. Lafond, E. Moulines, and J. Salmon. Adaptive multinomial matrix completion. Electron. J. Statist., 9(2):2950-2975, 2015. · Zbl 1329.62304
[44] Y. Koren, R. Bell, and C. Volinsky.Matrix factorization techniques for recommender systems.Computer, 42(8):30-37, 2009.
[45] J. Lafond. Low rank matrix completion with exponential family noise. In Peter Grnwald, Elad Hazan, and Satyen Kale, editors,Proceedings of The 28th Conference on Learning Theory, volume 40 ofProceedings of Machine Learning Research, pages 1224-1243, Paris, France, 2015. PMLR.
[46] X. N. Lam, T. Vu, T. D. Le, and A. D. Duong. Addressing cold-start problem in recommendation systems. InProceedings of the 2Nd International Conference on Ubiquitous Information Management and Communication, ICUIMC ’08, pages 208-211, New York, NY, USA, 2008. ACM.
[47] R. M. Larsen. Lanczos bidiagonalization with partial reorthogonalization, 1998.
[48] E. L. Lehmann and G. Casella.Theory of Point Estimation. Springer-Verlag, New York, NY, USA, second edition, 1998. · Zbl 0916.62017
[49] Z. Liu and L. Vandenberghe. Interior-point method for nuclear norm approximation with application to system identification.SIAM J. Matrix Anal. Appl., 31(3):1235-1256, 2009. · Zbl 1201.90151
[50] Z. Liu and L. Vandenberghe. Interior-point method for nuclear norm approximation with application to system identification.SIAM Journal on Matrix Analysis and Applications, 31(3):1235-1256, 2010. · Zbl 1201.90151
[51] H. Ma, D. Zhou, C. Liu, M. R. Lyu, and I. King. Recommender systems with social regularization. InProceedings of the Fourth ACM International Conference on Web Search and Data Mining, WSDM ’11, pages 287-296, New York, NY, USA, 2011. ACM. ISBN 978-1-4503-0493-1.
[52] R. Mazumder, T. Hastie, and R. Tibshirani. Spectral regularization algorithms for learning large incomplete matrices.J. Mach. Learn. Res., 11:2287-2322, 2010. · Zbl 1242.68237
[53] S. Mendelson. Obtaining fast error rates in nonconvex situations.Journal of Complexity, 24(3):380 - 397, 2008. · Zbl 1338.60112
[54] N. Natarajan and I. S. Dhillon. Inductive matrix completion for predicting genedisease associations.Bioinformatics, 30(12):i60-i68, 06 2014. ISSN 1367-4803.
[55] N. Natarajan, D. Shin, and I. S. Dhillon. Which app will you use next?: Collaborative filtering with interactional context. InProceedings of the 7th ACM Conference on Recommender Systems, RecSys ’13, pages 201-208, New York, NY, USA, 2013. ACM. ISBN 978-1-4503-2409-0.
[56] S. Negahban and M. J. Wainwright. Estimation of (near) low-rank matrices with noise and high-dimensional scaling.Ann. Statist., 39(2):1069-1097, 2011. · Zbl 1216.62090
[57] Y. Nesterov. Gradient methods for minimizing composite functions.Mathematical Programming, 140(1):125-161, 2013. · Zbl 1287.90067
[58] S. Oh, A. Montanari, and A. Karbasi. Sensor network localization from local connectivity: Performance analysis for the mds-map algorithm. In2010 IEEE Information Theory Workshop on Information Theory (ITW 2010, Cairo), pages 1-5, 2010.
[59] J. Pag‘es.Multiple Factor Analysis by Example Using R. Chapman & Hall/CRC The R Series. Taylor & Francis, 2014. ISBN 9781482205473.
[60] N. Parikh and S. Boyd. Proximal algorithms.Found. Trends Optim., 1(3):127-239, 2014.
[61] B. Recht, M. Fazel, and P. A. Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization.SIAM Rev., 52(3):471-501, 2010. · Zbl 1198.90321
[62] J. D. M. Rennie and N. Srebro. Fast maximum margin matrix factorization for collaborative prediction. InProceedings of the 22Nd International Conference on Machine Learning, ICML ’05, pages 713-719, New York, NY, USA, 2005. ACM.
[63] R.Vershynin. Introduction to the non-asymptotic analysis of random matrices.CoRR, abs/1011.3027, 2010.
[64] S. Shin, D.and Cetintas and I. S. Lee, K.-C.and Dhillon. Tumblr blog recommendation with boosted inductive matrix completion. InProceedings of the 24th ACM International on Conference on Information and Knowledge Management, CIKM ’15, pages 203-212, New York, NY, USA, 2015. ACM. ISBN 978-1-4503-3794-6.
[65] A. P. Singh and G. J. Gordon. Relational learning via collective matrix factorization. In Proceedings of the 14th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, KDD ’08, pages 650-658, New York, NY, USA, 2008. ACM.
[66] A. P. Singh and G. J. Gordon. A bayesian matrix factorization model for relational data. InProceedings of the Twenty-Sixth Conference on Uncertainty in Artificial Intelligence, UAI’10, pages 556-563, Arlington, Virginia, United States, 2010. AUAI Press.
[67] A. M.-C. So and Y. Ye. Theory of semidefinite programming for sensor network localization. InProceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA ’05, pages 405-414, Philadelphia, PA, USA, 2005. Society for Industrial and Applied Mathematics. · Zbl 1297.90110
[68] N. Srebro, J. Rennie, and T. S. Jaakkola. Maximum-margin matrix factorization, 2005. 42
[69] M. Udell, C. Horn, R. Zadeh, and S. Boyd. Generalized low rank models.Found. Trends Mach. Learn., 9(1):1-118, June 2016. ISSN 1935-8237. · Zbl 1350.68221
[70] S. van de Geer.Estimation and Testing Under Sparsity: ´Ecole d’ ´Et´e de Probabilit´es de SaintFlour XLV - 2015. Lecture Notes in Mathematics. Springer International Publishing, 2016. · Zbl 1362.62006
[71] L. Xu, Z. Chen, Q. Zhou, E. Chen, N. J. Yuan, and X. Xie. Aligned matrix completion: Integrating consistency and independency in multiple domains. In2016 IEEE 16th International Conference on Data Mining (ICDM), pages 529-538, 2016.
[72] M. Xu, R. Jin, and Z.-H. Zhou. Speedup matrix completion with side information: Application to multi-label learning. InProceedings of the 26th International Conference on Neural Information Processing Systems - Volume 2, NIPS’13, pages 2301-2309, USA, 2013. Curran Associates Inc.
[73] Q. Yao and J. T. Kwok. Accelerated inexact soft-impute for fast large-scale matrix completion. InProceedings of the 24th International Conference on Artificial Intelligence, IJCAI’15, pages 4002-4008. AAAI Press, 2015.
[74] T. Zhang. Statistical behavior and consistency of classification methods based on convex risk minimization.Ann. Statist., 32(1):56-85, 2004. · Zbl 1105.62323
[75] M. Zitnik and B. Zupan. Matrix factorization-based data fusion for gene function prediction in baker’s yeast and slime mold.Pacific Symposium on Biocomputing. Pacific Symposium on Biocomputing, pages 400-11, 2014.
[76] M.
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.