English
 
Help Privacy Policy Disclaimer
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Conference Paper

On the Convergence of Spectral Clustering on Random Samples: The Normalized Case

MPS-Authors
/persons/resource/persons76237

von Luxburg,  U
Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society;
Max Planck Institute for Biological Cybernetics, Max Planck Society;

/persons/resource/persons83824

Bousquet,  O
Department Empirical Inference, Max Planck Institute for Biological Cybernetics, Max Planck Society;
Max Planck Institute for Biological Cybernetics, Max Planck Society;

Fulltext (public)
There are no public fulltexts stored in PuRe
Supplementary Material (public)
There is no public supplementary material available
Citation

von Luxburg, U., Bousquet, O., & Belkin, M. (2004). On the Convergence of Spectral Clustering on Random Samples: The Normalized Case. In J. Shawe-Taylor, & Y. Singer (Eds.), Learning Theory: 17th Annual Conference on Learning Theory, COLT 2004, Banff, Canada, July 1-4 (pp. 457-471). Berlin, Germany: Springer.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0013-F382-8
Abstract
Given a set of n randomly drawn sample points, spectral clustering in its simplest form uses the second eigenvector of the graph Laplacian matrix, constructed on the similarity graph between the sample points, to obtain a partition of the sample. We are interested in the question how spectral clustering behaves for growing sample size n. In case one uses the normalized graph Laplacian, we show that spectral clustering usually converges to an intuitively appealing limit partition of the data space. We argue that in case of the unnormalized graph Laplacian, equally strong convergence results are difficult to obtain.