Algorithms for matrix completion

Abstract

We consider collaborative filtering methods for matrix completion. A typical approach is to find a low rank matrix that matches the observed ratings. However, the corresponding problem has local optima. In this thesis, we study two approaches to remedy this issue: reference vector method and trace norm regularization. The reference vector method explicitly constructs user and item features based on similarities to reference sets of users and items. Then the learning task reduces to a convex regression problem for which the global optimum can be obtained. Second, we develop and analyze a new algorithm for the trace-norm regularization approach. To facilitate smooth primal optimization, we introduce a soft variational trace-norm and analyze a class of alternating optimization algorithms. We introduce a scalable primal-dual block coordinate descent algorithm for large sparse matrix completion. The algorithm explicitly maintains a sparse dual and the corresponding low rank primal solution at the same time. Preliminary empirical results illustrate both the scalability and the accuracy of the algorithm.