Accelerated Sparse Subspace Clustering

2017/10/31 by Hashemi, Abolfazl, Vikalo, Haris
#Computer Vision and Pattern Recognition (cs.CV) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1711.00126

Abstract

State-of-the-art algorithms for sparse subspace clustering perform spectral clustering on a similarity matrix typically obtained by representing each data point as a sparse combination of other points using either basis pursuit (BP) or orthogonal matching pursuit (OMP). BP-based methods are often prohibitive in practice while the performance of OMP-based schemes are unsatisfactory, especially in settings where data points are highly similar. In this paper, we propose a novel algorithm that exploits an accelerated variant of orthogonal least-squares to efficiently find the underlying subspaces. We show that under certain conditions the proposed algorithm returns a subspace-preserving solution. Simulation results illustrate that the proposed method compares favorably with BP-based method in terms of running time while being significantly more accurate than OMP-based schemes.

Related

• Scalable Sparse Subspace Clustering by Orthogonal Matching Pursuit
• A Novel Efficient Approach with Data-Adaptive Capability for OMP-based Sparse Subspace Clustering
• Greedier is Better: Selecting Multiple Neighbors per Iteration for Sparse Subspace Clustering
• Research on Clustering Performance of Sparse Subspace Clustering
• Weighted Sparse Subspace Representation: A Unified Framework for Subspace Clustering, Constrained Clustering, and Active Learning