Abstract: Low rank matrix completion plays a fundamental role in collaborative filtering applications, the key idea being that the variables lie in a smaller subspace than the ambient space. Often, additional information about the variables is known, and it is reasonable to assume that incorporating this information will lead to better predictions. We tackle the problem of matrix completion when the variables are related to each other via a graph. We formulate and derive an efficient alternating minimization scheme that solves optimizations with over 15 million observations up to 2 orders of magnitude faster than SGD based methods. On the theoretical front, we show that such methods generalize weighted nuclear norm formulations,and derive statistical consistency guarantees. We validate our results on both real world and synthetic datasets.
- Collaborative Filtering with Graph Information: Consistency and Scalable Methods (pdf, software, code)
N. Rao, H. Yu, P. Ravikumar, I. Dhillon.
In Neural Information Processing Systems (NIPS), pp. 2098–2106, December 2015. (Spotlight)