Fast Robust Subspace Tracking via PCA in Sparse Data-Dependent Noise

Namrata Vaswani, Praneeth NarayanamurthyIEEE J. Sel. Areas Inf. Theory 2020 · DOI

TL;DR

This paper introduces NORST, a novel algorithm for robustly tracking changing low-dimensional subspaces in data corrupted by sparse outliers and data-dependent noise. NORST achieves near-optimal detection and tracking delays with computational complexity comparable to standard PCA, making it significantly faster and more efficient than existing methods for real-time applications.

What Problem Does This Paper Address?

Many real-world applications, such as video surveillance, involve analyzing data that lies in a low-dimensional subspace, but this data is often corrupted by outliers (e.g., moving objects in a background scene) and, more subtly, by noise that depends on the underlying data itself. Tracking how this subspace changes over time is crucial, but existing methods for "robust subspace tracking" (ST) either require restrictive assumptions, have significant delays, or are computationally too expensive for real-time use. This paper tackles the challenge of developing a fast, provably correct algorithm that can handle both sparse outliers and data-dependent noise while achieving near-optimal tracking performance.

Methods

The core of the paper is the NORST (Nearly Optimal Robust Subspace Tracking) algorithm. It's a mini-batch approach that iteratively performs two main steps:

  1. Robust Regression (Projected Compressive Sensing): At each time step, NORST uses the previous subspace estimate to project the incoming data, effectively isolating the outlier component. It then employs a sparse recovery technique (l1 minimization) to estimate the sparse outlier and its support, followed by a least-squares step to refine the outlier estimate. This allows for the estimation of the "clean" data component.
  2. Subspace Update: Periodically (in mini-batches), NORST uses the estimated clean data components to update the subspace estimate via PCA (specifically, r-SVD).

A key innovation is the development of a novel non-asymptotic guarantee for PCA in the presence of data-dependent noise. This theoretical result is crucial for analyzing the performance of NORST, particularly when the noise is sparse and its support changes over time. The algorithm also incorporates a "subspace change detection" mechanism to adapt to significant shifts in the underlying subspace.

Datasets

The paper evaluates its methods on:

  • Synthetic Data: Generated to simulate various scenarios, including moving object models and Bernoulli models for outlier distribution, with varying outlier magnitudes and fractions.
  • Real-World Data:
    • Meeting Room (MR) and Lobby (LB) video sequences: Used for background subtraction tasks, demonstrating NORST's ability to handle real-world video data with challenging foreground/background similarities and occlusions.

Key Insights and Ideas

  • Data-Dependent Noise is a Real Challenge: The paper highlights that ignoring the data-dependent nature of noise can lead to suboptimal performance, especially when this noise has changing support.
  • Statistical Right Incoherence is Sufficient: Instead of requiring strict geometric incoherence of the subspace basis, the authors show that a statistical version is enough for robust tracking, which is more practical.
  • Near-Optimal Delays are Achievable: NORST demonstrates that subspace change detection and tracking can be performed with delays that are only logarithmically larger than the theoretical minimum, a significant improvement over prior work.
  • Computational Efficiency is Key: The algorithm's time complexity is on par with standard PCA, making it suitable for real-time applications where many existing robust methods are too slow.
  • Piecewise Constant Subspaces Simplify Analysis: The assumption that subspaces remain constant for a period simplifies theoretical guarantees, but the authors also discuss extensions for more dynamic scenarios.

Key Results

  • Theoretical Guarantees: NORST is proven to be correct under mild assumptions, providing near-optimal detection and tracking delays.
  • Computational Speed: The algorithm's time complexity is O(ndr log(1/ε)), comparable to non-robust PCA.
  • Improved Outlier Tolerance: Empirical results show NORST can tolerate a significantly higher fraction of outliers per row compared to methods like AltProj.
  • Superior Performance: NORST outperforms existing robust subspace tracking and RPCA methods (s-ReProCS, ORPCA, GRASTA, PCP, AltProj, RPCA-GD) in terms of subspace error, especially in challenging scenarios with data-dependent noise and significant subspace changes.
  • Real-World Effectiveness: Demonstrated success in background subtraction tasks on real video datasets, outperforming other methods.

Limitations and Future Work

  • Initialization: NORST requires an initial subspace estimate, which is typically obtained using existing RPCA algorithms like AltProj. The quality of this initial estimate can impact performance.
  • Subspace Change Magnitude: While NORST handles slow subspace changes well, very rapid or large changes might require more iterations or larger mini-batches.
  • Parameter Tuning: Like many algorithms, NORST has parameters (e.g., mini-batch size, sparsity threshold) that need to be set. The paper provides theoretical guidance but practical tuning might still be necessary.
  • Future Directions: The authors suggest extending the work to handle more general noise models, exploring online updates without explicit change detection, and further investigating applications with missing data. They also note that the "identically distributed" assumption on noise and coefficients can be relaxed.

Summary updated

BibTeX
@article{vaswani2020fast,
  author = {Namrata Vaswani and Praneeth Narayanamurthy},
  title = {{Fast Robust Subspace Tracking via PCA in Sparse Data-Dependent Noise}},
  journal = {IEEE J. Sel. Areas Inf. Theory},
  year = {2020},
  doi = {10.1109/jsait.2020.3040365},
}
Figure