The Mathematics Behind Spectral Clustering And The Equivalence To PCA

Spectral clustering is a popular algorithm that can be easily solved by standard linear algebra methods. Despite its simplicity, spectral clustering has been working mysteriously. For years, different papers try to explain it from different views. Shi and Malik(2000)[2] use the normalized cuts to measure the total dissimilarity between different groups and the total similarity within groups. By relaxing indicator vectors to real values, the optimization problem becomes a generalized eigenvalue problem. However, there is no guarantee on the quality of the relaxed problem's solution compared to the exact solution(von Luxburg, 2007)[6]. Meilan and Shi(2001)[4] provide a random walk view of spectral segmentation by interpreting the similarities as edge flows in a Markov random walk and prove the equivalence between the spectral problem formulated by the normalized cuts method and the eigenvalues/eigenvectors of the transition matrix of the random walk.