Fully Symmetric Kernel Quadrature

DOI10.1137/17M1121779zbMATH Open1385.65024arXiv1703.06359OpenAlexW2605229807MaRDI QIDQ4607640FDOQ4607640

Authors: Toni Karvonen, Simo Särkkä 

Publication date: 14 March 2018

Published in: SIAM Journal on Scientific Computing (Search for Journal in Brave)

Abstract: Kernel quadratures and other kernel-based approximation methods typically suffer from prohibitive cubic time and quadratic space complexity in the number of function evaluations. The problem arises because a system of linear equations needs to be solved. In this article we show that the weights of a kernel quadrature rule can be computed efficiently and exactly for up to tens of millions of nodes if the kernel, integration domain, and measure are fully symmetric and the node set is a union of fully symmetric sets. This is based on the observations that in such a setting there are only as many distinct weights as there are fully symmetric sets and that these weights can be solved from a linear system of equations constructed out of row sums of certain submatrices of the full kernel matrix. We present several numerical examples that show feasibility, both for a large number of nodes and in high dimensions, of the developed fully symmetric kernel quadrature rules. Most prominent of the fully symmetric kernel quadrature rules we propose are those that use sparse grids.

Full work available at URL: https://arxiv.org/abs/1703.06359

Recommendations

• scientific article; zbMATH DE number 5795783
• Kernel based quadrature on spheres and other homogeneous spaces
• scientific article; zbMATH DE number 3846809
• Peano kernel behaviour and error bounds for symmetric quadrature formulas
• Gaussian kernel quadrature at scaled Gauss-Hermite nodes
• \(k\)-kernel symmetric matrices
• Interior-point methods based on kernel functions for symmetric optimization
• Quasi-convex reproducing kernel meshfree method
• scientific article; zbMATH DE number 3917660
• Symmetry reduction of Fourier kernels

zbMATH Keywords

numerical examplesnumerical integrationreproducing kernel Hilbert spacessparse gridsBayesian quadraturekernel quadraturefully symmetric sets

Mathematics Subject Classification ID

Numerical quadrature and cubature formulas (65D32) Approximate quadratures (41A55) Hilbert spaces with reproducing kernels (= (proper) functional Hilbert spaces, including de Branges-Rovnyak and other structured spaces) (46E22)

Cites Work

• Algorithm 847
• Fully symmetric interpolatory rules for multiple integrals over infinite regions with Gaussian weight
• A stochastic algorithm for high-dimensional integrals over unbounded regions with Gaussian weight
• Fully Symmetric Interpolatory Rules for Multiple Integrals
• Gaussian processes for machine learning.
• Theory of Reproducing Kernels
• Probabilistic numerics and uncertainty in computations
• Title not available (Why is that?)
• Sparse grids
• Numerical integration using sparse grids
• Title not available (Why is that?)
• Bayes-Hermite quadrature
• Average-case analysis of numerical problems
• An algorithm for selecting a good value for the parameter \(c\) in radial basis function interpolation
• High dimensional integration of smooth functions over cubes
• Title not available (Why is that?)
• Title not available (Why is that?)
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• On choosing ``optimal shape parameters for RBF approximation
• On multivariate polynomial interpolation
• Toward real-time pricing of complex financial derivatives
• Title not available (Why is that?)
• Optimal Approximation in Hilbert Spaces with Reproducing Kernel Functions
• Stochastic collocation methods on unstructured grids in high dimensions via interpolation
• Title not available (Why is that?)
• Simple cubature formulas with high polynomial exactness
• Title not available (Why is that?)
• Gaussian measure in Hilbert space and applications in numerical analysis
• Scattered Data Approximation
• Sparse grid quadrature in high dimensions with applications in finance and insurance
• Higher-Dimensional Integration with Gaussian Weight for Applications in Probabilistic Design
• Title not available (Why is that?)
• A dimension adaptive sparse grid combination technique for machine learning
• Symmetric integration rules for hypercubes. I. Error coefficients
• Convergence analysis of deterministic kernel-based quadrature rules in misspecified settings
• Bayesian Probabilistic Numerical Methods
• Numerical cubature on scattered data by radial basis functions
• Title not available (Why is that?)
• Stochastic Integration Rules for Infinite Regions
• Multilevel sparse kernel-based interpolation
• Construction of fully symmetric numerical integration formulas
• On an interpolatory method for high dimensional integration
• Title not available (Why is that?)
• Multilevel quasi-interpolation on a sparse grid with the Gaussian

Cited In (9)

• Gaussian kernel quadrature at scaled Gauss-Hermite nodes
• Optimal Monte Carlo integration on closed manifolds
• On the positivity and magnitudes of Bayesian quadrature weights
• On the equivalence between kernel quadrature rules and random feature expansions
• Probabilistic integration: a role in statistical computation?
• Probabilistic linear solvers: a unifying view
• Bayesian Probabilistic Numerical Methods
• Symmetry exploits for Bayesian cubature methods
• Rejoinder: ``Probabilistic integration: a role in statistical computation?

Uses Software

• Spinterp
• PATSYM
• HRMSYM
• RANRTH

This page was built for publication: Fully Symmetric Kernel Quadrature

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4607640)