Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Mathematics of Computation

Multi- and infinite-variate integration and 𝐿²-approximation on Hilbert spaces with Gaussian kernels

Michael Gnewuch, Klaus Ritter, Robin Rüßmann

Published Jan 12, 2026• 0 citations
Publisher

Abstract

We study integration and L 2 L^2 -approximation in the worst-case setting for deterministic linear algorithms based on function evaluations. The underlying function space is a reproducing kernel Hilbert space with a Gaussian kernel of tensor product form. In the infinite-variate case, for both computational problems, we establish matching upper and lower bounds for the polynomial convergence rate of the n n -th minimal error. In the multivariate case, we improve several tractability results for the integration problem. For the proofs, we establish the following transference result together with an explicit construction: Each of the computational problems on a space with a Gaussian kernel is equivalent on the level of algorithms to the same problem on a Hermite space with suitable parameters.

DOI
10.1090/mcom/4191

Related papers

Multi- and Infinite-variate Integration and $L^2$-Approximation on Hilbert Spaces with Gaussian Kernels

Michael Gnewuch, Klaus Ritter, Robin Rüßmann

We study integration and $L^2$-approximation in the worst-case setting for deterministic linear algorithms based on function evaluations. The underlying function space is a reproducing kernel Hilbert space with a Gaussian kernel of tensor product form. In the infinite-variate case, for both computational problems, we establish matching upper and lower bounds for the polynomial convergence rate of the $n$-th minimal error. In the multivariate case, we improve several tractability results for the integration problem. For the proofs, we establish the following transference result together with an explicit construction: Each of the computational problems on a space with a Gaussian kernel is equivalent on the level of algorithms to the same problem on a Hermite space with suitable parameters.

arXiv:2412.05368•Dec 6, 2024•1 citation

Infinite-dimensional integration and L2 -approximation on Hermite spaces

Michael Gnewuch, Aicke Hinrichs, Klaus Ritter +1 more

We study integration and L2-approximation of functions of infinitely many variables in the following setting: The underlying function space is the countably infinite tensor product of univariate Hermite spaces and the probability measure is the corresponding product of the standard normal distribution. The maximal domain of the functions from this tensor product space is necessarily a proper subset of the sequence space RN. We establish upper and lower bounds for the minimal worst case errors under general assumptions; these bounds do match for tensor products of well-studied Hermite spaces of functions with finite or with infinite smoothness. In the proofs we employ embedding results, and the upper bounds are attained constructively with the help of multivariate decomposition methods.

arXiv:2304.01754•Journal of Approximation Theory•Feb 8, 2024•5 citations

Tractability of $\mathbb{L}_2$-approximation in hybrid function spaces

Peter Kritzer, Helene Laimer, Friedrich Pillichshammer

We consider multivariate $\mathbb{L}_2$-approximation in reproducing kernel Hilbert spaces which are tensor products of weighted Walsh spaces and weighted Korobov spaces. We study the minimal worst-case error $e^{\mathbb{L}_2-\mathrm{app},Λ}(N,d)$ of all algorithms that use $N$ information evaluations from the class $Λ$ in the $d$-dimensional case. The two classes $Λ$ considered in this paper are the class $Λ^{\rm all}$ consisting of all linear functionals and the class $Λ^{\rm std}$ consisting only of function evaluations. The focus lies on the dependence of $e^{\mathbb{L}_2-\mathrm{app},Λ}(N,d)$ on the dimension $d$. The main results are conditions for weak, polynomial, and strong polynomial tractability.

arXiv:1701.02910•Jan 11, 2017•0 citations

Intractability results for integration in tensor product spaces

Erich Novak, Friedrich Pillichshammer

We study lower bounds on the worst-case error of numerical integration in tensor product spaces. As reference we use the $N$-th minimal error of linear rules that use $N$ function values. The information complexity is the minimal number $N$ of function evaluations that is necessary such that the $N$-th minimal error is less than a factor $\varepsilon$ times the initial error. We are interested to which extent the information complexity depends on the number $d$ of variables of the integrands. If the information complexity grows exponentially fast in $d$, then the integration problem is said to suffer from the curse of dimensionality. Under the assumption of the existence of a worst-case function for the uni-variate problem we present two methods for providing good lower bounds on the information complexity. The first method is based on a suitable decomposition of the worst-case function. This method can be seen as a generalization of the method of decomposable reproducing kernels, that is often successfully applied when integration in Hilbert spaces with a reproducing kernel is studied. The second method, although only applicable for positive quadrature rules, has the advantage, that it does not require a suitable decomposition of the worst-case function. Rather, it is based on a spline approximation of the worst-case function and can be used for analytic functions. The methods presented can be applied to problems beyond the Hilbert space setting. For demonstration purposes we apply them to several examples, notably to uniform integration over the unit-cube, weighted integration over the whole space, and integration of infinitely smooth functions over the cube. Some of these results have interesting consequences in discrepancy theory.

