# Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds

arXiv: https://arxiv.org/abs/1706.02803 · HTML: https://mlsanity.com/paper/1706.02803/

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 9 Jun 2017.

## Built on by (most cited first, 16 of 16)

- [PINNACLE: PINN Adaptive ColLocation and Experimental points selection](https://mlsanity.com/paper/2404.07662/) (2024)
- [Sampling-based Nystr"om Approximation and Kernel Quadrature](https://mlsanity.com/paper/2301.09517/) (2023)
- [An algorithm for clustering with confidence-based must-link and cannot-link constraints](https://mlsanity.com/paper/2212.14437/) (2022)
- [FedPower: Privacy-Preserving Distributed Eigenspace Estimation](https://mlsanity.com/paper/2103.00704/) (2021)
- [On Generalization Bounds for Projective Clustering](https://mlsanity.com/paper/2310.09127/) (2023)
- [Neuronal Correlation: a Central Concept in Neural Network](https://mlsanity.com/paper/2201.09069/) (2022)
- [Constrained Clustering and Multiple Kernel Learning without Pairwise Constraint Relaxation](https://mlsanity.com/paper/2203.12546/) (2022)
- [On The Relative Error of Random Fourier Features for Preserving Kernel Distance](https://mlsanity.com/paper/2210.00244/) (2022)
- [Scalable Kernel Logistic Regression with Nystr"om Approximation: Theoretical Analysis and Application to Discrete Choice Modelling](https://mlsanity.com/paper/2402.06763/) (2024)
- [Scalable kernel balancing weights in a nationwide observational study of hospital profit status and heart attack outcomes](https://mlsanity.com/paper/2311.00568/) (2023)
- [Scalable Density-based Clustering with Random Projections](https://mlsanity.com/paper/2402.15679/) (2024)
- [Distributed Clustering based on Distributional Kernel](https://mlsanity.com/paper/2409.09418/) (2024)
- [Coreset Spectral Clustering](https://mlsanity.com/paper/2503.07227/) (2025)
- [Scalable Varied-Density Clustering via Graph Propagation](https://mlsanity.com/paper/2508.02989/) (2025)
- [Communication-Avoiding Linear Algebraic Kernel K-Means on GPUs](https://mlsanity.com/paper/2601.17136/) (2026)
- [Towards Robust and Scalable Density-based Clustering via Graph Propagation](https://mlsanity.com/paper/2605.00390/) (2026)

## Abstract (arXiv)

Kernel k-means clustering can correctly identify and extract a far more varied collection of cluster structures than the linear k-means clustering algorithm. However, kernel k-means clustering is computationally expensive when the non-linear feature map is high-dimensional and there are many input points. Kernel approximation, e.g., the Nystr"om method, has been applied in previous works to approximately solve kernel learning problems when both of the above conditions are present. This work analyzes the application of this paradigm to kernel k-means clustering, and shows that applying the linear k-means clustering algorithm to frackε (1 + o(1)) features constructed using a so-called rank-restricted Nystr"om approximation results in cluster assignments that satisfy a 1 + ε approximation ratio in terms of the kernel k-means cost function, relative to the guarantee provided by the same algorithm without the use of the Nystr"om method. As part of the analysis, this work establishes a novel 1 + ε relative-error trace norm guarantee for low-rank approximation using the rank-restricted Nystr"om approximation. Empirical evaluations on the 8.1 million instance MNIST8M dataset demonstrate the scalability and usefulness of kernel k-means clustering with Nystr"om approximation. This work argues that spectral clustering using Nystr"om approximation---a popular and computationally efficient, but theoretically unsound approach to non-linear clustering---should be replaced with the efficient and theoretically sound combination of kernel k-means clustering with Nystr"om approximation. The superior performance of the latter approach is empirically verified.