High-Dimensional Robust PCA
Huan Xu
Dr.
the Department of Electrical and Computer Engineering
The University of Texas at Austin
Abstract :
The analysis of very high dimensional data has drawn increasing attention
due to a broad array of applications. This exciting new regime poses
severe challenges and many of our tried-and-true statistical techniques
fail in this regime. In this talk we revisit one of the perhaps most
widely used statistical techniques for dimensionality reduction: Principal
Component Analysis (PCA). PCA is well-known to be exceptionally brittle
-- even a single corrupted point can lead to arbitrarily bad PCA output.
We consider PCA in the high-dimensional regime, where a constant fraction
of the observations in the data set are arbitrarily corrupted. We show
that many existing techniques for controlling the effect of outliers fail
in this setting, and discuss some of the unique challenges (and also
opportunities) that the high-dimensional regime poses. Then, we propose a
High-dimensional Robust Principal Component Analysis (HR-PCA) algorithm
that is computationally tractable, provably robust to contaminated points,
and easily kernelizable. The resulting subspace has a bounded deviation
from the desired one, achieves maximal robustness, and unlike ordinary PCA
algorithms, achieves optimality (i.e., exact recovery) in the limiting
case where the proportion of corrupted points goes to zero. To the best of
our knowledge, this is the very first robust PCA algorithm that works in
the high-dimensional regime.
Bio:
Huan Xu is a postdoctoral associate in the Department of Electrical and
Computer Engineering at The University of Texas at Austin. He received the
B.Eng. degree in automation from Shanghai Jiaotong University, Shanghai,
China in 1997, the M.Eng. degree in electrical engineering from the
National University of Singapore in 2003, and the Ph.D. degree in
electrical engineering from McGill University, Canada in 2009. His
research interests include high-dimensional data analysis, machine
learning, robust optimization, and decision making and control under
uncertainty. Starting from Jan. 2011, he will join the Department of
Mechanical Engineering of the National University of Singapore as an
Assistant Professor.