Scalable sparse subspace clustering

In this paper, we address two problems in Sparse Sub-space Clustering algorithm (SSC), i.e., scalability issue and out-of-sample problem. SSC constructs a sparse similar-ity graph for spectral clustering by using ℓ1-minimization based coefficients, has achieved state-of-the-art results for image clustering and motion segmentation. However, the time complexity of SSC is proportion to the cubic of prob-lem size such that it is inefficient to apply SSC into large scale setting. Moreover, SSC does not handle with out-of-sample data that are not used to construct the similarity graph. For each new datum, SSC needs recalculating the cluster membership of the whole data set, which makes SSC is not competitive in fast online clustering. To address the problems, this paper proposes an out-of-sample extension of SSC, named as Scalable Sparse Subspace Clustering (SSS-C), which makes SSC feasible to cluster large scale data sets. The solution of SSSC adopts a ”sampling, clustering, coding, and classifying ” strategy. Extensive experimental results on several popular data sets demonstrate the effec-tiveness and efficiency of our method comparing with the state-of-the-art algorithms. 1