nips nips2009 nips2009-148 nips2009-148-reference knowledge-graph by maker-knowledge-mining
Source: pdf
Author: Raghu Meka, Prateek Jain, Inderjit S. Dhillon
Abstract: The low-rank matrix completion problem is a fundamental problem with many important applications. Recently, [4],[13] and [5] obtained the first non-trivial theoretical results for the problem assuming that the observed entries are sampled uniformly at random. Unfortunately, most real-world datasets do not satisfy this assumption, but instead exhibit power-law distributed samples. In this paper, we propose a graph theoretic approach to matrix completion that solves the problem for more realistic sampling models. Our method is simpler to analyze than previous methods with the analysis reducing to computing the threshold for complete cascades in random graphs, a problem of independent interest. By analyzing the graph theoretic problem, we show that our method achieves exact recovery when the observed entries are sampled from the Chung-Lu-Vu model, which can generate power-law distributed graphs. We also hypothesize that our algorithm solves the matrix completion problem from an optimal number of entries for the popular preferential attachment model and provide strong empirical evidence for the claim. Furthermore, our method is easy to implement and is substantially faster than existing methods. We demonstrate the effectiveness of our method on random instances where the low-rank matrix is sampled according to the prevalent random graph models for complex networks and present promising preliminary results on the Netflix challenge dataset. 1
[1] Albert-Laszlo Barabasi and Reka Albert. Emergence of scaling in random networks. Science, 286:509, 1999.
[2] Matthew Brand. Fast online svd revisions for lightweight recommender systems. In SDM, 2003.
[3] Jian-Feng Cai, Emmanuel J. Candes, and Zuowei Shen. A singular value thresholding algorithm for matrix completion, 2008.
[4] Emmanuel J. Cand` s and Benjamin Recht. Exact matrix completion via convex optimization. CoRR, e abs/0805.4471, 2008.
[5] Emmanuel J. Cand` s and Terence Tao. The power of convex relaxation: Near-optimal matrix completion. e CoRR, abs/0903.1476, 2009.
[6] Fan R. K. Chung, Linyuan Lu, and Van H. Vu. The spectra of random graphs with given expected degrees. Internet Mathematics, 1(3), 2003.
[7] A. Clauset, C.R. Shalizi, and M.E.J. Newman. Power-law distributions in empirical data. SIAM Review, page to appear, 2009.
[8] Uriel Feige and Eran Ofek. Spectral techniques applied to sparse random graphs. Random Struct. Algorithms, 27(2):251–275, 2005.
[9] Joel Friedman, Jeff Kahn, and Endre Szemer´ di. On the second eigenvalue in random regular graphs. In e STOC, pages 587–598, 1989.
[10] Christos Gkantsidis, Milena Mihail, and Ellen W. Zegura. Spectral analysis of internet topologies. In INFOCOM, 2003. ´
[11] David Kempe, Jon M. Kleinberg, and Eva Tardos. Maximizing the spread of influence through a social network. In KDD, pages 137–146, 2003. ´
[12] David Kempe, Jon M. Kleinberg, and Eva Tardos. Influential nodes in a diffusion model for social networks. In ICALP, pages 1127–1138, 2005.
[13] Raghunandan H. Keshavan, Sewoong Oh, and Andrea Montanari. Matrix completion from a few entries. CoRR, abs/0901.3150, 2009.
[14] Jon M. Kleinberg. Hubs, authorities, and communities. ACM Comput. Surv., 31(4es):5, 1999.
[15] Yehuda Koren. Factorization meets the neighborhood: a multifaceted collaborative filtering model. In KDD, pages 426–434, 2008.
[16] Silvio Lattanazi and D. Sivakumar. Affiliation networks. In STOC, 2009.
[17] Jure Leskovec, Jon M. Kleinberg, and Christos Faloutsos. Graph evolution: Densification and shrinking diameters. TKDD, 1(1), 2007.
[18] Yehuda Koren M. Bell. Scalable collaborative filtering with jointly derived neighborhood interpolation weights. In ICDM, pages 43–52, 2007.
[19] Milena Mihail and Christos H. Papadimitriou. On the eigenvalue power law. In RANDOM, pages 254– 262, 2002.
[20] Benjamin Recht, Maryam Fazel, and Pablo A. Parrilo. Guaranteed minimum-rank solutions of linear matrix equations via nuclear norm minimization, 2007. 9