Indefinite Parzen Window for Spectral Clustering

Kernel functions used to compute pairwise similarities in spectral clustering and kernel methods are almost exclusively positive semidefinite. We show that for a recent information theoretic spectral clustering algorithm, the theoretically optimal kernel is given by the indefinite Epanechnikov function via Parzen windowing for density estimation. We perform clustering using this indefinite kernel, and report results which show improved performance. Finally, we briefly indicate some properties of the negative spectrum of the corresponding indefinite kernel matrix.