On Spectral Clustering: Analysis and an algorithm

"On Spectral Clustering: Analysis and an algorithm", Andrew Y. Ng, Michael I. Jordan, Yair Weiss, NIPS 2001

Based on the spectral methods which use the top eigenvectors of a matrix corresponding to the similarity between some features, the paper proposes a simple spectral clustering algorithm to utilize the k eigenvectors simultaneously.
There are several steps:
1.Construct an affinity matrix defined by Gaussian kernel.
2.Set the covariance matrix by the affinity matrix.
3.Find the eigenvectors of the covariance matrix and do normalization.
4.Cluster the eigenvectors via k-means method.
5.Assign the original points to corresponding clusters.

Moreover, under some assumption and analyses, they say that the final clusters will be tight and the k well-separated points will be on the surface of the k-sphere according to their “true” clusters.