Today’s post will be concerned with the clustering problem. Suppose one has a data set and wants to split the set into two “meaningful” clusters. We will show how the eigenvectors of the graph Laplacian can provide such a clustering, giving an efficient method for clustering. The result that guarantees the performance of this method is inspired in an isoperimetric inequality proved in the late 60’s. This post is tightly related to my previous post about Spectral Clustering and Diffusion Maps.

Continue reading Cheeger Inequality and Spectral Clustering