Moderna spektrala partitioneringsalgoritmer

Spectral clustering, as a particular method in unsupervised learning, has been successfully applied in many fields due to its ability to capture complicated structures in data through graph-based representations. Traditionally, spectral clustering relies on the Kmeans algorithm to post-process the eigenvectors of the standard graph Laplacian. In this thesis, we investigate and compare several advanced clustering algorithms applied to the spectral embeddings derived from both the standard Laplacian and the generalized non-linear graph p-Laplacian. The first algorithm uses the column-pivoted QR (CPQR) factorization to select representative coordinate directions encoded in the eigenvectors of the graph Laplacian. The second constructs an indicator matrix from the eigenvector matrix by solving a minimization problem. These methods are designed to address limitations of the conventional Kmeans approach, particularly its sensitivity to initialization and its poor performance on non-convex structures. The theoretical background of these algorithms are briefly explained, and we evaluate these methods across synthetic and real-world benchmark datasets, analyzing clustering quality and computational complexity. The results demonstrate that these algorithms outperforms the standard Kmeans algorithm for standard graph Laplacian. Applying them to the graph p-Laplacian can significantly improve clustering performance in datasets with non-convex structures, but the improvement over Kmeans becomes minimal. Furthermore, it suffers from a much higher computational cost due to the procedure of solving a nonlinear eigenvalue problem.