# A Randomized Approach to Efficient Kernel Clustering

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Aug 2016.

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

- [Two-Stage Surrogate Modeling for Data-Driven Design Optimization with Application to Composite Microstructure Generation](https://mlsanity.com/paper/2401.02008/) (2024)

## Abstract (arXiv)

Kernel-based K-means clustering has gained popularity due to its simplicity and the power of its implicit non-linear representation of the data. A dominant concern is the memory requirement since memory scales as the square of the number of data points. We provide a new analysis of a class of approximate kernel methods that have more modest memory requirements, and propose a specific one-pass randomized kernel approximation followed by standard K-means on the transformed data. The analysis and experiments suggest the method is accurate, while requiring drastically less memory than standard kernel K-means and significantly less memory than Nystrom based approximations.