Adventures in Theory : A Lecture Series in Theoretical and Mathematical Science
Tuesday, April 14, 2009, 4:30pm, 130 Physics
Emmanuel J. Candes (California Institute of Technology)
Exact Matrix Completion by Convex Optimization Theory and Algorithms
Abstract:- The recovery of a data matrix from a sampling of its entries is a problem of
considerable practical interest. In partially filled out surveys, for instance,
we would like to infer the many missing entries. In the area of recommender
systems, users submit ratings on a subset of entries in a database, and the
vendor provides recommendations based on the user's preferences.
Because users only rate a few items, we would like to infer their preference
for unrated items (the famous Netflix problem). Formally, suppose that we
observe m entries selected uniformly at random from a matrix. Can we
complete the matrix and recover the entries that we have not seen?
Surprisingly, one can recover low-rank matrices exactly from what appear
to be highly incomplete sets of sampled entries; that is, from a minimally
sampled set of entries. Further, perfect recovery is possible by solving a
simple convex optimization program, namely, a convenient semi-definite
program. We show that our methods are optimal and succeed as soon as
recovery is possible by any method whatsoever. Time permitting, we will
also present a very efficient algorithm based on iterative singular value
thresholding, which can complete matrices with about a billion entries in a
matter of minutes on a personal computer.
Generated at 1:10pm Friday, April 19, 2024 by Mcal. Top
* Reload
* Login