Fast spectral clustering via the Nyström method

Anna Choromanska, Tony Jebara, Hyungtae Kim, Mahesh Mohan, Claire Monteleoni

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We propose and analyze a fast spectral clustering algorithm with computational complexity linear in the number of data points that is directly applicable to large-scale datasets. The algorithm combines two powerful techniques in machine learning: spectral clustering algorithms and Nyström methods commonly used to obtain good quality low rank approximations of large matrices. The proposed algorithm applies the Nyström approximation to the graph Laplacian to perform clustering. We provide theoretical analysis of the performance of the algorithm and show the error bound it achieves and we discuss the conditions under which the algorithm performance is comparable to spectral clustering with the original graph Laplacian. We also present empirical results.

Original languageEnglish (US)
Title of host publicationAlgorithmic Learning Theory - 24th International Conference, ALT 2013, Proceedings
Number of pages15
StatePublished - 2013
Event24th International Conference on Algorithmic Learning Theory, ALT 2013 - Singapore, Singapore
Duration: Oct 6 2013Oct 9 2013

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume8139 LNAI
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Other24th International Conference on Algorithmic Learning Theory, ALT 2013


  • Nyström method
  • error bounds
  • large-scale clustering
  • performance guarantees
  • sampling
  • sparsity
  • spectral clustering
  • unsupervised learning

ASJC Scopus subject areas

  • Theoretical Computer Science
  • General Computer Science


Dive into the research topics of 'Fast spectral clustering via the Nyström method'. Together they form a unique fingerprint.

Cite this