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

Rocky Mountain Journal of Mathematics

Integration and $L_2$-Approximation: Average Case Setting with Isotropic Wiener Measure for Smooth Functions

Klaus Ritter, G.W. Wasilkowski

Published Dec 1, 1996• 10 citations
Publisher

Abstract

. We propose isotropic probability measures defined on classes of smooth multivariate functions. These provide a natural extension of the classical isotropic Wiener measure to multivariate functions from C 2r . We show that in the corresponding average case setting the minimal errors of algorithms that use n function values are \\Theta \\Gamma n \\Gamma(d+4r+1)=2d \\Delta and \\Theta \\Gamma n \\Gamma(4r+1)=2d \\Delta for the integration and L 2 -approximation problems respectively. Here d is the number of variables of the corresponding class of functions. This means that the minimal average errors depend essentially on the number d of variables. In particular, for d large relative to r, the L 2 -approximation problem is intractable. The integration and L 2 -approximation problems have been recently studied with measures whose covariance kernels are tensor products. The results for these measures and for isotropic measures differ significantly. 1 Introduction We study the integratio...

DOI
10.1216/rmjm/1181072003

Related papers

Cubature and Reconstruction of Smooth Isotropic Random Functions

K. Ritter, G.W. Wasilkowski

We propose isotropic probability measures defined on classes of smooth multivariate functions. These provide a natural extension of the classical isotropic Wiener measure to multivariate functions from C 2r . We show that in the corresponding average case setting the minimal errors of algorithms that use n function values are Θ (n -(d+4r+1)/2d ) and Θ (n -(4r+1)/2d ) for the integration and L 2 -approximation problems respectively. Here d is the number of variables of the corresponding class of functions. This means that the minimal average errors depend essentially on the number d of variables. In particular, for d large relative to r, the L 2 -approximation problem is intractable. The integration and L 2 -approximation problems have been recently studied with measures whose covariance kernels are tensor products. The results for these measures and for isotropic measures differ significantly.

•Jan 1, 1997•0 citations

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

A Monte Carlo method for integration of multivariate smooth functions I: Sobolev spaces

Mario Ullrich

We study a Monte Carlo algorithm that is based on a specific (randomly shifted and dilated) lattice point set. The main result of this paper is that the mean squared error for a given compactly supported, square-integrable function is bounded by $n^{-1/2}$ times the $L_2$-norm of the Fourier transform outside a region around the origin, where $n$ is the expected number of function evaluations. As corollaries we obtain the order of convergence for the Sobolev spaces $H^s_p$ with isotropic, anisotropic or mixed smoothness for all values of the parameters. This proves, in particular, that the optimal order of convergence in the latter case is $n^{-s-1/2}$ for $p\ge2$, which is, in contrast to the case of deterministic algorithms, independent of the dimension. This shows that Monte Carlo algorithms can improve the order by more than $n^{-1/2}$ for a whole class of practically important function classes. All results carry over to functions defined on the unit cube without boundary conditions.

•Apr 20, 2016•1 citation

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

Michael Gnewuch, Klaus Ritter, Robin Rüßmann

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.

Mathematics of Computation•Jan 12, 2026•0 citations

Average Case (s, t)-Weak Tractability of L2-Approximation with Weighted Covariance Kernels

Jia Chen, Huichao Yan

We study the multivariate L2-approximation problem APPd defined over a Banach space in the average case setting. The space is equipped with a zero-mean Gaussian measure with a weighted covariance kernel, which depends on parameter sequences α={αj}j∈N and β={βj}j∈N with 1<α1≤α2≤⋯ and 1≥β1≥β2≥⋯>0. In this paper, two interesting weighted covariance kernels are considered, which model the importance of the covariance kernels. Under the absolute error criterion or the normalized error criterion, we discuss (s,t)-weak tractability of the L2-approximation problem APP={APPd}d∈N from a Banach space whose zero-mean Gaussian measure has the above two weighted covariance kernels for some positive numbers s and t in the average case setting. Here, (s,t)-weak tractability means how the information complexity behaves as a function of dt and ε−s for large dimension d and small threshold ε. In particular, for all s>0 and t∈(0,1), we find the matching sufficient and necessary condition on the parameter sequences α={αj}j∈N and β={βj}j∈N to obtain (s,t)-weak tractability under the absolute error criterion or the normalized error criterion in the average case setting. We describe (s,t)-weak tractability by the matching sufficient and necessary condition, which reflects symmetry.

