Natural language research announcements

[Rajhans Samdani <rsamdan2 AT illinois.edu>]

Speaker:  Professor Yi Ma
ECE Department, University of Illinois-U/C
and VC Group, Microsoft Research Asia

Date:  Wednesday, March 10, 2010
Time:  4:00 - 5:00 pm
Where:  4269 Beckman Institute

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 (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, background modeling, movie repairing,
robust batch image alignment, video stabilization, super-resolution,
web document analysis, to robust system identification and beyond.


This is joint work with Emmanuel Candes of Stanford and John Wright of MSRA.


Rajhans Samdani,
Graduate Student,
Dept. of Computer Science,
University of Illinois at Urbana-Champaign.