# Robust Principal Component Analysis on Graphs

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

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Apr 2015.

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

- [Ensemble Clustering via Co-association Matrix Self-enhancement](https://mlsanity.com/paper/2205.05937/) (2022)
- [Bayesian Low-rank Matrix Completion with Dual-graph Embedding: Prior Analysis and Tuning-free Inference](https://mlsanity.com/paper/2203.10044/) (2022)
- [Learning Spatial-Temporal Regularized Tensor Sparse RPCA for Background Subtraction](https://mlsanity.com/paper/2309.15576/) (2023)
- [Network Representation Learning: From Traditional Feature Learning to Deep Learning](https://mlsanity.com/paper/2103.04339/) (2021)
- [Matrix Decomposition on Graphs: A Functional View](https://mlsanity.com/paper/2102.03233/) (2021)
- [Robust PCA for Anomaly Detection and Data Imputation in Seasonal Time Series](https://mlsanity.com/paper/2208.01998/) (2022)
- [Self-paced Principal Component Analysis](https://mlsanity.com/paper/2106.13880/) (2021)
- [Graph Regularized PCA](https://mlsanity.com/paper/2601.10199/) (2026)
- [Faster Riemannian Newton-type Optimization by Subsampling and Cubic Regularization](https://mlsanity.com/paper/2302.11076/) (2023)
- [Beyond Low-rankness: Guaranteed Matrix Recovery via Modified Nuclear Norm](https://mlsanity.com/paper/2507.18327/) (2025)

## Abstract (arXiv)

Principal Component Analysis (PCA) is the most widely used tool for linear dimensionality reduction and clustering. Still it is highly sensitive to outliers and does not scale well with respect to the number of data samples. Robust PCA solves the first issue with a sparse penalty term. The second issue can be handled with the matrix factorization model, which is however non-convex. Besides, PCA based clustering can also be enhanced by using a graph of data similarity. In this article, we introduce a new model called "Robust PCA on Graphs" which incorporates spectral graph regularization into the Robust PCA framework. Our proposed model benefits from 1) the robustness of principal components to occlusions and missing values, 2) enhanced low-rank recovery, 3) improved clustering property due to the graph smoothness assumption on the low-rank matrix, and 4) convexity of the resulting optimization problem. Extensive experiments on 8 benchmark, 3 video and 2 artificial datasets with corruptions clearly reveal that our model outperforms 10 other state-of-the-art models in its clustering and low-rank recovery tasks.