# Randomized Clustered Nystrom for Large-Scale Kernel Machines

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Dec 2016.

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

- [Scalable kernel balancing weights in a nationwide observational study of hospital profit status and heart attack outcomes](https://mlsanity.com/paper/2311.00568/) (2023)
- [Low-Rank Compression of Pretrained Models via Randomized Subspace Iteration](https://mlsanity.com/paper/2604.02659/) (2026)

## Abstract (arXiv)

The Nystrom method has been popular for generating the low-rank approximation of kernel matrices that arise in many machine learning problems. The approximation quality of the Nystrom method depends crucially on the number of selected landmark points and the selection procedure. In this paper, we present a novel algorithm to compute the optimal Nystrom low-approximation when the number of landmark points exceed the target rank. Moreover, we introduce a randomized algorithm for generating landmark points that is scalable to large-scale data sets. The proposed method performs K-means clustering on low-dimensional random projections of a data set and, thus, leads to significant savings for high-dimensional data sets. Our theoretical results characterize the tradeoffs between the accuracy and efficiency of our proposed method. Extensive experiments demonstrate the competitive performance as well as the efficiency of our proposed method.