arXiv:2404.17163•Apr 26, 2024•0 citations

Tractability of $\mathbb{L}_2$-approximation in hybrid function spaces

Peter Kritzer, Helene Laimer, Friedrich Pillichshammer

We consider multivariate $\mathbb{L}_2$-approximation in reproducing kernel Hilbert spaces which are tensor products of weighted Walsh spaces and weighted Korobov spaces. We study the minimal worst-case error $e^{\mathbb{L}_2-\mathrm{app},\Lambda}(N,d)$ of all algorithms that use $N$ information evaluations from the class $\Lambda$ in the $d$-dimensional case. The two classes $\Lambda$ considered in this paper are the class $\Lambda^{{\rm all}}$ consisting of all linear functionals and the class $\Lambda^{{\rm std}}$ consisting only of function evaluations. The focus lies on the dependence of $e^{\mathbb{L}_2-\mathrm{app},\Lambda}(N,d)$ on the dimension $d$. The main results are conditions for weak, polynomial, and strong polynomial tractability.

Functiones et Approximatio Commentarii Mathematici•May 4, 2017•1 citation

The power of standard information for multivariate approximation in the randomized setting

G.W. Wasilkowski, H. Woźniakowski

We study approximating multivariate functions from a reproducing kernel Hilbert space with the error between the function and its approximation measured in a weighted $L_2$-norm. We consider functions with an arbitrarily large number of variables, $d$, and we focus on the randomized setting with algorithms using standard information consisting of function values at randomly chosen points. We prove that standard information in the randomized setting is as powerful as linear information in the worst case setting. Linear information means that algorithms may use arbitrary continuous linear functionals, and by the power of information we mean the speed of convergence of the $n$th minimal errors, i.e., of the minimal errors among all algorithms using $n$ function evaluations. Previously, it was only known that standard information in the randomized setting is no more powerful than the linear information in the worst case setting. We also study (strong) tractability of multivariate approximation in the randomized setting. That is, we study when the minimal number of function evaluations needed to reduce the initial error by a factor $\varepsilon$ is polynomial in $\varepsilon ^{-1}$ (strong tractability), and polynomial in $d$ and $\varepsilon ^{-1}$ (tractability). We prove that these notions in the randomized setting for standard information are equivalent to the same notions in the worst case setting for linear information. This result is useful since for a number of important applications only standard information can be used and verifying (strong) tractability for standard information is in general difficult, whereas (strong) tractability in the worst case setting for linear information is known for many spaces and is relatively easy to check. We illustrate the tractability results for weighted Korobov spaces. In particular, we present necessary and sufficient conditions for strong tractability and tractability. For product weights independent of $d$, we prove that strong tractability is equivalent to tractability. We stress that all proofs are constructive. That is, we provide randomized algorithms that enjoy the maximal speed of convergence. We also exhibit randomized algorithms which achieve strong tractability and tractability error bounds.

