Robust Principal Component Analysis on Graphs

By Nauman Shahid, Vassilis Kalofolias, Xavier Bresson, Michael M. Bronstein, Pierre Vandergheynst. 2015

123 citations recorded by the source corpus.

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.

Subfields: Computational Mechanics, Computer Vision and Pattern Recognition, Media Technology, Probabilistic & Bayesian Methods

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 Media Technology

In Probabilistic & Bayesian Methods

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”
Fast Robust PCA on Graphs (2015, unknown): “In fact, for PCA, this can be considered as a method of exploiting the local smoothness information in order to improve clustering quality.”
How to Learn a Graph from Smooth Signals (2016, methodology): “We present efficient, scalable primal-dual based algorithms for both our model and the previous state of the art, and evaluate their performance on artificial and real data.”
Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset (2015, methodology): “To take into account both spatial and temporal coherence, strategies can be classified as follows: (a) combination the methods of (1) and (2) like spatiotemporal IRLS [131], SCM-RPCA [348] and GSRPCALSD [240], (b) spatio-temporal coherency clues based approaches like in SMD-RPCA [60], c) graph-based”