Kernelised covariance matrices, dimension reduction and imbalanced spectral clustering

Abstract

The Gaussian Mixture Model (abbrv. GMM) is a classic generative model for clustered data, for which spectral clustering based on dimension reduction via PCA has been an effective framework. In this work, we investigate kernelised covariance matrices as an alternative mechanism for dimension reduction and spectral clustering, focusing on truncation kernels that select pairs of data points with suitable separation constraints. The structure of these matrices is motivated by considerations from statistical mechanics of repulsive particle systems. Our approach is particularly relevant for the setting of imbalanced clusters, where the sizes of the largest and smallest clusters have a diverging ratio with the problem size, and existing PCA-based methods turn out to be of limited effectiveness. We demonstrate efficient dimension reduction and clustering performance of these modified covariance matrices, substantiated by quantitative bounds. In particular, they achieve superior dimension reduction guarantees compared to PCA for a wide range of parameters in the regime of imbalanced clusters. For spectral clustering, our approach exhibits improvements over PCA in the imbalanced setting, in particular guaranteeing accurate clustering in a much larger regime of intra-cluster separations. Our theoretical guarantees reflected in a range of simulation experiments that exhibit these improvements for unbalanced clustering problems. Our analytical approach, based on kernel Laplacians, provide a toolbox as well as a relevant conceptual ingredient for clustering problems at large. We believe that our work will motivate the application of such kernelised covariance matrices for related classes of statistical problems, as well as spur new investigations in the theory of random matrices.

The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.

More in Machine Learning (Statistics)

• arXiv preprint · 27 October 2026

  Threshold Criteria for Bosonic and Fermionic Trimers on a Square Lattice: A Birman--Schwinger Comparison

  Janikul Abdullaev, Abdumalik Eshniyozov and Mikhail Dolgopolov
• arXiv preprint · 22 October 2026

  A sharp gradient-corrected Lieb--Thirring inequality in one dimension with applications to density functional theory

  Thiago Carvalho Corso and Louis Garrigue
• arXiv preprint · 27 October 2026

  Every route counts, but some count more: a max-plus view of the C. elegans brain

  Emma Reyner-Fuentes, Sebastian Rudolph, Carmen Peláez-Moreno and 1 other
• arXiv preprint · 20 October 2026

  Lieb-Robinson bounds via the Combes-Thomas estimate

  Tali Braester, Haochen Luo, George Peykanu and 1 other
• arXiv preprint · 30 October 2026

  Persistence of Unitary Almost Mathieu Operator Gaps Ten Dry Martinis, Five on the Rim

  Dan S. Borgnia, Matthew Faust and Long Li

All new papers in Machine Learning (Statistics)