Kernel K-Means Low Rank Approximation for Spectral Clustering and Diffusion Maps

摘要

Spectral Clustering and Diffusion Maps are currently the leading methods for advanced clustering or dimensionality reduction. However, they require the eigenanalysis of a sample's graph Laplacian L, something very costly for moderately sized samples and prohibitive for very large ones. We propose to build a low rank approximation to L using essentially the centroids obtained applying kernel K-means over the similarity matrix. We call this approach kernel KASP (kKASP) as it follows the KASP procedure of Yan et al. but coupling centroid selection with the local geometry defined by the similarity matrix. As we shall see, kKASP's reconstructions are competitive with KASP's ones, particularly in the low rank range.