Publications

Matrix Completion

–Updated 07/2016. Highlight the local geometry nature of our proof. New slides with a cleaner summary of the proof sketch.

Background: Motivated by applications such as recommender systems (e.g. Netflix prize), the problem of recovering a low-rank matrix from a few observations has been popular recently. It is a prototype example of how to utilize the low-rank structure to deal with big data. There are two popular approaches to impose the low-rank structure: nuclear norm based approach and matrix factorization (MF) based approach. The latter approach is especially amenable for big data problems, and has served as the basic component of most competing algorithms for Netflix prize. However, due to the non-convexity, it seems to be difficult to obtain a theoretical guarantee.

ddd