Fast Robust PCA on Graphs

By Nauman Shahid, Nathanael Perraudin, Vassilis Kalofolias, Gilles Puy, Pierre Vandergheynst. 2015

118 citations recorded by the source corpus.

Mining useful clusters from high dimensional data have received significant attention of the computer vision and pattern recognition community in the recent years. Linear and nonlinear 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), nonconvexity (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(n log(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.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Optimization & Training

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Mechanics

In Computer Vision and Pattern Recognition

In Optimization & Training

Citations in the corpus

Geometric Deep Learning on Graphs and Manifolds Using Mixture Model CNNs (2016, methodology): “l eigenfunctions of the Laplacian operator as a generalization of the Fourier basis. Constructions such as wavelets [14, 18, 21, 39, 45] or algorithms such as dictionary learning [62], Lasso [9], PCA [43, 44], or matrix completion [23] originally developed for the Euclidean domain, were also applied”
Data-Driven Tree Transforms and Metrics (2017, methodology): “The field of graph signal processing adapts classical techniques to signals supported on a graph (or a network), such as filtering and wavelets in the graph domain [13]–[22].”
Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset (2015, methodology): “(2015) [324] Shape and Confidence Map-based (SCM-RPCA) Sobral et al.”