Robust Subspace Recovery with Adversarial Outliers

Tuesday, June 18, 2019 - 10:00am - 10:50am
Lind 305
Tyler Maunu (Massachusetts Institute of Technology)
We study the problem of robust subspace recovery (RSR) in the presence of adversarial outliers. That
is, we seek a subspace that contains a large portion of a dataset when some fraction of the data points are
arbitrarily corrupted. We first examine a theoretical estimator that is intractable to calculate and use it
to derive information-theoretic bounds of exact recovery. We then propose two tractable estimators: a
variant of RANSAC and a simple relaxation of the theoretical estimator. The two estimators are fast to
compute and achieve state-of-the-art theoretical performance in a noiseless RSR setting with adversarial
outliers. The former estimator achieves better theoretical guarantees in the noiseless case, while the
latter estimator is robust to small noise, and its guarantees significantly improve with non-adversarial
models of outliers. We give a complete comparison of guarantees for the adversarial RSR problem, as
well as a short discussion on the estimation of affine subspaces.