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.

A [short version](http://proceedings.mlr.press/v80/narayanamurthy18a.html) will be presented at ICML 2018 (Long Talk). arXiv admin note: text overlap with arXiv:1803.00651

Cited by in corpus (6)

• Robust Subspace Learning: Robust PCA, Robust Subspace Tracking, and Robust Subspace Recovery
• Provable Subspace Tracking from Missing Data and Matrix Completion
• Federated Over-Air Subspace Tracking from Incomplete and Corrupted Data
• Fast Robust Subspace Tracking via PCA in Sparse Data-Dependent Noise
• Online Graph Dictionary Learning
• Provable Low Rank Phase Retrieval