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

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•6 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•19 citations

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.

arXiv:2412.05368•Mathematics of Computation•Jan 12, 2026•3 citations

Complexity of Sobolev imbeddings and integration in the deterministic and randomized settings

Peixin Ye

This paper reformulates the problems of approximation of imbedding and integration from anisotropic Sobolev classes B(Wrp([0, 1]d)) in the deterministic, randomized and average case settings, and obtains the exact orders of the n-th minimal error of these problems in all three settings. The results show that in the case of B(Wrp([0, 1]d)) being not imbedded into the space of continuous functions C([0, 1]d), the randomized and average case error are essential smaller than the deterministic ones. Quantitatively, this maximal gain for imbedding problem amounts to the factor n-1+ε for any ε > 0, and for integration problem the gain is up to factor n-1 which is also the maximal speedup over the deterministic algorithms observed so far in natural numerical problems.

Scientia Sinica Mathematica•Mar 1, 2011•1 citation

Tractability of Multi-Parametric Euler and Wiener Integrated Processes

Mikhail Anatolievich Lifshits, Anargyros Papageorgiou, H. Woźniakowski

We study average case approximation of Euler and Wiener integrated processes of d variables which are almost surely r_k-times continuously differentiable with respect to the k-th variable. Let n(h,d) denote the minimal number of continuous linear functionals which is needed to find an algorithm that uses n such functionals and whose average case error improves the average case error of the zero algorithm by a factor h. Strong polynomial tractability means that there are nonnegative numbers C and p such that n(h,d)< C h^{-p} for all d and 0 1/(2\ln 3), whereas it holds for the Wiener case iff liminf r_k/k^s > 0 for some s>1/2. Other types of tractability are also studied.

arXiv:1112.4248•Dec 19, 2011•20 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 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 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.
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.
This paper reformulates the problems of approximation of imbedding and integration from anisotropic Sobolev classes B(Wrp([0, 1]d)) in the deterministic, randomized and average case settings, and obtains the exact orders of the n-th minimal error of these problems in all three settings. The results show that in the case of B(Wrp([0, 1]d)) being not imbedded into the space of continuous functions C([0, 1]d), the randomized and average case error are essential smaller than the deterministic ones. Quantitatively, this maximal gain for imbedding problem amounts to the factor n-1+ε for any ε > 0, and for integration problem the gain is up to factor n-1 which is also the maximal speedup over the deterministic algorithms observed so far in natural numerical problems.
We study average case approximation of Euler and Wiener integrated processes of d variables which are almost surely r_k-times continuously differentiable with respect to the k-th variable. Let n(h,d) denote the minimal number of continuous linear functionals which is needed to find an algorithm that uses n such functionals and whose average case error improves the average case error of the zero algorithm by a factor h. Strong polynomial tractability means that there are nonnegative numbers C and p such that n(h,d)< C h^{-p} for all d and 0 1/(2\ln 3), whereas it holds for the Wiener case iff liminf r_k/k^s > 0 for some s>1/2. Other types of tractability are also studied.