Robust Principal Component Analysis: Exact Recovery of Corrupted Low-Rank Matrices via Convex Optimization

Speaker:	Dr. Yi MA
		ECE Department, UIUC
		Research Manager, Microsoft Research Asia

Title:		"Robust Principal Component Analysis:
		 Exact Recovery of Corrupted Low-Rank Matrices via
		 Convex Optimization"

Date:		Wednesday, 6 January 2010

Time:		11:00am - 12 noon

Venue:		Room 3412 (via lifts 17/18), HKUST

Abstract:

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. We will also review the rapid development of fast algorithms
for solving this problem that, for large matrices, is significantly faster
and more scalable than general-purpose solvers. We provide simulations and
real-data examples corroborating the theoretical results. The simulation
results actually have revealed even more striking phenomena and remarkable
pictures that merit future investigation.

This is joint work with Emmanuel Candes, Xiaodong Li, and John Wright


*****************
Biography:

Yi Ma is an associate professor at the Electrical & Computer Engineering
Department of the University of Illinois at Urbana-Champaign. He is also
the research manager of the Visual Computing group at Microsoft Research
Asia in Beijing since January 2009. His main research interest is in
computer vision, high-dimensional data analysis, and systems theory. He is
the first author of the popular vision textbook "An Invitation to 3-D
Vision," published by Springer in 2003. Yi Ma received two Bachelors'
degree in Automation and Applied Mathematics from Tsinghua University
(Beijing, China) in 1995, a Master of Science degree in EECS in 1997, a
Master of Arts degree in Mathematics in 2000, and a PhD degree in EECS in
2000, all from the University of California at Berkeley. Yi Ma received
the David Marr Best Paper Prize at the International Conference on
Computer Vision 1999, the Longuet-Higgins Best Paper Prize at the European
Conference on Computer Vision 2004, and the Sang Uk Lee Best Student Paper
Award with his students at the Asian Conference on Computer Vision in
2009. He also received the CAREER Award from the National Science
Foundation in 2004 and the Young Investigator Award from the Office of
Naval Research in 2005. He is an associate editor of IEEE Transactions on
Pattern Analysis and Machine Intelligence and has served as the chief
guest editor for special issues for the Proceedings of IEEE and the IEEE
Signal Processing Magazine. He will also serve as Program Chair for ICCV
2013 in Sydney, Australia. He is a senior member of IEEE and a member of
ACM, SIAM, and ASEE.