Fast Robust PCA on Graphs
arXiv:1507.08173 · doi:10.1109/JSTSP.2016.2555239
Abstract
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.
References in corpus (4)
Cited by in corpus (29)
- Decomposition into Low-rank plus Additive Matrices for Background/Foreground Separation: A Review for a Comparative Evaluation with a Large-Scale Dataset
- Stationary signal processing on graphs
- Graph Multiview Canonical Correlation Analysis
- Spectral Domain Sampling of Graph Signals
- Two-Channel Critically-Sampled Graph Filter Banks With Spectral Domain Sampling
- Large Scale Graph Learning from Smooth Signals
- Geometric deep learning on graphs and manifolds using mixture model CNNs
- Canonical Correlation Analysis of Datasets with a Common Source Graph
- Nonlinear Dimensionality Reduction for Discriminative Analytics of Multiple Datasets
- Multi-way Graph Signal Processing on Tensors: Integrative analysis of irregular geometries
- Joint Time-Vertex Fractional Fourier Transform
- Graph Learning for Spatiotemporal Signals with Long- and Short-Term Characterization
- Hilbert Transform, Analytic Signal, and Modulation Analysis for Graph Signal Processing
- Spatiotemporal Covariance Neural Networks
- Knowledge-Based Distant Regularization in Learning Probabilistic Models
- Joint Estimation of Low-Rank Components and Connectivity Graph in High-Dimensional Graph Signals: Application to Brain Imaging
- Simultaneous Low-rank Component and Graph Estimation for High-dimensional Graph Signals: Application to Brain Imaging
- A Time-Vertex Signal Processing Framework
- Going off the Grid: Iterative Model Selection for Biclustered Matrix Completion
- Matrix Decomposition on Graphs: A Functional View
- Depth Restoration: A fast low-rank matrix completion via dual-graph regularization
- Connecting Graph Convolutional Networks and Graph-Regularized PCA
- Robust On-line Matrix Completion on Graphs
- Compressive PCA for Low-Rank Matrices on Graphs
- Regularisation for PCA- and SVD-type matrix factorisations
- Data-Driven Tree Transforms and Metrics
- Network Representation Learning: From Traditional Feature Learning to Deep Learning
- Time-Varying Graph Learning with Constraints on Graph Temporal Variation
- Nonlinear Dimensionality Reduction on Graphs