Infinite-dimensional integration in weighted Hilbert spaces: anchored decompositions, optimal deterministic algorithms, and higher-order convergence

DOI10.1007/S10208-014-9198-8zbMATH Open1312.65002arXiv1210.4223OpenAlexW2050041808MaRDI QIDQ486680FDOQ486680

Authors: Josef Dick, Michael Gnewuch 

Publication date: 16 January 2015

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Abstract: We study numerical integration of functions depending on an infinite number of variables. We provide lower error bounds for general deterministic linear algorithms and provide matching upper error bounds with the help of suitable multilevel algorithms and changing dimension algorithms. More precisely, the spaces of integrands we consider are weighted reproducing kernel Hilbert spaces with norms induced by an underlying anchored function space decomposition. Here the weights model the relative importance of different groups of variables. The error criterion used is the deterministic worst case error. We study two cost models for function evaluation which depend on the number of active variables of the chosen sample points, and two classes of weights, namely product and order-dependent (POD) weights and the newly introduced weights with finite active dimension. We show for these classes of weights that multilevel algorithms achieve the optimal rate of convergence in the first cost model while changing dimension algorithms achieve the optimal convergence rate in the second model. As an illustrative example, we discuss the anchored Sobolev space with smoothness parameter $alpha$ and provide new optimal quasi-Monte Carlo multilevel algorithms and quasi-Monte Carlo changing dimension algorithms based on higher-order polynomial lattice rules.

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

Recommendations

• Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition
• Infinite-dimensional integration on weighted Hilbert spaces
• Optimal randomized multilevel algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition
• Liberating the dimension
• Lower error bounds for randomized multilevel and changing dimension algorithms

zbMATH Keywords

convergencenumerical integrationquasi-Monte Carlo methodsreproducing kernel Hilbert spaceserror boundnumerical examplepath integrationpolynomial lattice ruleschanging-dimension algorithmsmultilevel algorithms

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Irregularities of distribution, discrepancy (11K38) Hilbert spaces with reproducing kernels (= (proper) functional Hilbert spaces, including de Branges-Rovnyak and other structured spaces) (46E22)

Cites Work

• Theory of Reproducing Kernels
• Title not available (Why is that?)
• Multilevel Monte Carlo Path Simulation
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Monte Carlo complexity of global solution of integral equations
• Monte Carlo complexity of parametric integration
• A class of generalized Walsh functions
• Title not available (Why is that?)
• Walsh Spaces Containing Smooth Functions and Quasi–Monte Carlo Rules of Arbitrary High Order
• The decay of the Walsh coefficients of smooth functions
• Title not available (Why is that?)
• Quasi-Monte Carlo finite element methods for a class of elliptic partial differential equations with random coefficients
• Title not available (Why is that?)
• On the Walsh Functions
• Infinite-dimensional quadrature and approximation of distributions
• When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?
• Strong tractability of multivariate integration of arbitrary high order using digitally shifted polynomial lattice rules
• Low-discrepancy point sets obtained by digital constructions over finite fields
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Improved multilevel Monte Carlo convergence using the Milstein scheme
• Component-by-component constructions achieve the optimal rate of convergence for multivariate integration in weighted Korobov and Sobolev spaces
• On decompositions of multivariate functions
• Cubature formulas, discrepancy, and nonlinear approximation
• Evaluations of \(k\)-fold Euler/Zagier sums: a compendium of results for arbitrary \(k\)
• Good lattice rules in weighted Korobov spaces with general weights
• Liberating the dimension
• Dimension-wise integration of high-dimensional functions with applications to finance
• Weighted geometric discrepancies and numerical integration on reproducing kernel Hilbert spaces
• Construction algorithms for polynomial lattice rules for multivariate integration
• Multilevel quasi-Monte Carlo path simulation
• Infinite-dimensional integration on weighted Hilbert spaces
• The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension
• Monte Carlo simulation of stochastic integrals when the cost of function evaluation is dimension dependent
• Liberating the dimension for \(L_2\)-approximation
• On tractability of path integration
• Deterministic multi-level algorithms for infinite-dimensional integration on \(\mathbb R^{\mathbb N}\)
• Tractability of infinite-dimensional integration in the worst case and randomized settings
• Multi-level Monte Carlo algorithms for infinite-dimensional integration on \(\mathbb R^{\mathbb N}\)
• On weighted Hilbert spaces and integration of functions of infinitely many variables
• Lower error bounds for randomized multilevel and changing dimension algorithms
• Optimal randomized multilevel algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition
• Scrambled polynomial lattice rules for infinite-dimensional integration
• Finite-order weights imply tractability of multivariate integration
• Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition
• Construction algorithms for higher order polynomial lattice rules
• Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules
• Generalized tractability for multivariate problems. I: Linear tensor product problems and linear information

Cited In (21)

• Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition
• On weighted Hilbert spaces and integration of functions of infinitely many variables
• The numerical approximation of nonlinear functionals and functional differential equations
• A construction of polynomial lattice rules with small gain coefficients
• Embeddings for infinite-dimensional integration and \(L_2\)-approximation with increasing smoothness
• Embeddings of weighted Hilbert spaces and applications to multivariate and infinite-dimensional integration
• Deterministic multi-level algorithms for infinite-dimensional integration on \(\mathbb R^{\mathbb N}\)
• Hyperbolic cross approximation in infinite dimensions
• Variable subspace sampling and multi-level algorithms
• Efficient implementations of the multivariate decomposition method for approximating infinite-variate integrals
• Efficient algorithms for multivariate and \(\infty\)-variate integration with exponential weight
• MDFEM: multivariate decomposition finite element method for elliptic PDEs with uniform random diffusion coefficients using higher-order QMC and FEM
• High-dimensional integration on \(\mathbb{R}^d\), weighted Hermite spaces, and orthogonal transforms
• Explicit error bounds for randomized Smolyak algorithms and an application to infinite-dimensional integration
• Infinite-dimensional integration on weighted Hilbert spaces
• Infinite-dimensional integration and the multivariate decomposition method
• The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension
• Lower error bounds for randomized multilevel and changing dimension algorithms
• Optimal randomized multilevel algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition
• Some results on the complexity of numerical integration
• MDFEM: multivariate decomposition finite element method for elliptic PDEs with lognormal diffusion coefficients using higher-order QMC and FEM

This page was built for publication: Infinite-dimensional integration in weighted Hilbert spaces: anchored decompositions, optimal deterministic algorithms, and higher-order convergence

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