Speaker; Emmanuel Candès (Professor of Mathematics, Stanford University, Winner of NSF Waterman Award, Winner of ICIAM Collatz Prize)

Time: 14:30—15:30, October 12,2013

Place: Lecture Hall, Second Floor, Jia Yi Bing Building, 82 Jing Chun Yuan, PKU

Abstract: 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.