# Fast DPP Sampling for Nystr"om with Application to Kernel Methods

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

## Key facts

- Cited by 15 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 19 Mar 2016.

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

- [Diversified Sampling for Batched Bayesian Optimization with Determinantal Point Processes](https://mlsanity.com/paper/2110.11665/) (2021)
- [Connections and Equivalences between the Nystr"om Method and Sparse Variational Gaussian Processes](https://mlsanity.com/paper/2106.01121/) (2021)
- [Sampling-based Nystr"om Approximation and Kernel Quadrature](https://mlsanity.com/paper/2301.09517/) (2023)
- [DNS: Determinantal Point Process Based Neural Network Sampler for Ensemble Reinforcement Learning](https://mlsanity.com/paper/2201.13357/) (2022)
- [Random Gegenbauer Features for Scalable Kernel Methods](https://mlsanity.com/paper/2202.03474/) (2022)
- [From Sampling to Optimization on Discrete Domains with Applications to Determinant Maximization](https://mlsanity.com/paper/2102.05347/) (2021)
- [Hardness of Maximum Likelihood Learning of DPPs](https://mlsanity.com/paper/2205.12377/) (2022)
- [Scalable MCMC Sampling for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2207.00486/) (2022)
- [Variational Gaussian Processes: A Functional Analysis View](https://mlsanity.com/paper/2110.12798/) (2021)
- [Scalable Sampling for Nonsymmetric Determinantal Point Processes](https://mlsanity.com/paper/2201.08417/) (2022)
- [Reconstructing Kernel-based Machine Learning Force Fields with Super-linear Convergence](https://mlsanity.com/paper/2212.12737/) (2022)
- [Towards Deterministic Diverse Subset Sampling](https://mlsanity.com/paper/2105.13942/) (2021)
- [Computational Complexity of Normalizing Constants for the Product of Determinantal Point Processes](https://mlsanity.com/paper/2111.14148/) (2021)
- [Boosting Nystr"om Method](https://mlsanity.com/paper/2302.11032/) (2023)
- [Triply-Scalable Equivariant Gaussian Process Modeling](https://mlsanity.com/paper/2609.21085/) (2026)

## Abstract (arXiv)

The Nystr"om method has long been popular for scaling up kernel methods. Its theoretical guarantees and empirical performance rely critically on the quality of the landmarks selected. We study landmark selection for Nystr"om using Determinantal Point Processes (DPPs), discrete probability models that allow tractable generation of diverse samples. We prove that landmarks selected via DPPs guarantee bounds on approximation errors; subsequently, we analyze implications for kernel ridge regression. Contrary to prior reservations due to cubic complexity of DPPsampling, we show that (under certain conditions) Markov chain DPP sampling requires only linear time in the size of the data. We present several empirical results that support our theoretical analysis, and demonstrate the superior performance of DPP-based landmark selection compared with existing approaches.