Title: Nearly Optimal Robust Subspace Tracking,
Abstract: In this work, we study the robust subspace tracking (RST) problem and obtain
one of the first two provable guarantees for it. The goal of RST is to track
sequentially arriving data vectors that lie in a slowly changing
low-dimensional subspace, while being robust to corruption by additive sparse
outliers. It can also be interpreted as a dynamic (time-varying) extension of
robust PCA (RPCA), with the minor difference that RST also requires a short
tracking delay. We develop a recursive projected compressive sensing algorithm
that we call Nearly Optimal RST via ReProCS (ReProCS-NORST) because its
tracking delay is nearly optimal. We prove that NORST solves both the RST and
the dynamic RPCA problems under weakened standard RPCA assumptions, two simple
extra assumptions (slow subspace change and most outlier magnitudes lower
bounded), and a few minor assumptions.
Our guarantee shows that NORST enjoys a near optimal tracking delay of $O(r
\log n \log(1/\epsilon))$. Its required delay between subspace change times is
the same, and its memory complexity is $n$ times this value. Thus both these
are also nearly optimal. Here $n$ is the ambient space dimension, $r$ is the
subspaces' dimension, and $\epsilon$ is the tracking accuracy. NORST also has
the best outlier tolerance compared with all previous RPCA or RST methods, both
theoretically and empirically (including for real videos), without requiring
any model on how the outlier support is generated. This is possible because of
the extra assumptions it uses.