Spectral clustering faces a challenging scale issue when sample size is large. Nyström method is the random sapling-based method that is usually applied in such cases. We propose an efficient spectral clustering method using random Fourier features. Our method achieves similar accuracy as Nyström method, but achieves a significant speedup in computations.

Related Publications

• L. He, N. Ray, Y. Guan, H. Zhang, “Fast large-scale spectral clustering via explicit feature mapping,” IEEE Transactions on Cybernetics, 2018.
• L. He, N. Ray, H. Zhang, “Error bound of Nyström-approximated NCut eigenvectors and its application to training size selection,” Neurocomputing, vol.239, pp.130-142, 2017.