标题： 高斯混合模型中谱聚类的最优性 显示英文标题

标题： Optimality of Spectral Clustering in the Gaussian Mixture Model

摘要： 谱聚类是最受欢迎的用于分组高维数据的算法之一。它易于实现且计算效率高。尽管它非常流行并且有成功的应用案例，但其理论性质尚未被完全理解。在本文中，我们证明当簇的数量固定且信噪比足够大时，谱聚类在具有各向同性协方差矩阵的高斯混合模型中是最优的。文献中广泛假设谱聚类的分析需要谱间隙条件。与此相反，在本文中建立谱聚类最优性时不需这些条件。 显示英文摘要

摘要： Spectral clustering is one of the most popular algorithms to group high dimensional data. It is easy to implement and computationally efficient. Despite its popularity and successful applications, its theoretical properties have not been fully understood. In this paper, we show that spectral clustering is minimax optimal in the Gaussian Mixture Model with isotropic covariance matrix, when the number of clusters is fixed and the signal-to-noise ratio is large enough. Spectral gap conditions are widely assumed in the literature to analyze spectral clustering. On the contrary, these conditions are not needed to establish optimality of spectral clustering in this paper.