# Spectral Clustering using Eigenspectrum Shape Based Nystrom Sampling

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 21 Jul 2020.

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

- [Etat de l'art sur l'application des bandits multi-bras](https://mlsanity.com/paper/2101.00001/) (2021)

## Abstract (arXiv)

Spectral clustering has shown a superior performance in analyzing the cluster structure. However, its computational complexity limits its application in analyzing large-scale data. To address this problem, many low-rank matrix approximating algorithms are proposed, including the Nystrom method - an approach with proven approximate error bounds. There are several algorithms that provide recipes to construct Nystrom approximations with variable accuracies and computing times. This paper proposes a scalable Nystrom-based clustering algorithm with a new sampling procedure, Centroid Minimum Sum of Squared Similarities (CMS3), and a heuristic on when to use it. Our heuristic depends on the eigen spectrum shape of the dataset, and yields competitive low-rank approximations in test datasets compared to the other state-of-the-art methods