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.

Normalized Cuts and Image Segmentation

"Normalized Cuts and Image Segmentation", Jianbo Shi and Jitendra Malik, Trans. PAMI 2000

The paper proposes a general framework for image segmentation. Generally, the result of each partition method is affected by the coherence of brightness, color, texture, or motion, and the hierarchical partition should form a tree structure. Therefore, the authors generate a graph theoretic formulation of grouping.

The grouping algorithm consists of several steps:
1.Given an image, set up a weighted graph, and set the weight on the edge according to the similarity.
2.solve the equation for eigenvectors with the smaller eigenvalues.
3.Here they use the eigenvector with the second smallest eigenvalue to bipartition the graph and solve the normalized cut problem.
4.Recursively partition if necessary.

If necessary, one can use all of the to eigenvectors to obtain a K-way partition and follow the modified algorithm.
The computational approach that they have developed uses matrix theory and linear algebra which are based on the concepts from spectral graph theory.