Exact Subspace Clustering in Linear Time

Authors

  • Shusen Wang Zhejiang University
  • Bojun Tu Zhejiang University
  • Congfu Xu Zhejiang University
  • Zhihua Zhang Shanghai Jiao Tong University

DOI:

https://doi.org/10.1609/aaai.v28i1.8963

Keywords:

subspace clustering

Abstract

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.

Downloads

Published

2014-06-21

How to Cite

Wang, S., Tu, B., Xu, C., & Zhang, Z. (2014). Exact Subspace Clustering in Linear Time. Proceedings of the AAAI Conference on Artificial Intelligence, 28(1). https://doi.org/10.1609/aaai.v28i1.8963

Issue

Section

Main Track: Novel Machine Learning Algorithms