Research map / Learning theory and algorithms / Clustering
Nyström Method with Kernel K-means++ Samples as Landmarks
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (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 changed | Where | Measured | Effect |
|---|---|---|---|
| Use kernel K-means++ samples as landmarks instead of uniform, leverage score or K-DPP sampling | Nystrom low-rank approximation of Gaussian kernel matrix · 13 UCI/LIACC datasets, K=100, varying bandwidth | lift of Frobenius norm error | Helped |
| Increase K-DPP chain length from 1 000 to 10 000 MC steps with uniform initial state (ablation) | K-DPP Nystrom method · ailerons, parkinsons, elevators, ujil, cal-housing | lift of Frobenius norm error: 1 000 -> 10 000 MC steps | Helped |
| Run K-DPP chain beyond 1 000 steps from a uniformly random initial state (ablation) | K-DPP Nystrom method · five datasets, K=100 | runtime vs accuracy | Mixed |
| Initialize K-DPP chain with K-means++ samples instead of uniform sampling (ablation) | K-DPP Nystrom method · Comparison with Li et al. (2016) | runtime and accuracy | Helped |
| Increase approximation rank from 5 to 100 (ablation) | kernel K-means++ sampling · five datasets, median-distance bandwidth | lift of Frobenius norm error: 5 -> 100 | Helped |
| Use approximate leverage score sampling instead of K-DPP initialized uniformly | landmark selection baselines · five datasets, rank sweep | lift of Frobenius norm error | Helped |
| Select l = K ln n landmarks instead of l = K ln K for a rank K=100 approximation (ablation) | kernel K-means++ sampling · Appendix C, K=100 | lift of Frobenius norm error | No clear effect |
| Select l = K ln K landmarks instead of l = K for a rank K approximation (ablation) | kernel K-means++ sampling · K=100 | approximation accuracy and selection time | Helped |
| Use kernel K-means++ sampling instead of approximate leverage score sampling on high-dimensional data | landmark selection · ujil (more than 500 attributes) | selection time | Hurt |
| Use leverage score sampling instead of kernel K-means++ on cal-housing | landmark selection · cal-housing | lift of Frobenius norm error | Hurt |
Closest papers by meaning
- Randomized Clustered Nystrom for Large-Scale Kernel Machines (AAAI 2018 · similarity 0.91)
- Recursive Sampling for the Nystrom Method (NeurIPS 2017 · similarity 0.88)
- Incremental Nyström-based Multiple Kernel Clustering (AAAI 2025 · similarity 0.87)
- Entrywise error bounds for low-rank approximations of kernel matrices (NeurIPS 2024 · similarity 0.85)
- Learning in Feature Spaces via Coupled Covariances: Asymmetric Kernel SVD and Nyström method (ICML 2024 · similarity 0.84)
- Scalable Multiple Kernel Clustering: Learning Clustering Structure from Expectation (ICML 2024 · similarity 0.84)
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.