# Provable Dynamic Robust PCA or Robust Subspace Tracking

arXiv: https://arxiv.org/abs/1705.08948 · HTML: https://mlsanity.com/paper/1705.08948/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 May 2017.

## Built on by (most cited first, 5 of 5)

- [The Ideal Continual Learner: An Agent That Never Forgets](https://mlsanity.com/paper/2305.00316/) (2023)
- [Subspace Change-Point Detection via Low-Rank Matrix Factorisation](https://mlsanity.com/paper/2110.04044/) (2021)
- [Byzantine-Resilient Federated PCA and Low Rank Column-wise Sensing](https://mlsanity.com/paper/2309.14512/) (2023)
- [Tuning-Free Online Robust Principal Component Analysis through Implicit Regularization](https://mlsanity.com/paper/2409.07275/) (2024)
- [AltGDmin: Alternating GD and Minimization for Partly-Decoupled (Federated) Optimization](https://mlsanity.com/paper/2504.14741/) (2025)

## Abstract (arXiv)

Dynamic robust PCA refers to the dynamic (time-varying) extension of robust PCA (RPCA). It assumes that the true (uncorrupted) data lies in a low-dimensional subspace that can change with time, albeit slowly. The goal is to track this changing subspace over time in the presence of sparse outliers. We develop and study a novel algorithm, that we call simple-ReProCS, based on the recently introduced Recursive Projected Compressive Sensing (ReProCS) framework. Our work provides the first guarantee for dynamic RPCA that holds under weakened versions of standard RPCA assumptions, slow subspace change and a lower bound assumption on most outlier magnitudes. Our result is significant because (i) it removes the strong assumptions needed by the two previous complete guarantees for ReProCS-based algorithms; (ii) it shows that it is possible to achieve significantly improved outlier tolerance, compared with all existing RPCA or dynamic RPCA solutions by exploiting the above two simple extra assumptions; and (iii) it proves that simple-ReProCS is online (after initialization), fast, and, has near-optimal memory complexity.