Algorithms for matrix completion

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.

Department dc:contributor.department

Massachusetts Institute of Technology. Dept. of Electrical Engineering and Computer Science.

Grantor dc:publisher

Massachusetts Institute of Technology

Year dc:date.issued

2012

Author dc:creator

• Xin, Yu, Ph. D. Massachusetts Institute of Technology

Advisor dc:contributor.advisor

• Tommi S. Jaakkola.

• Electrical Engineering and Computer Science.

Statement dc:rights

• M.I.T. theses are protected by copyright. They may be viewed from this source for any purpose, but reproduction or distribution in any format is prohibited without written permission. See provided URL for inquiries about permission.

Licence dc:rights.uri

• http://dspace.mit.edu/handle/1721.1/7582

Language dc:language.iso

eng

Handle dc:identifier.uri

http://hdl.handle.net/1721.1/71500

OAI identifier oai:identifier

oai:dspace.mit.edu:1721.1/71500