# Nystr"om landmark sampling and regularized Christoffel functions

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 May 2019.

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

- [Nystr"omformer: A Nystr"om-Based Algorithm for Approximating Self-Attention](https://mlsanity.com/paper/2102.03902/) (2021)
- [Chameleon: A Flexible Data-mixing Framework for Language Model Pretraining and Finetuning](https://mlsanity.com/paper/2505.24844/) (2025)
- [CS4ML: A general framework for active learning with arbitrary data based on Christoffel functions](https://mlsanity.com/paper/2306.00945/) (2023)
- [Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via Leverage Scores Sampling](https://mlsanity.com/paper/2311.13548/) (2023)
- [Optimal sampling for least-squares approximation](https://mlsanity.com/paper/2409.02342/) (2024)
- [A Scalable Nystrom-Based Kernel Two-Sample Test with Permutations](https://mlsanity.com/paper/2502.13570/) (2025)
- [Optimal Learning Rates for Regularized Least-Squares with a Fourier Capacity Condition](https://mlsanity.com/paper/2204.07856/) (2022)
- [Beyond Nystr"omformer -- Approximation of self-attention by Spectral Shifting](https://mlsanity.com/paper/2103.05638/) (2021)

## Abstract (arXiv)

Selecting diverse and important items, called landmarks, from a large set is a problem of interest in machine learning. As a specific example, in order to deal with large training sets, kernel methods often rely on low rank matrix Nystr"om approximations based on the selection or sampling of landmarks. In this context, we propose a deterministic and a randomized adaptive algorithm for selecting landmark points within a training data set. These landmarks are related to the minima of a sequence of kernelized Christoffel functions. Beyond the known connection between Christoffel functions and leverage scores, a connection of our method with finite determinantal point processes (DPPs) is also explained. Namely, our construction promotes diversity among important landmark points in a way similar to DPPs. Also, we explain how our randomized adaptive algorithm can influence the accuracy of Kernel Ridge Regression.