Evolutionary Self-Expressive Models for Subspace Clustering

Abstract

The problem of organizing data that evolves over time into clusters is encountered in a number of practical settings. We introduce evolutionary subspace clustering, a method whose objective is to cluster a collection of evolving data points that lie on a union of low-dimensional evolving subspaces. To learn the parsimonious representation of the data points at each time step, we propose a non-convex optimization framework that exploits the self-expressiveness property of the evolving data while taking into account representation from the preceding time step. To find an approximate solution to the aforementioned non-convex optimization problem, we develop a scheme based on alternating minimization that both learns the parsimonious representation as well as adaptively tunes and infers a smoothing parameter reflective of the rate of data evolution. The latter addresses a fundamental challenge in evolutionary clustering -- determining if and to what extent one should consider previous clustering solutions when analyzing an evolving data collection. Our experiments on both synthetic and real-world datasets demonstrate that the proposed framework outperforms state-of-the-art static subspace clustering algorithms and existing evolutionary clustering schemes in terms of both accuracy and running time, in a range of scenarios.

References in corpus (17)

• Robust Recovery of Subspace Structures by Low-Rank Representation
• Alternating Direction Algorithms for ${\ell }_1$-Problems in Compressive Sensing
• A geometric analysis of subspace clustering with outliers
• Submodular meets Spectral: Greedy Algorithms for Subset Selection, Sparse Approximation and Dictionary Selection
• Structured Sparse Subspace Clustering: A Joint Affinity Learning and Subspace Clustering Framework
• Robust PCA via Outlier Pursuit
• Robust subspace clustering
• GED: the method for group evolution discovery in social networks
• Adaptive Evolutionary Clustering
• High Dimensional Low Rank plus Sparse Matrix Decomposition
• Randomized Robust Subspace Recovery for High Dimensional Data Matrices
• Greedy Subspace Clustering
• Innovation Pursuit: A New Approach to Subspace Clustering
• Active Orthogonal Matching Pursuit for Sparse Subspace Clustering
• Noisy subspace clustering via matching pursuits
• Subspace Clustering with Missing and Corrupted Data
• Accelerated Sparse Subspace Clustering

Cited by in corpus (4)

• Evolutionary Robust Clustering Over Time for Temporal Data
• Neural Ordinary Differential Equation Model for Evolutionary Subspace Clustering and Its Applications
• LSTM-Assisted Evolutionary Self-Expressive Subspace Clustering
• Performance-Complexity Tradeoffs in Greedy Weak Submodular Maximization with Random Sampling