主 题: Recovering the unseen: Some recent advances in low-rank matrix reconstruction
报告人: Emmanuel Candès (Professor of Mathematics, Stanford University)
时 间: 2013-10-12 14:30-15:30
地 点: Lecture Hall, Second Floor, Jia Yi Bing Building, 82 Jing Chun Yuan, PKU (Distinguished Lecture Series)
A problem of great interest concerns the recovery of a data matrix from a sampling of its entries. 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 (this is the famous Netflix problem). Formally, suppose that we observe a few entries selected uniformly at random from a matrix. Can we complete the matrix and recover the entries that we have not seen?
This talk discusses two surprising phenomena. The first is that one can recover low-rank matrices exactly from what appear to be highly incomplete sets of sampled entries. Further, perfect recovery is possible by solving a simple convex optimization program. The second is that exact recovery via convex programming is further possible even in situations where a positive fraction of the observed entries are corrupted in an almost arbitrary fashion. In passing, this suggests the possibility of a principled approach to principal component analysis that is robust vis a vis outliers and missing data. We discuss algorithms for solving these optimization problems emphasizing the suitability of our methods for large scale problems. Finally, we present surprising applications in the area of computer vision.
