Abstract:
Spectral clustering is one of the most popular algorithims 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. The spectral clustering algorithm is often used as a consistent initializer for more sophisticated clustering algorithims such as EM. However, in this talk, we show that spectral clustering is actually already optimal for the Gaussian Mixture Models, when the number of clusters of is fixed and consistent clustering is possible. Contrary to that the spectral gap conditions are widely assumed in literature to analyze spectral clustering, these conditions are not needed in this work to establish its optimality.