Fully symmetric kernel quadrature

Research output: Contribution to journalArticleScientificpeer-review

Standard

Fully symmetric kernel quadrature. / Karvonen, Toni; Särkkä, Simo.

In: SIAM Journal on Scientific Computing, Vol. 40, No. 2, 2018, p. A697-A720.

Research output: Contribution to journalArticleScientificpeer-review

Harvard

APA

Vancouver

Author

Bibtex - Download

@article{7c68109137944f0f990a307ca65a7844,
title = "Fully symmetric kernel quadrature",
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.",
keywords = "numerical integration, kernel quadrature, Bayesian quadrature, reproducing kernel, Hilbert spaces, fully symmetric sets, sparse grids",
author = "Toni Karvonen and Simo S{\"a}rkk{\"a}",
year = "2018",
doi = "10.1137/17M1121779",
language = "English",
volume = "40",
pages = "A697--A720",
journal = "SIAM Journal on Scientific Computing",
issn = "1064-8275",
number = "2",

}

RIS - Download

TY - JOUR

T1 - Fully symmetric kernel quadrature

AU - Karvonen, Toni

AU - Särkkä, Simo

PY - 2018

Y1 - 2018

N2 - 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.

AB - 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.

KW - numerical integration

KW - kernel quadrature

KW - Bayesian quadrature

KW - reproducing kernel

KW - Hilbert spaces

KW - fully symmetric sets

KW - sparse grids

U2 - 10.1137/17M1121779

DO - 10.1137/17M1121779

M3 - Article

VL - 40

SP - A697-A720

JO - SIAM Journal on Scientific Computing

JF - SIAM Journal on Scientific Computing

SN - 1064-8275

IS - 2

ER -

ID: 18149659