# Fast Robust PCA on Graphs

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Jul 2015.

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

- [Cross-Contrastive Clustering for Multimodal Attributed Graphs with Dual Graph Filtering](https://mlsanity.com/paper/2511.20030/) (2025)
- [Spatiotemporal Covariance Neural Networks](https://mlsanity.com/paper/2409.10068/) (2024)
- [Bayesian Low-rank Matrix Completion with Dual-graph Embedding: Prior Analysis and Tuning-free Inference](https://mlsanity.com/paper/2203.10044/) (2022)
- [Network Representation Learning: From Traditional Feature Learning to Deep Learning](https://mlsanity.com/paper/2103.04339/) (2021)
- [To Fold or Not to Fold: Graph Regularized Tensor Train for Visual Data Completion](https://mlsanity.com/paper/2306.11123/) (2023)
- [Matrix Decomposition on Graphs: A Functional View](https://mlsanity.com/paper/2102.03233/) (2021)
- [Variational Bayesian inference for CP tensor completion with side information](https://mlsanity.com/paper/2206.12486/) (2022)
- [Fast and Robust Sparsity-Aware Block Diagonal Representation](https://mlsanity.com/paper/2312.01137/) (2023)
- [Fast unsupervised ground metric learning with tree-Wasserstein distance](https://mlsanity.com/paper/2411.07432/) (2024)
- [New methods for metastimuli: architecture, embeddings, and neural network optimization](https://mlsanity.com/paper/2102.07090/) (2021)
- [Regularisation for PCA- and SVD-type matrix factorisations](https://mlsanity.com/paper/2106.12955/) (2021)
- [Graph-theoretical approach to robust 3D normal extraction of LiDAR data](https://mlsanity.com/paper/2205.11460/) (2022)
- [CoVariance Filters and Neural Networks over Hilbert Spaces](https://mlsanity.com/paper/2509.13178/) (2025)

## Abstract (arXiv)

Mining useful clusters from high dimensional data has received significant attention of the computer vision and pattern recognition community in the recent years. Linear and non-linear dimensionality reduction has played an important role to overcome the curse of dimensionality. However, often such methods are accompanied with three different problems: high computational complexity (usually associated with the nuclear norm minimization), non-convexity (for matrix factorization methods) and susceptibility to gross corruptions in the data. In this paper we propose a principal component analysis (PCA) based solution that overcomes these three issues and approximates a low-rank recovery method for high dimensional datasets. We target the low-rank recovery by enforcing two types of graph smoothness assumptions, one on the data samples and the other on the features by designing a convex optimization problem. The resulting algorithm is fast, efficient and scalable for huge datasets with O(nlog(n)) computational complexity in the number of data samples. It is also robust to gross corruptions in the dataset as well as to the model parameters. Clustering experiments on 7 benchmark datasets with different types of corruptions and background separation experiments on 3 video datasets show that our proposed model outperforms 10 state-of-the-art dimensionality reduction models. Our theoretical analysis proves that the proposed model is able to recover approximate low-rank representations with a bounded error for clusterable data.