Kernelised covariance matrices, dimension reduction and imbalanced spectral clustering

Xiaoyu Dong; Subhro Ghosh; Soumendu Sundar Mukherjee; Himasish Talukdar

stat.MLOct 23, 2026

Kernelised covariance matrices, dimension reduction and imbalanced spectral clustering

Authors: Xiaoyu Dong, Subhro Ghosh, Soumendu Sundar Mukherjee, Himasish Talukdar

Organizations: National University of Singapore, Singapore · Indian Statistical Institute, Kolkata, India

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.

Figures & tables

$m$	$1:1:1:1$	$3:3:1:1$	$4:2:1:1$	$26:4:1:1$
512	$(128,128,128,128)$	$(192,192,64,64)$	$(256,128,64,64)$	$(416,64,16,16)$
128	$(32,32,32,32)$	$(48,48,16,16)$	$(64,32,16,16)$	$(104,16,4,4)$
64	$(16,16,16,16)$	$(24,24,8,8)$	$(32,16,8,8)$	$(52,8,2,2)$

Table 1. Minority cluster sizes for

k=5

. The remaining cluster has size

4096-m

. Each column is a separate separation experiment at each value of

m

Figure 1. Two-cluster separation and clustering experiments, with sizes

(4096-m,m)

and

m=2048,512,128,32

from left to right. Here and in the subsequent figures, we use the following convention:

n=4096

p=128

, and

\sigma=1

; the horizontal axis is

\Delta/\sigma

on a logarithmic scale; the top row shows average error and the bottom row shows worst-cluster error; markers show means over eight independent noise replicates, and shaded regions are the descriptive confidence intervals specified in the text.

Figure 2. Five-cluster separation and clustering experiments with total minority size

m=512

and largest-cluster size

3584

. Columns use minority ratios

1:1:1:1

3:3:1:1

4:2:1:1

, and

26:4:1:1

; exact sizes are in Table 1 .

Figure 3. Five-cluster separation and clustering experiments with total minority size

m=128

and largest-cluster size

3968

. Columns use the same four minority ratios as Figure 2 , giving smallest-cluster sizes

32,16,16,4

Figure 4. Five-cluster separation and clustering experiments with total minority size

m=64

and largest-cluster size

4032

. Columns use the same four minority ratios as Figure 2 , giving smallest-cluster sizes

16,8,8,2

Clustering

Clustering groups data points by shared structure, developing methods to discover, validate, and interpret groups across diverse data and constraints.

See all 347 papers

Aug 9, 2026

Multi-kernel spectral clustering: Entrywise eigenvector perturbation bounds and exact recovery

Kernel spectral clustering with a single bandwidth can be inadequate for data exhibiting multiple characteristic pairwise-distance scales, a problem particularly prevalent in the high-dimensional regime. We address this issue through a multi-kernel formulation that aggregates kernels with different bandwidths. The bandwidths are selected as prescribed empirical quantiles of the pairwise squared distances, thereby capturing the relevant distance scales without requiring prior population-scale information. We develop a rigorous theoretical analysis of the resulting method under a general high-dimensional, multi-scale mixture model with heterogeneous cluster centers and covariance geometries. We construct a blockwise constant, low-rank informative approximation to the empirical multi-kernel matrix and establish row-wise

\ell_{2,\infty}

perturbation bounds for its leading spectral components, as well as for the associated normalized Laplacian matrix. These bounds yield observation-level control of the spectral embedding, which is more informative than conventional global eigenspace perturbation estimates. Under suitable eigen-gap and cluster-separation conditions, we show that approximate

K

-means applied to the multi-kernel spectral embedding achieves exact recovery with high probability.

Zeqin Lin, Guangming Pan, Zhixiang Zhang +1

1Nanyang Technological University · University of Macau · 3Dalian University of Technology

Clustering Unsupervised Clustering Spectral Clustering Kernel Methods Spectral Methods

Ask PDF

Sep 28, 2026

GEM-KMeans: Memory-Efficient and Accurate Clustering on Massive Scale with GPU Optimization

Memory-efficient scaling on clustering problems without sacrificing statistical accuracy is of central interest for large-scale data analysis and machine learning problems. Nonnegative low-rank (NLR) matrix factorization for

K

-means is a scalable clustering method, which connects to semidefinite relaxations with optimal average-case exact recovery guarantees. However, a direct GPU implementation of NLR requires multiple large factor-sized buffers and substantial data movements that are essentially memory-bound. In this paper, we introduce GEM-KMeans, a spectrally normalized yet mathematically equivalent NLR formulation that fuses the gradient update, nonnegative projection, and sufficient statistics for normalization and iterate movement into a matrix-multiplication epilogue. Instead of retaining three massive factor-sized arrays, our IO-aware GPU implementation materializes only one single factor with small tile-reduction arrays as additional storage in the High Bandwidth Memory (HBM). We derive explicit memory costs and spectrally normalized smoothness bounds for optimizing the clustering objective function. Accurate clustering is demonstrated at massive scales on synthetic and real datasets, where performance gains of GEM-KMeans over existing GPU-accelerated Lloyd's algorithms involve data-dependent runtime tradeoffs.

Peng Xu, Nihar Koganti, Volodymyr Kindratenko +1

Department of Statistics, University of Illinois Urbana-Champaign · Department of Electrical and Computer Engineering, University of Illinois Urbana-Champaign · National Center for Supercomputing Applications, University of Illinois Urbana-Champaign +3

Clustering Non-Negative Matrix Factorization Low-Rank Matrix Decomposition GPU Kernel Optimization

Ask PDF

Aug 29, 2026

Clustering as Approximation by Constrained Projectors: Theory and Guarantees

This paper develops a unified theoretical framework showing that a broad family of clustering methods, including k-means, fuzzy c-means, kernel k-means, kernel FCM, and spectral clustering, can all be expressed as structured low-rank projectors acting on a signal-derived matrix. By formulating each method as an instance of min over B in C of ||M - M P_B||_F^2, with different constraint sets C, we establish a common optimization template that clarifies the algebraic links among hard, fuzzy, kernel-induced, and orthonormal projections. Within this framework, we derive non-trivial theoretical results, including geodesic convexity properties on the projection manifold, perturbation bounds quantifying stability to matrix noise, and exact recovery guarantees under ideal block-model conditions. The analysis further explains when different clustering families collapse to the same optimal subspace and how deviations arise under small inter-cluster leakage. Overall, the work provides a coherent, theory-first foundation for understanding clustering through structured projectors.

Angshul Majumdar

Indraprastha Institute of Information Technology Delhi New Delhi 110020, India

Clustering Spectral Clustering

Ask PDF

Abstract

Clustering

Explore similar work

Multi-kernel spectral clustering: Entrywise eigenvector perturbation bounds and exact recovery

GEM-KMeans: Memory-Efficient and Accurate Clustering on Massive Scale with GPU Optimization

Clustering as Approximation by Constrained Projectors: Theory and Guarantees