On the Convergence of Spectral Clustering on Random Samples: The Normalized Case
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.
Cite
Text
von Luxburg et al. "On the Convergence of Spectral Clustering on Random Samples: The Normalized Case." Annual Conference on Computational Learning Theory, 2004. doi:10.1007/978-3-540-27819-1_32Markdown
[von Luxburg et al. "On the Convergence of Spectral Clustering on Random Samples: The Normalized Case." Annual Conference on Computational Learning Theory, 2004.](https://mlanthology.org/colt/2004/vonluxburg2004colt-convergence/) doi:10.1007/978-3-540-27819-1_32BibTeX
@inproceedings{vonluxburg2004colt-convergence,
title = {{On the Convergence of Spectral Clustering on Random Samples: The Normalized Case}},
author = {von Luxburg, Ulrike and Bousquet, Olivier and Belkin, Mikhail},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2004},
pages = {457-471},
doi = {10.1007/978-3-540-27819-1_32},
url = {https://mlanthology.org/colt/2004/vonluxburg2004colt-convergence/}
}