Mathematics of Computation•Dec 13, 2006•34 citations
We study integration and L 2 L^2 -approximation in the worst-case setting for deterministic linear algorithms based on function evaluations. The underlying function space is a reproducing kernel Hilbert space with a Gaussian kernel of tensor product form. In the infinite-variate case, for both computational problems, we establish matching upper and lower bounds for the polynomial convergence rate of the n n -th minimal error. In the multivariate case, we improve several tractability results for the integration problem. For the proofs, we establish the following transference result together with an explicit construction: Each of the computational problems on a space with a Gaussian kernel is equivalent on the level of algorithms to the same problem on a Hermite space with suitable parameters.
Multi- and Infinite-variate Integration and L2L^2L2-Approximation on Hilbert Spaces with Gaussian Kernels
We study integration and L2L^2L2-approximation in the worst-case setting for deterministic linear algorithms based on function evaluations. The underlying function space is a reproducing kernel Hilbert space with a Gaussian kernel of tensor product form. In the infinite-variate case, for both computational problems, we establish matching upper and lower bounds for the polynomial convergence rate of the nnn-th minimal error. In the multivariate case, we improve several tractability results for the integration problem. For the proofs, we establish the following transference result together with an explicit construction: Each of the computational problems on a space with a Gaussian kernel is equivalent on the level of algorithms to the same problem on a Hermite space with suitable parameters.
We study integration and L2-approximation of functions of infinitely many variables in the following setting: The underlying function space is the countably infinite tensor product of univariate Hermite spaces and the probability measure is the corresponding product of the standard normal distribution. The maximal domain of the functions from this tensor product space is necessarily a proper subset of the sequence space RN. We establish upper and lower bounds for the minimal worst case errors under general assumptions; these bounds do match for tensor products of well-studied Hermite spaces of functions with finite or with infinite smoothness. In the proofs we employ embedding results, and the upper bounds are attained constructively with the help of multivariate decomposition methods.
Tractability of L2\mathbb{L}_2L2​-approximation in hybrid function spaces
We consider multivariate L2\mathbb{L}_2L2​-approximation in reproducing kernel Hilbert spaces which are tensor products of weighted Walsh spaces and weighted Korobov spaces. We study the minimal worst-case error eL2−app,Λ(N,d)e^{\mathbb{L}_2-\mathrm{app},Λ}(N,d)eL2​−app,Λ(N,d) of all algorithms that use NNN information evaluations from the class ΛΛΛ in the ddd-dimensional case. The two classes ΛΛΛ considered in this paper are the class ΛallΛ^{\rm all}Λall consisting of all linear functionals and the class ΛstdΛ^{\rm std}Λstd consisting only of function evaluations. The focus lies on the dependence of eL2−app,Λ(N,d)e^{\mathbb{L}_2-\mathrm{app},Λ}(N,d)eL2​−app,Λ(N,d) on the dimension ddd. The main results are conditions for weak, polynomial, and strong polynomial tractability.
We study lower bounds on the worst-case error of numerical integration in tensor product spaces. As reference we use the NNN-th minimal error of linear rules that use NNN function values. The information complexity is the minimal number NNN of function evaluations that is necessary such that the NNN-th minimal error is less than a factor ε\varepsilonε times the initial error. We are interested to which extent the information complexity depends on the number ddd of variables of the integrands. If the information complexity grows exponentially fast in ddd, then the integration problem is said to suffer from the curse of dimensionality. Under the assumption of the existence of a worst-case function for the uni-variate problem we present two methods for providing good lower bounds on the information complexity. The first method is based on a suitable decomposition of the worst-case function. This method can be seen as a generalization of the method of decomposable reproducing kernels, that is often successfully applied when integration in Hilbert spaces with a reproducing kernel is studied. The second method, although only applicable for positive quadrature rules, has the advantage, that it does not require a suitable decomposition of the worst-case function. Rather, it is based on a spline approximation of the worst-case function and can be used for analytic functions. The methods presented can be applied to problems beyond the Hilbert space setting. For demonstration purposes we apply them to several examples, notably to uniform integration over the unit-cube, weighted integration over the whole space, and integration of infinitely smooth functions over the cube. Some of these results have interesting consequences in discrepancy theory.
Tractability of L2\mathbb{L}_2L2​-approximation in hybrid function spaces
We consider multivariate L2\mathbb{L}_2L2​-approximation in reproducing kernel Hilbert spaces which are tensor products of weighted Walsh spaces and weighted Korobov spaces. We study the minimal worst-case error eL2−app,Λ(N,d)e^{\mathbb{L}_2-\mathrm{app},\Lambda}(N,d)eL2​−app,Λ(N,d) of all algorithms that use NNN information evaluations from the class Λ\LambdaΛ in the ddd-dimensional case. The two classes Λ\LambdaΛ considered in this paper are the class Λall\Lambda^{{\rm all}}Λall consisting of all linear functionals and the class Λstd\Lambda^{{\rm std}}Λstd consisting only of function evaluations. The focus lies on the dependence of eL2−app,Λ(N,d)e^{\mathbb{L}_2-\mathrm{app},\Lambda}(N,d)eL2​−app,Λ(N,d) on the dimension ddd. The main results are conditions for weak, polynomial, and strong polynomial tractability.
We study approximating multivariate functions from a reproducing kernel Hilbert space with the error between the function and its approximation measured in a weighted L2L_2L2​-norm. We consider functions with an arbitrarily large number of variables, ddd, and we focus on the randomized setting with algorithms using standard information consisting of function values at randomly chosen points. We prove that standard information in the randomized setting is as powerful as linear information in the worst case setting. Linear information means that algorithms may use arbitrary continuous linear functionals, and by the power of information we mean the speed of convergence of the nnnth minimal errors, i.e., of the minimal errors among all algorithms using nnn function evaluations. Previously, it was only known that standard information in the randomized setting is no more powerful than the linear information in the worst case setting. We also study (strong) tractability of multivariate approximation in the randomized setting. That is, we study when the minimal number of function evaluations needed to reduce the initial error by a factor ε\varepsilonε is polynomial in ε−1\varepsilon ^{-1}ε−1 (strong tractability), and polynomial in ddd and ε−1\varepsilon ^{-1}ε−1 (tractability). We prove that these notions in the randomized setting for standard information are equivalent to the same notions in the worst case setting for linear information. This result is useful since for a number of important applications only standard information can be used and verifying (strong) tractability for standard information is in general difficult, whereas (strong) tractability in the worst case setting for linear information is known for many spaces and is relatively easy to check. We illustrate the tractability results for weighted Korobov spaces. In particular, we present necessary and sufficient conditions for strong tractability and tractability. For product weights independent of ddd, we prove that strong tractability is equivalent to tractability. We stress that all proofs are constructive. That is, we provide randomized algorithms that enjoy the maximal speed of convergence. We also exhibit randomized algorithms which achieve strong tractability and tractability error bounds.