Active Orthogonal Matching Pursuit for Sparse Subspace Clustering

Abstract

Sparse Subspace Clustering (SSC) is a state-of-the-art method for clustering high-dimensional data points lying in a union of low-dimensional subspaces. However, while ${\ell }_1$ optimization-based SSC algorithms suffer from high computational complexity, other variants of SSC, such as Orthogonal Matching Pursuit-based SSC (OMP-SSC), lose clustering accuracy in pursuit of improving time efficiency. In this letter, we propose a novel Active OMP-SSC, which improves clustering accuracy of OMP-SSC by adaptively updating data points and randomly dropping data points in the OMP process, while still enjoying the low computational complexity of greedy pursuit algorithms. We provide heuristic analysis of our approach, and explain how these two active steps achieve a better tradeoff between connectivity and separation. Numerical results on both synthetic data and real-world data validate our analyses and show the advantages of the proposed active algorithm.

14 pages, 5 figures, 1 table

References in corpus (4)

• Structured Sparse Subspace Clustering: A Joint Affinity Learning and Subspace Clustering Framework
• Greedy Subspace Clustering
• Restricted Isometry Property of Gaussian Random Projection for Finite Set of Subspaces
• A Theoretical Analysis of Noisy Sparse Subspace Clustering on Dimensionality-Reduced Data

Cited by in corpus (6)

• Scalable and Robust Sparse Subspace Clustering Using Randomized Clustering and Multilayer Graphs
• Efficient Solvers for Sparse Subspace Clustering
• A fast and Accurate Similarity-constrained Subspace Clustering Framework for Unsupervised Hyperspectral Image Classification
• Evolutionary Self-Expressive Models for Subspace Clustering
• Restricted Connection Orthogonal Matching Pursuit For Sparse Subspace Clustering
• Theory of Spectral Method for Union of Subspaces-Based Random Geometry Graph