AAAI Publications, Twenty-Eighth AAAI Conference on Artificial Intelligence

Font Size: 
Exact Subspace Clustering in Linear Time
Shusen Wang, Bojun Tu, Congfu Xu, Zhihua Zhang

Last modified: 2014-06-21


Subspace clustering is an important unsupervised learning problem with wide applications in computer vision and data analysis. However, the state-of-the-art methods for this problem suffer from high time complexity---quadratic or cubic in $n$ (the number of data instances). In this paper we exploit a data selection algorithm to speedup computation and the robust principal component analysis to strengthen robustness. Accordingly, we devise a scalable and robust subspace clustering method which costs time only linear in $n$. We prove theoretically that under certain mild assumptions our method solves the subspace clustering problem exactly even for grossly corrupted data. Our algorithm is based on very simple ideas, yet it is the only linear time algorithm with noiseless or noisy recovery guarantee. Finally, empirical results verify our theoretical analysis.


subspace clustering

Full Text: PDF