A Monte Carlo method for integration of multivariate smooth functions

DOI10.1137/16M1075557MaRDI QIDQ5347536zbMATH OpenOpenAlexFDO

Authors Mario Ullrich

Publication date 24 May 2017

Published in SIAM Journal on Numerical Analysis (Search for Journal in Brave)

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

zbMATH Keywords

frolov cubatureMonte Carlo methodSobolev spaces

Mathematics Subject Classification ID

Fourier and Fourier-Stieltjes transforms and other transforms of Fourier type (42B10) Sobolev spaces and other spaces of ``smooth functions, embedding theorems, trace theorems (46E35) Monte Carlo methods (65C05) Numerical integration (65D30) Analysis of algorithms and problem complexity (68Q25)

Abstract: 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 optimal order of convergence for functions from the Sobolev spaces $H_p^s$ with isotropic, anisotropic, or mixed smoothness with given compact support for all values of the parameters. If the region of integration is the unit cube, we obtain the same optimal orders for functions without boundary conditions. This proves, in particular, that the optimal order of convergence in the latter case is $n^{-s-1/2}$ for $pge2$, 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 natural function spaces.

Recommendations

• A universal algorithm for multivariate integration
• Large-Scale Scientific Computing
• scientific article; zbMATH DE number 2051231
• A new optimal Monte Carlo method for calculating integrals of smooth functions
• On the optimization of approximate integration by Monte Carlo methods

Cites work

• A direct proof of Sobolev embeddings for quasi-homogeneous Lizorkin-Triebel spaces with mixed norms
• A universal algorithm for multivariate integration
• An estimate of the mean remainder term in quadrature formulae
• Change of variable in spaces of mixed smoothness and numerical integration of multivariate functions on the unit cube
• Constructing Randomly Shifted Lattice Rules in Weighted Sobolev Spaces
• Cubature formulae for Besov classes
• CUBATURE FORMULAS FOR CLASSES OF FUNCTIONS WITH BOUNDED MIXED DIFFERENCE
• Cubature formulas, discrepancy, and nonlinear approximation
• Deterministic and stochastic error bounds in numerical analysis
• Discrepancy theory and quasi-Monte Carlo integration
• scientific article; zbMATH DE number 3870002 (Why is no real title available?)
• scientific article; zbMATH DE number 4080153 (Why is no real title available?)
• scientific article; zbMATH DE number 3558807 (Why is no real title available?)
• scientific article; zbMATH DE number 515830 (Why is no real title available?)
• scientific article; zbMATH DE number 721668 (Why is no real title available?)
• scientific article; zbMATH DE number 1049042 (Why is no real title available?)
• scientific article; zbMATH DE number 3316189 (Why is no real title available?)
• scientific article; zbMATH DE number 3367521 (Why is no real title available?)
• On ``Upper error bounds for quadrature formulas on function classes by K. K. Frolov
• On the approximate calculation of multiple integrals
• Optimal importance sampling for the approximation of integrals
• Optimal quadrature for Haar wavelet spaces
• Product rules are optimal for numerical integration in classical smoothness spaces
• Randomly shifted lattice rules for unbounded integrands
• Some results on the complexity of numerical integration
• The role of Frolov's cubature formula for functions with bounded mixed derivative
• Tractability of multivariate problems. Volume II: Standard information for functionals.

Cited in

(40)

• An iterative computation of approximations on Korobov-like spaces.
• On the orthogonality of the Chebyshev-Frolov lattice and applications
• A note on the dispersion of admissible lattices
• Optimal Monte Carlo methods for \(L^2\)-approximation
• Digital net properties of a polynomial analogue of Frolov's construction
• A Monte Carlo computation of polynomial approximations on a hypercube
• Numerical performance of optimized Frolov lattices in tensor product reproducing kernel Sobolev spaces
• Monte Carlo integration of non-differentiable functions on \([0,1]^\iota\), \(\iota =1,\ldots, d\), using a single determinantal point pattern defined on \([0,1]^d\)
• On the effective dimension and multilevel Monte Carlo
• Optimal randomized quadrature for weighted Sobolev and Besov classes with the Jacobi weight on the ball
• Monte Carlo with determinantal point processes
• Explicit error bounds for randomized Smolyak algorithms and an application to infinite-dimensional integration
• Optimal Monte Carlo integration on closed manifolds
• Optimal confidence for Monte Carlo integration of smooth functions
• On the approximate calculation of multiple integrals
• Change of variable in spaces of mixed smoothness and numerical integration of multivariate functions on the unit cube
• A universal algorithm for multivariate integration
• Complexity of Monte Carlo integration for Besov classes on the unit sphere
• Consistency of randomized integration methods
• scientific article; zbMATH DE number 6613559 (Why is no real title available?)
• An optimal Monte Carlo algorithm for multivariate Feynman–Kac path integrals
• A new optimal Monte Carlo method for calculating integrals of smooth functions
• scientific article; zbMATH DE number 2051231 (Why is no real title available?)
• Recovery of Sobolev functions restricted to iid sampling
• Component-by-component construction of randomized rank-1 lattice rules achieving almost the optimal randomized error rate
• Monte Carlo integration with a growing number of control variates
• Large-Scale Scientific Computing
• Stratified Monte Carlo integration
• Random-prime-fixed-vector randomised lattice-based algorithm for high-dimensional integration
• Higher-Order Monte Carlo through Cubic Stratification
• A Universal Median Quasi-Monte Carlo Integration
• Linear Monte Carlo quadrature with optimal confidence intervals
• Lattice rules with random \(n\) achieve nearly the optimal \(\mathcal{O}(n^{-\alpha-1/2})\) error independently of the dimension
• A simple universal algorithm for high-dimensional integration
• Accelerated convergence of error quantiles using robust randomized quasi Monte Carlo methods
• Optimal restricted Monte Carlo integration on generalized Hölder classes
• A randomised lattice rule algorithm with pre-determined generating vector and random number of points for Korobov spaces with \(0 < \alpha \le 1/2\)
• Optimal algorithms for numerical integration: recent results and open problems
• L₂-approximation using randomized lattice algorithms
• Monte Carlo computation of the mean of a function with convex support

This page was built for publication: A Monte Carlo method for integration of multivariate smooth functions

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