Abstract: The advantage of the traditional spectral clustering algorithm is applicable in the small scale data set. A new method was proposed in the light of the laplacian matrix characteristics. First, a new Gram matrix was reconstructed and some lies of the new matrix were needed, then the eigen-decomposition based on accelerating iterative method was solved. The calculation speed of the proposed method is very fast and the space complexity is small for large scale data set

Key words: Clustering, Spectral clustering, Large-scale data set, Accelerating iterative method, Laplacian matrix