mlsanityData to 14 Oct 2026

Sampling-based Nystr"om Approximation and Kernel Quadrature

arXiv 2301.09517 ↗First posted 23 Jan 2023math.NA cs.LG cs.NAcited by 17

Not on the map. Why?

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.

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

17 of 54 references.

References · 17

  1. 2017Nonparametric regression using deep neural networks with ReLU activation functioncited by 433
  2. 2015On the Equivalence between Kernel Quadrature Rules and Random Feature Expansionscited by 138
  3. 2013Revisiting the Nystrom Method for Improved Large-Scale Machine Learningcited by 77
  4. 2021Kernel Thinningcited by 47
  5. 2021Generalized Kernel Thinningcited by 29
  6. 2019Kernel quadrature with DPPscited by 27
  7. 2021Positively Weighted Kernel Quadrature via Subsamplingcited by 25
  8. 2019On the minimax optimality and superiority of deep neural network learning over sparse parameter spacescited by 24
  9. 2017Fixed-Rank Approximation of a Positive-Semidefinite Matrix from Streaming Datacited by 23
  10. 2022Nystr"om Kernel Mean Embeddingscited by 22
  11. 2020Kernel interpolation with continuous volume samplingcited by 21
  12. 2022Fast Bayesian Inference with Batch Bayesian Quadrature via Kernel Recombinationcited by 20
5 more
  1. 2021Distribution Compression in Near-linear Timecited by 19
  2. 2017Scalable Kernel K-Means Clustering with Nystrom Approximation: Relative-Error Boundscited by 16
  3. 2016Fast DPP Sampling for Nystr"om with Application to Kernel Methodscited by 15
  4. 2016Convergence guarantees for kernel-based quadrature rules in misspecified settingscited by 15
  5. 2020A Randomized Algorithm to Reduce the Support of Discrete Measurescited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 7; 2024: 2; 2025: 4; 2026: 4.

17 papers.

Sort:

  1. 2025Weighted quantization using MMD: From mean field to mean shift via gradient flowscited by 12
  2. 2023Kernel quadrature with randomly pivoted Choleskycited by 11
  3. 2023Efficient Numerical Integration in Reproducing Kernel Hilbert Spaces via Leverage Scores Samplingcited by 10
  4. 2024Conditional Bayesian Quadraturecited by 9
  5. 2023SOBER: Highly Parallel Bayesian Optimization and Bayesian Quadrature over Discrete and Mixed Spacescited by 7
  6. 2023Adaptive Batch Sizes for Active Learning A Probabilistic Numerics Approachcited by 6
  7. 2025Nested Expectations with Kernel Quadraturecited by 5
  8. 2023When can Regression-Adjusted Control Variates Help? Rare Events, Sobolev Embedding and Minimax Optimalitycited by 4
  9. 2023Stochastic Nonlinear Control via Finite-dimensional Spectral Dynamic Embeddingcited by 3
  10. 2024A Quadrature Approach for General-Purpose Batch Bayesian Optimization via Probabilistic Liftingcited by 3
  11. 2026To discretize continually: Mean shift interacting particle systems for Bayesian inferencecited by 2
  12. 2023Policy Gradient with Kernel Quadraturecited by 1
5 more
  1. 2026Bayesian Quadraturecited by 1
  2. 2025Gradient-based Sample Selection for Faster Bayesian Optimizationcited by 0
  3. 2025BayesSum: Bayesian Quadrature in Discrete Spacescited by 0
  4. 2026Fast and Provably Accurate Sequential Designs using Hilbert Space Gaussian Processescited by 0
  5. 2026Convex-Geometric Error Bounds for Positive-Weight Kernel Quadraturecited by 0