Gao, Wei; Zhou, Dingxuan Convergence of spectral clustering with a general similarity function. (Chinese. English summary) Zbl 1488.68043 Sci. Sin., Math. 42, No. 10, 985-994 (2012). Summary: Spectral clustering algorithms are generated by eigenfunctions of graph Laplacians associated with similarity functions. In this paper, we prove the convergence of the spectral clustering associated with a general similarity function, and give quantitative estimates for the convergence based on a covering number argument. When the similarity function is Lipschitz \(s>0\) on a subset of a Euclidean space, a convergence rate of \(O(\sqrt{\log(n+1)}/\sqrt{n})\) is verified. We also show that the covering numbers of an involved function set may behave as badly as possible. Cited in 2 Documents MSC: 68T05 Learning and adaptive systems in artificial intelligence 05C50 Graphs and linear algebra (matrices, eigenvalues, etc.) 62H30 Classification and discrimination; cluster analysis (statistical aspects) Keywords:spectral clustering; graph Laplacian; similarity function; rate of convergence; covering number PDFBibTeX XMLCite \textit{W. Gao} and \textit{D. Zhou}, Sci. Sin., Math. 42, No. 10, 985--994 (2012; Zbl 1488.68043) Full Text: DOI