# Sampling-based Nystr"om Approximation and Kernel Quadrature

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

## Key facts

- Cited by 17 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 54 references that are in the map.
- First posted on arXiv 23 Jan 2023.

## Builds on (most cited first, 17 of 17)

- [Nonparametric regression using deep neural networks with ReLU activation function](https://mlsanity.com/paper/1708.06633/) (2017)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Revisiting the Nystrom Method for Improved Large-Scale Machine Learning](https://mlsanity.com/paper/1303.1849/) (2013)
- [Kernel Thinning](https://mlsanity.com/paper/2105.05842/) (2021)
- [Generalized Kernel Thinning](https://mlsanity.com/paper/2110.01593/) (2021)
- [Kernel quadrature with DPPs](https://mlsanity.com/paper/1906.07832/) (2019)
- [Positively Weighted Kernel Quadrature via Subsampling](https://mlsanity.com/paper/2107.09597/) (2021)
- [On the minimax optimality and superiority of deep neural network learning over sparse parameter spaces](https://mlsanity.com/paper/1905.09195/) (2019)
- [Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Data](https://mlsanity.com/paper/1706.05736/) (2017)
- [Nystr"om Kernel Mean Embeddings](https://mlsanity.com/paper/2201.13055/) (2022)
- [Kernel interpolation with continuous volume sampling](https://mlsanity.com/paper/2002.09677/) (2020)
- [Fast Bayesian Inference with Batch Bayesian Quadrature via Kernel Recombination](https://mlsanity.com/paper/2206.04734/) (2022)
- [Distribution Compression in Near-linear Time](https://mlsanity.com/paper/2111.07941/) (2021)
- [Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Bounds](https://mlsanity.com/paper/1706.02803/) (2017)
- [Fast DPP Sampling for Nystr"om with Application to Kernel Methods](https://mlsanity.com/paper/1603.06052/) (2016)
- [Convergence guarantees for kernel-based quadrature rules in misspecified settings](https://mlsanity.com/paper/1605.07254/) (2016)
- [A Randomized Algorithm to Reduce the Support of Discrete Measures](https://mlsanity.com/paper/2006.01757/) (2020)

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

- [Weighted quantization using MMD: From mean field to mean shift via gradient flows](https://mlsanity.com/paper/2502.10600/) (2025)
- [Kernel quadrature with randomly pivoted Cholesky](https://mlsanity.com/paper/2306.03955/) (2023)
- [Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via Leverage Scores Sampling](https://mlsanity.com/paper/2311.13548/) (2023)
- [Conditional Bayesian Quadrature](https://mlsanity.com/paper/2406.16530/) (2024)
- [SOBER: Highly Parallel Bayesian Optimization and Bayesian Quadrature over Discrete and Mixed Spaces](https://mlsanity.com/paper/2301.11832/) (2023)
- [Adaptive Batch Sizes for Active Learning A Probabilistic Numerics Approach](https://mlsanity.com/paper/2306.05843/) (2023)
- [Nested Expectations with Kernel Quadrature](https://mlsanity.com/paper/2502.18284/) (2025)
- [When can Regression-Adjusted Control Variates Help? Rare Events, Sobolev Embedding and Minimax Optimality](https://mlsanity.com/paper/2305.16527/) (2023)
- [Stochastic Nonlinear Control via Finite-dimensional Spectral Dynamic Embedding](https://mlsanity.com/paper/2304.03907/) (2023)
- [A Quadrature Approach for General-Purpose Batch Bayesian Optimization via Probabilistic Lifting](https://mlsanity.com/paper/2404.12219/) (2024)
- [To discretize continually: Mean shift interacting particle systems for Bayesian inference](https://mlsanity.com/paper/2605.14142/) (2026)
- [Policy Gradient with Kernel Quadrature](https://mlsanity.com/paper/2310.14768/) (2023)
- [Bayesian Quadrature](https://mlsanity.com/paper/2602.16218/) (2026)
- [Gradient-based Sample Selection for Faster Bayesian Optimization](https://mlsanity.com/paper/2504.07742/) (2025)
- [BayesSum: Bayesian Quadrature in Discrete Spaces](https://mlsanity.com/paper/2512.16105/) (2025)
- [Fast and Provably Accurate Sequential Designs using Hilbert Space Gaussian Processes](https://mlsanity.com/paper/2604.20414/) (2026)
- [Convex-Geometric Error Bounds for Positive-Weight Kernel Quadrature](https://mlsanity.com/paper/2605.05705/) (2026)

## Abstract (arXiv)

We analyze the Nystr"om approximation of a positive definite kernel associated with a probability measure. We first prove an improved error bound for the conventional Nystr"om approximation with i.i.d. sampling and singular-value decomposition in the continuous regime; the proof techniques are borrowed from statistical learning theory. We further introduce a refined selection of subspaces in Nystr"om approximation with theoretical guarantees that is applicable to non-i.i.d. landmark points. Finally, we discuss their application to convex kernel quadrature and give novel theoretical guarantees as well as numerical observations.