Provable Dynamic Robust PCA or Robust Subspace Tracking

Praneeth Narayanamurthy, Namrata Vaswani
5/24/2017
cs.ITstat.ML

Official code: andrewssobral/lrslibrary (887 stars, last commit 2025-11-22). 1 more implementation below.

Abstract

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.

View on arXivView PDF

Code Implementations(2)

andrewssobral/lrslibraryOfficial100%

Low-Rank and Sparse Tools for Background Modeling and Subtraction in Videos

887377C, MNov 7, 201411 months ago
matlabmatrixmatrix-completionmatrix-factorizationrpca+4 more
praneethmurthy/ReProCSOfficial100%
MIT

MATLAB implementation of "Provable Dynamic Robust PCA or Robust Subspace tracking", IEEE Transactions on Information Theory, 2019.

208C, C++Sep 7, 20176 years agoMIT
matrix-factorizationrobust-pcarobust-regresssionsubspace-analysissubspace-tracking

Similar Papers

On the Convergence of IRLS and Its Variants in Outlier-Robust Estimation

79% match2023

RANSAC Revisited: An Improved Algorithm for Robust Subspace Recovery under Adversarial and Noisy Corruptions

78% match1 repo302025

Corruption-Robust Offline Reinforcement Learning with General Function Approximation

78% match2023

Optimal Robust Estimation under Local and Global Corruptions: Stronger Adversary and Smaller Error

78% match2024

Verifying Properties of Binary Neural Networks Using Sparse Polynomial Optimization

78% match2024

Rotation-Based Subspace Tracking for Robust Kernel PCA on Streaming Data

78% match2026

Cite this paper

@article{narayanamurthy2017provable,
  title  = {Provable Dynamic Robust PCA or Robust Subspace Tracking},
  author = {Praneeth Narayanamurthy and Namrata Vaswani},
  year   = {2017},
  eprint = {1705.08948},
  archivePrefix = {arXiv},
  url    = {https://arxiv.org/abs/1705.08948}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/1705.08948.svg)](https://codeofpaper.com/paper/1705.08948)

Discussion