主 题: Robust Principal Component Analysis and Its Applications
报告人: Prof. Yi MA(Microsoft Research Asia)
时 间: 2010-05-11 14:00-15:00
地 点: 理科一号搂1418
Principal component analysis is a fundamental operation in computational data analysis, with myriad applications ranging from web search, to bioinformatics, to dynamical system identification, to computer vision and image analysis. However, its performance and applicability in real scenarios are limited by a lack of robustness to outlying or corrupted observations. In this work, we consider the idealized “robust principal component analysis” problem of recovering a low-rank matrix A from corrupted observations D = A E. Here, the error entries E can be arbitrarily large (modeling grossly corrupted observations common in visual and bioinformatic data), but are assumed to be sparse. We prove that most matrices A can be efficiently and exactly recovered from most error sign-and-support patterns, by solving a simple convex program. Our result holds even when the rank of A grows nearly proportionally (up to a logarithmic factor) to the dimensionality of the observation space and the number of errors E grows in proportion to the total number of entries in the matrix (or even dense if its signs are random).
We will also review the rapid development of fast and scalable algorithms for solving this problem that, for large matrices, is significantly faster and more scalable than general-purpose solvers. The main goal of this talk is to showcase some of the wide spectrum of exciting applications that have been enabled by this new tool, ranging from robust face recognition, video background modeling, movie repairing, robust batch image alignment, video stabilization, super-resolution, web document analysis, to robust system identification and beyond.
