Learned Robust PCA: A Scalable Deep Unfolding Approach for High-Dimensional Outlier Detection

HanQin Cai, Jialin Liu, Wotao Yin

TL;DR

Researchers have developed Learned Robust PCA (LRPCA), a deep-learning-enhanced approach to separating low-rank data from sparse outliers. By "unfolding" a non-convex optimization algorithm into a novel hybrid neural network, LRPCA achieves state-of-the-art speed and accuracy on high-dimensional data without the massive computational overhead of traditional SVD-based methods.

What Problem Does This Paper Address?

Robust Principal Component Analysis (RPCA) is a workhorse in machine learning, used for everything from removing glare in faces to separating moving objects from static backgrounds in video. Mathematically, it tries to decompose a corrupted matrix $Y$ into a low-rank component $X$ (the "clean" data) and a sparse component $S$ (the outliers).

However, RPCA faces a "Goldilocks" problem. Traditional convex methods are mathematically elegant but painfully slow because they require Singular Value Decomposition (SVD) at every step—a massive bottleneck for high-dimensional data. Newer non-convex methods are faster but notoriously difficult to tune; picking the right step sizes and thresholds often feels like guesswork. Furthermore, existing "deep unfolding" attempts (which turn algorithms into neural networks) still rely on those slow SVD steps, making them unscalable for large-scale real-world applications.

Methods

The authors introduce LRPCA, which stands out through three key innovations:

  1. SVD-Free Architecture: Instead of performing an SVD on the whole matrix, LRPCA factorizes the low-rank component into two smaller matrices ($X = LR^\top$). This reduces the computational complexity from $O(n^3)$ to $O(n^2r)$, where $r$ is the rank.
  2. Differentiable Thresholding: Traditional algorithms use "hard-thresholding" (sorting and picking the top $k$ values), which is not differentiable and thus can't be trained via backpropagation. LRPCA uses soft-thresholding, allowing the model to learn the optimal outlier-detection parameters directly from data.
  3. The FRMNN Model: Most unfolded networks have a fixed number of layers (iterations). If you need more accuracy, you're out of luck. The authors proposed a Feedforward-Recurrent-Mixed Neural Network. It uses unique "feedforward" layers for the first few critical iterations and then transitions into "recurrent" layers with tied parameters. This allows the model to run for "infinite" iterations until a desired accuracy is reached, without needing to be retrained for different depths.

Datasets

The authors evaluated LRPCA on three main fronts:

  • Synthetic Data: Randomly generated low-rank matrices corrupted with varying levels of sparse outliers to test the limits of recovery.
  • VIRAT Video Dataset: A benchmark for video background subtraction. They used 65 videos for training and 4 for verification, vectorizing frames to create high-dimensional matrices.
  • Ultrasound Imaging: A specialized dataset of 3,200 examples used to compare LRPCA against CORONA, a previous state-of-the-art learning-based RPCA method.

Key Insights and Ideas

  • Learning Beats Hand-Tuning: By training on data, LRPCA finds "aggressive" step sizes and precise thresholds that a human would likely never find manually. This leads to much faster convergence.
  • Linear Convergence is Preserved: The authors didn't just build a black-box neural network; they provided a theoretical proof (Theorem 1) showing that LRPCA maintains a linear convergence rate under standard assumptions like incoherence and sparsity.
  • Scalability is the Killer App: Because LRPCA avoids SVDs and uses efficient matrix multiplications, it can handle video resolutions and matrix sizes that cause other learning-based RPCA methods to crash or take hours to process.

Key Results

  • Superior Robustness: On synthetic tests, LRPCA successfully recovered data with up to 60% outlier density, whereas the baseline ScaledGD failed once outliers exceeded 45%.
  • Massive Speedups: In video background subtraction, LRPCA was roughly 15x to 20x faster than ScaledGD and 4x to 5x faster than AltProj. For example, on the "ParkingLot1" video, LRPCA finished in 16 seconds compared to ScaledGD’s 260 seconds.
  • Inference Efficiency: Compared to CORONA (the previous deep-learning benchmark), LRPCA’s average inference time was 0.0057 seconds vs. CORONA’s 0.9225 seconds—a nearly 160x improvement.

Limitations and Future Work

The primary limitation is that LRPCA requires the rank ($r$) of the underlying data to be known or estimated beforehand. If the rank is significantly misestimated, performance drops.

For future work, the authors suggest exploring stochastic versions of the algorithm to handle even larger datasets that don't fit in memory. They also see potential in extending this framework to Robust Tensor PCA, moving from 2D matrices to multi-dimensional data arrays.

Summary updated

Abstract

Robust principal component analysis (RPCA) is a critical tool in modern machine learning, which detects outliers in the task of low-rank matrix reconstruction. In this paper, we propose a scalable and learnable non-convex approach for high-dimensional RPCA problems, which we call Learned Robust PCA (LRPCA). LRPCA is highly efficient, and its free parameters can be effectively learned to optimize via deep unfolding. Moreover, we extend deep unfolding from finite iterations to infinite iterations via a novel feedforward-recurrent-mixed neural network model. We establish the recovery guarantee of LRPCA under mild assumptions for RPCA. Numerical experiments show that LRPCA outperforms the state-of-the-art RPCA algorithms, such as ScaledGD and AltProj, on both synthetic datasets and real-world applications.
BibTeX
@inproceedings{cai2021learned,
  author = {HanQin Cai and Jialin Liu and Wotao Yin},
  title = {{Learned Robust PCA: A Scalable Deep Unfolding Approach for High-Dimensional Outlier Detection}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2021},
  url = {https://openreview.net/forum?id=FViOz7g8AWY},
}

Loading related content...

Figure