AI Paper Atlas

Research map / Learning theory and algorithms / Clustering

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

Shusen Wang, Alex Gittens, Michael W. Mahoney

JMLR 2019 · Learning theory and algorithms › Clustering · approach: Subspace clustering · 84 citations (OpenAlex)

Read the paperCheck your idea against 137,217 papers

AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Measured effects reported in the paper

What was changedWhereMeasuredEffect
increase sketch size c from 100 to 1600 (ablation)Nystrom kernel k-means · MNIST8M (s=20)NMI: 0.3833 -> 0.4069Improved
increase sketch size c from 400 to 1600 (ablation)Nystrom kernel k-means · MNIST8M (s=80)NMI: 0.4101 -> 0.4233Improved
increase sketch size c from 100 to 1600 (ablation)Nystrom kernel k-means · MNIST8M (s=20)total runtime (s): 227.4 -> 2785.4Hurt
increase target dimension s from 10 to 80 (ablation)Nystrom kernel k-means · MNIST8M (c=1600)NMI: 0.3852 -> 0.4233Improved
increase target dimension s from 80 to 160 (ablation)Nystrom kernel k-means · MNIST8M (c=1600)NMI: 0.4233 -> 0.4086Hurt
increase target dimension s from 10 to 320 (ablation)Nystrom kernel k-means · MNIST8M (c=1600)total runtime (s): 2840.9 -> 3537.5Hurt
increase compute nodes from 8 to 32 (ablation)Nystrom kernel k-means · MNIST8M (c=400, s=20)total runtime (s): 3201.5 -> 867.9Improved
increase compute nodes from 32 to 128 (ablation)Nystrom kernel k-means · MNIST8M (c=400, s=20)total runtime (s): 867.9 -> 828.2No clear effect
increase compute nodes from 32 to 128 (ablation)Nystrom kernel k-means · MNIST8M (c=400, s=80)total runtime (s): 940.6 -> 1232.4Hurt
use Nystrom instead of random feature mapsapproximate kernel k-means · medium-scale datasets (MNIST, Mushrooms, PenDigits)NMI and objectiveImproved
use Nystrom or RFM instead of the two-step methodapproximate kernel k-means · medium-scale datasetsNMI and objectiveImproved
vary target rank s (k, sqrt(ck), c) (ablation)Nystrom kernel k-means · medium-scale datasetsNMI and objectiveNo clear effect

Closest papers by meaning

Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.

Open scime draft

Get the next scime Dispatch and a monthly field update

Free. We send a confirmation link first; every email has a one-click unsubscribe. Privacy