Sampling-based Nyström Approximation and Kernel Quadrature

Satoshi Hayakawa, Harald Oberhauser, Terry Lyons
1/23/2023
math.NAcs.LGstat.ML

No official code found. Best implementation: satoshi-hayakawa/kernel-quadrature (5 stars, last commit 2023-05-16).

Abstract

We analyze the Nyström approximation of a positive definite kernel associated with a probability measure. We first prove an improved error bound for the conventional Nyström 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öm 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.

View on arXivView PDF

Code Implementations(1)

satoshi-hayakawa/kernel-quadratureCommunity100%
50PythonOct 5, 20213 years agoNOASSERTION

Similar Papers

Nyström Kernel Stein Discrepancy

81% match1 repo22024

Boosting Nyström Method

81% match2023

Making the Nyström method highly accurate for low-rank approximations

80% match2023

On the Approximation of Kernel functions

80% match2024

Faster Low-Rank Approximation and Kernel Ridge Regression via the Block-Nyström Method

79% match2025

Kernel Quadrature with Randomly Pivoted Cholesky

77% match1 repo12023

Cite this paper

@article{hayakawa2023samplingbased,
  title  = {Sampling-based Nyström Approximation and Kernel Quadrature},
  author = {Satoshi Hayakawa and Harald Oberhauser and Terry Lyons},
  year   = {2023},
  eprint = {2301.09517},
  archivePrefix = {arXiv},
  url    = {http://arxiv.org/abs/2301.09517v3},
  journal = {ICML 2023 2023}
}

Add a badge to your README

Shows whether official code is linked for this paper.

Code of Paper badge
[![Code of Paper](https://codeofpaper.com/badge/2301.09517.svg)](https://codeofpaper.com/paper/2301.09517)

Discussion