Symmetry•Nov 14, 2024•0 citations

Integration and Approximation of Multivariate Functions: Average Case Complexity with Isotropic Wiener Measure

G.W. Wasilkowski

Journal of Approximation Theory•May 1, 1994•18 citations
Integration and L2L_2L2​-Approximation: Average Case Setting with Isotropic Wiener Measure for Smooth Functions
. We propose isotropic probability measures defined on classes of smooth multivariate functions. These provide a natural extension of the classical isotropic Wiener measure to multivariate functions from C 2r . We show that in the corresponding average case setting the minimal errors of algorithms that use n function values are \Theta \Gamma n \Gamma(d+4r+1)=2d \Delta and \Theta \Gamma n \Gamma(4r+1)=2d \Delta for the integration and L 2 -approximation problems respectively. Here d is the number of variables of the corresponding class of functions. This means that the minimal average errors depend essentially on the number d of variables. In particular, for d large relative to r, the L 2 -approximation problem is intractable. The integration and L 2 -approximation problems have been recently studied with measures whose covariance kernels are tensor products. The results for these measures and for isotropic measures differ significantly. 1 Introduction We study the integratio...
We propose isotropic probability measures defined on classes of smooth multivariate functions. These provide a natural extension of the classical isotropic Wiener measure to multivariate functions from C 2r . We show that in the corresponding average case setting the minimal errors of algorithms that use n function values are Θ (n -(d+4r+1)/2d ) and Θ (n -(4r+1)/2d ) for the integration and L 2 -approximation problems respectively. Here d is the number of variables of the corresponding class of functions. This means that the minimal average errors depend essentially on the number d of variables. In particular, for d large relative to r, the L 2 -approximation problem is intractable. The integration and L 2 -approximation problems have been recently studied with measures whose covariance kernels are tensor products. The results for these measures and for isotropic measures differ significantly.
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.
We study a Monte Carlo algorithm that is based on a specific (randomly shifted and dilated) lattice point set. The main result of this paper is that the mean squared error for a given compactly supported, square-integrable function is bounded by n−1/2n^{-1/2}n−1/2 times the L2L_2L2​-norm of the Fourier transform outside a region around the origin, where nnn is the expected number of function evaluations. As corollaries we obtain the order of convergence for the Sobolev spaces HpsH^s_pHps​ with isotropic, anisotropic or mixed smoothness for all values of the parameters. This proves, in particular, that the optimal order of convergence in the latter case is n−s−1/2n^{-s-1/2}n−s−1/2 for p≥2p\ge2p≥2, which is, in contrast to the case of deterministic algorithms, independent of the dimension. This shows that Monte Carlo algorithms can improve the order by more than n−1/2n^{-1/2}n−1/2 for a whole class of practically important function classes. All results carry over to functions defined on the unit cube without boundary conditions.
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.
We study the multivariate L2-approximation problem APPd defined over a Banach space in the average case setting. The space is equipped with a zero-mean Gaussian measure with a weighted covariance kernel, which depends on parameter sequences α={αj}j∈N and β={βj}j∈N with 1<α1≤α2≤⋯ and 1≥β1≥β2≥⋯>0. In this paper, two interesting weighted covariance kernels are considered, which model the importance of the covariance kernels. Under the absolute error criterion or the normalized error criterion, we discuss (s,t)-weak tractability of the L2-approximation problem APP={APPd}d∈N from a Banach space whose zero-mean Gaussian measure has the above two weighted covariance kernels for some positive numbers s and t in the average case setting. Here, (s,t)-weak tractability means how the information complexity behaves as a function of dt and ε−s for large dimension d and small threshold ε. In particular, for all s>0 and t∈(0,1), we find the matching sufficient and necessary condition on the parameter sequences α={αj}j∈N and β={βj}j∈N to obtain (s,t)-weak tractability under the absolute error criterion or the normalized error criterion in the average case setting. We describe (s,t)-weak tractability by the matching sufficient and necessary condition, which reflects symmetry.