Matrix Completion

Often a dataset can be viewed as a matrix, and in many situations that matrix is incomplete. Consider for example the Netflix matrix, where every entry is a particular user’s rating of a particular movie. Netflix does not have the ratings for every user on every movie, so this matrix is incomplete. The problem of matrix completion asks, very generally, what kinds of assumptions might we make on that underlying matrix to successfully reconstruct the entire matrix? This paper (and its predecessor by Candes and Recht) provided breakthrough results showing that a low-rank and incoherent matrix can be perfectly reconstructed using a convex optimization problem. Our work showed that a high-rank matrix can also be recovered, if it’s columns lie in a union of subspaces. I am studying the assumptions behind such algorithms, the application of matrix completion to real engineering problems, and new generalizations of the matrix completion problem to other models.