Fast spectral clustering via the Nyström method

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

doi:10.1007/978-3-642-40935-6_26

Fast spectral clustering via the Nyström method

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

Electrical and Computer Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Abstract

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 language	English (US)
Title of host publication	Algorithmic Learning Theory - 24th International Conference, ALT 2013, Proceedings
Pages	367-381
Number of pages	15
DOIs	https://doi.org/10.1007/978-3-642-40935-6_26
State	Published - 2013
Event	24th International Conference on Algorithmic Learning Theory, ALT 2013 - Singapore, Singapore Duration: Oct 6 2013 → Oct 9 2013

Publication series

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

Other

Other	24th International Conference on Algorithmic Learning Theory, ALT 2013
Country/Territory	Singapore
City	Singapore
Period	10/6/13 → 10/9/13

Keywords

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

Access to Document

10.1007/978-3-642-40935-6_26

Cite this

Choromanska, A., Jebara, T., Kim, H., Mohan, M., & Monteleoni, C. (2013). Fast spectral clustering via the Nyström method. In Algorithmic Learning Theory - 24th International Conference, ALT 2013, Proceedings (pp. 367-381). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8139 LNAI). https://doi.org/10.1007/978-3-642-40935-6_26

Fast spectral clustering via the Nyström method. / Choromanska, Anna; Jebara, Tony; Kim, Hyungtae et al.
Algorithmic Learning Theory - 24th International Conference, ALT 2013, Proceedings. 2013. p. 367-381 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 8139 LNAI).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Choromanska, A, Jebara, T, Kim, H, Mohan, M & Monteleoni, C 2013, Fast spectral clustering via the Nyström method. in Algorithmic Learning Theory - 24th International Conference, ALT 2013, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 8139 LNAI, pp. 367-381, 24th International Conference on Algorithmic Learning Theory, ALT 2013, Singapore, Singapore, 10/6/13. https://doi.org/10.1007/978-3-642-40935-6_26

Choromanska A, Jebara T, Kim H, Mohan M, Monteleoni C. Fast spectral clustering via the Nyström method. In Algorithmic Learning Theory - 24th International Conference, ALT 2013, Proceedings. 2013. p. 367-381. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-642-40935-6_26

@inproceedings{e8aced51b3df43d2938b81e1fffae40b,

title = "Fast spectral clustering via the Nystr{\"o}m method",

abstract = "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{\"o}m methods commonly used to obtain good quality low rank approximations of large matrices. The proposed algorithm applies the Nystr{\"o}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.",

keywords = "Nystr{\"o}m method, error bounds, large-scale clustering, performance guarantees, sampling, sparsity, spectral clustering, unsupervised learning",

author = "Anna Choromanska and Tony Jebara and Hyungtae Kim and Mahesh Mohan and Claire Monteleoni",

year = "2013",

doi = "10.1007/978-3-642-40935-6_26",

language = "English (US)",

isbn = "9783642409349",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

pages = "367--381",

booktitle = "Algorithmic Learning Theory - 24th International Conference, ALT 2013, Proceedings",

}

TY - GEN

T1 - Fast spectral clustering via the Nyström method

AU - Choromanska, Anna

AU - Jebara, Tony

AU - Kim, Hyungtae

AU - Mohan, Mahesh

AU - Monteleoni, Claire

PY - 2013

Y1 - 2013

N2 - 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.

AB - 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.

KW - Nyström method

KW - error bounds

KW - large-scale clustering

KW - performance guarantees

KW - sampling

KW - sparsity

KW - spectral clustering

KW - unsupervised learning

UR - http://www.scopus.com/inward/record.url?scp=84887422889&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84887422889&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-40935-6_26

DO - 10.1007/978-3-642-40935-6_26

M3 - Conference contribution

AN - SCOPUS:84887422889

SN - 9783642409349

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 367

EP - 381

BT - Algorithmic Learning Theory - 24th International Conference, ALT 2013, Proceedings

T2 - 24th International Conference on Algorithmic Learning Theory, ALT 2013

Y2 - 6 October 2013 through 9 October 2013

ER -

Fast spectral clustering via the Nyström method

Abstract

Publication series

Other

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this