# Nystr"om Kernel Mean Embeddings

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

## Key facts

- Cited by 22 papers in the map (data through 14 Oct 2026).
- Builds on 15 of its 47 references that are in the map.
- First posted on arXiv 31 Jan 2022.

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

- [Enriching Word Vectors with Subword Information](https://mlsanity.com/paper/1607.04606/) (2016)
- [Kernel Mean Embedding of Distributions: A Review and Beyond](https://mlsanity.com/paper/1605.09522/) (2016)
- [MMD GAN: Towards Deeper Understanding of Moment Matching Network](https://mlsanity.com/paper/1705.08584/) (2017)
- [FMA: A Dataset For Music Analysis](https://mlsanity.com/paper/1612.01840/) (2016)
- [On the Equivalence between Kernel Quadrature Rules and Random Feature Expansions](https://mlsanity.com/paper/1502.06800/) (2015)
- [Generative Models and Model Criticism via Optimized Maximum Mean Discrepancy](https://mlsanity.com/paper/1611.04488/) (2016)
- [Less is More: Nystr"om Computational Regularization](https://mlsanity.com/paper/1507.04717/) (2015)
- [Interpretable Distribution Features with Maximum Testing Power](https://mlsanity.com/paper/1605.06796/) (2016)
- [Kernel quadrature with DPPs](https://mlsanity.com/paper/1906.07832/) (2019)
- [Differentially Private Database Release via Kernel Mean Embeddings](https://mlsanity.com/paper/1710.01641/) (2017)
- [Kernel Mean Estimation and Stein's Effect](https://mlsanity.com/paper/1306.0842/) (2013)
- [Compressive K-means](https://mlsanity.com/paper/1610.08738/) (2016)
- [MONK -- Outlier-Robust Mean Embedding Estimation by Median-of-Means](https://mlsanity.com/paper/1802.04784/) (2018)
- [On Sampling Random Features From Empirical Leverage Scores: Implementation and Theoretical Guarantees](https://mlsanity.com/paper/1903.08329/) (2019)
- [Nonparametric Detection of Anomalous Data Streams](https://mlsanity.com/paper/1405.2294/) (2014)

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

- [Sampling-based Nystr"om Approximation and Kernel Quadrature](https://mlsanity.com/paper/2301.09517/) (2023)
- [Estimating Koopman operators with sketching to provably learn large scale dynamical systems](https://mlsanity.com/paper/2306.04520/) (2023)
- [Representation Distribution Matching for One-Step Visual Generation](https://mlsanity.com/paper/2607.02375/) (2026)
- [Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via Leverage Scores Sampling](https://mlsanity.com/paper/2311.13548/) (2023)
- [Near-Minimax-Optimal Distributional Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2402.07598/) (2024)
- [Nonparametric Control Koopman Operators](https://mlsanity.com/paper/2405.07312/) (2024)
- [On the Robustness of Kernel Goodness-of-Fit Tests](https://mlsanity.com/paper/2408.05854/) (2024)
- [Efficient Robust Bayesian Optimization for Arbitrary Uncertain Inputs](https://mlsanity.com/paper/2310.20145/) (2023)
- [A Scalable Nystrom-Based Kernel Two-Sample Test with Permutations](https://mlsanity.com/paper/2502.13570/) (2025)
- [Nystr"om M-Hilbert-Schmidt Independence Criterion](https://mlsanity.com/paper/2302.09930/) (2023)
- [Sketch In, Sketch Out: Accelerating both Learning and Inference for Structured Prediction with Kernels](https://mlsanity.com/paper/2302.10128/) (2023)
- [Nystr"om Kernel Stein Discrepancy](https://mlsanity.com/paper/2406.08401/) (2024)
- [Huber-energy measure quantization](https://mlsanity.com/paper/2212.08162/) (2022)
- [Non-parametric Hypothesis Tests for Distributional Group Symmetry](https://mlsanity.com/paper/2307.15834/) (2023)
- [Minimax Lower Bounds of Kernel Discrepancy Estimation: MMD, HSIC, KSD](https://mlsanity.com/paper/2607.24235/) (2026)
- [Deep Conditional Measure Quantization](https://mlsanity.com/paper/2301.06907/) (2023)
- [Boosting Nystr"om Method](https://mlsanity.com/paper/2302.11032/) (2023)
- [Kernel Quantile Embeddings and Associated Probability Metrics](https://mlsanity.com/paper/2505.20433/) (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)
- [From Scores to Samples: Elastic Forcing for Autoregressive Video Generation](https://mlsanity.com/paper/2609.35491/) (2026)
- [Kernelized Parameter Sensitivity Atlases for Amortized Conditional Interpretability](https://mlsanity.com/paper/2610.12737/) (2026)

## Abstract (arXiv)

Kernel mean embeddings are a powerful tool to represent probability distributions over arbitrary spaces as single points in a Hilbert space. Yet, the cost of computing and storing such embeddings prohibits their direct use in large-scale settings. We propose an efficient approximation procedure based on the Nystr"om method, which exploits a small random subset of the dataset. Our main result is an upper bound on the approximation error of this procedure. It yields sufficient conditions on the subsample size to obtain the standard n-1/2 rate while reducing computational costs. We discuss applications of this result for the approximation of the maximum mean discrepancy and quadrature rules, and illustrate our theoretical findings with numerical experiments.