A Landmark-based Fast Spectral Clustering Algorithm

Spectral clustering is one of the most important and most popular fundamental algorithms in the field of machine learning and pattern recognition. Spectral clustering converts the problem from clustering to finding the best partition of the connectivity graph. Spectral clustering fully uses the eigenvectors of the similarity matrix describing the similarity between sample pairs to find the cluster information of the graph. With good clustering results and simple implementation, spectral clustering has won its place at the field of image segmentation, face recognition and voice analysis. However, spectral clustering spends intolerable amount of time and space while handling huge size of data due to its maintaining and eigen-decomposing on a dense Laplacian matrix which is quadratic to the number of samples. The poor efficiency of spectral clustering becomes the major bottleneck, which limits its application on industry.In this paper, we analyzed most of the popular accelerative algorithms for spectral clustering. We then proposed a landmark and subspace iteration based fast spectral clustering algorithm following the concept of sparse coding. We build similarity relationship between normal samples and landmark samples which are picked up randomly, and then use sparse coding to redefine the feature of samples. We store the new feature into a sparse flat matrix and perform subspace iteration on it. We found a way to get the top eigenvectors with subspace iteration and without building the full Laplacian matrix.Theoretical analysis and real experiments shows that our algorithm reduces both the time complexity and space complexity to linear with the promise of accuracy of clustering results. Our algorithm produces better results faster than popular algorithms on most of the datasets. We put our algorithm into real practice on image segmentation and achieved competitive results. We finally discussed the further development of our algorithm.