# Emmanuel J. Candes : Exact Matrix Completion by Convex Optimization Theory and Algorithms

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.

**Category**: Number Theory**Duration**: 01:34:47**Date**: April 14, 2009 at 4:25 PM**Views**: 109-
**Tags:**seminar, Adventures in Theory : A Lecture Series in Theoretical and Mathematical Science

## 0 Comments