Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition
type: Item
instance of: scholarly article
title: Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition
zbMATH Open document ID: 1296.41025
author: Josef Dick
author: Michael Gnewuch
published in: Journal of Approximation Theory
publication date: 2014-06-19T00:00:00Z
full work available at URL: https://arxiv.org/abs/1306.2821
review text: The authors study numerical integration problems for functions with infinitely many variables. An important tool is the analysis of variance (ANOVA) decomposition of the integrand. The paper extends the analysis of convergence rates of random multilevel algorithms (a.o. quasi-Monte Carlo methods) started in [\textit{F. J. Hickernell} et al., J. Complexity 26, No. 3, 229--254 (2010; Zbl 1207.65005)] and [\textit{J. Baldeaux} and \textit{M. Gnewuch}, SIAM J. Numer. Anal. 52, 1128--1155 (2014)]. The layout of the paper, as indicated in the introduction, is given below: \S 1: Introduction (\(2 {1\over 2}\) pages) \qquad A thorough discussion of the background material and previous results \S 2: Preliminaries (\(9\) pages) \qquad Introduction of weights, function spaces, cost and error criteria and algorithms \S 3: Lower error bounds (\(2 {1\over 2}\) pages) \qquad Provides a.o. lower bounds for the error (cf. Theorem 1.1) \S 4: Changing dimension algorithms (\(9\) pages) \qquad The bound given before is shown to be sharp for finite-intersection and product weights (an upper bound is given, along with sharp upper error bounds) \S 5: Examples: unanchored Sobolev spaces and interlaced scrambled polynomial lattice rules (\(5\) pages) \qquad Unanchored Sobolev spaces of smoothness \(\xi\geq 1\) are studied and it is shown that the optimal rate of convergence is achieved in case of interlaced scrambled polynomial lattice rules. Appendix (\(3 {1\over 2}\) pages) \qquad Embedding between spaces and bounds on a square sum of Walsh coefficients for the functions studied in \S 5 are given.
reviewed by: Marcel G. de Bruin
Mathematics Subject Classification ID: 41A55
Mathematics Subject Classification ID: 28A25
Mathematics Subject Classification ID: 65C05
Mathematics Subject Classification ID: 65D32
Mathematics Subject Classification ID: 65Y20
Mathematics Subject Classification ID: 68W40
zbMATH DE Number: 6305514
zbMATH Keywords: ANOVA decomposition
zbMATH Keywords: randomized algorithms
zbMATH Keywords: numerical integration
zbMATH Keywords: multivariate decomposition method
zbMATH Keywords: dimension-wise quadrature method
zbMATH Keywords: quasi-Monte Carlo method
MaRDI profile type: Publication
OpenAlex ID: W1984820072
arXiv ID: 1306.2821
cites work: Q4369767
cites work: Theory of Reproducing Kernels
cites work: Scrambled Polynomial Lattice Rules for Infinite-Dimensional Integration
cites work: QMC rules of arbitrary high order: Reproducing kernel Hilbert space approach
cites work: Optimal Randomized Multilevel Algorithms for Infinite-Dimensional Integration on Function Spaces with ANOVA-Type Decomposition
cites work: A class of generalized Walsh functions
cites work: Smoothing noisy data with spline functions: Estimating the correct degree of smoothing by the method of generalized cross-validation
cites work: Infinite-dimensional quadrature and approximation of distributions
cites work: Higher order scrambled digital nets achieve the optimal rate of the root mean square error for smooth integrands
cites work: Infinite-dimensional integration in weighted Hilbert spaces: anchored decompositions, optimal deterministic algorithms, and higher-order convergence
cites work: High-dimensional integration: The quasi-Monte Carlo way
cites work: Q3160669
cites work: Good lattice rules in weighted Korobov spaces with general weights
cites work: Multilevel Monte Carlo Path Simulation
cites work: Infinite-dimensional integration on weighted Hilbert spaces
cites work: Lower Error Bounds for Randomized Multilevel and Changing Dimension Algorithms
cites work: On weighted Hilbert spaces and integration of functions of infinitely many variables
cites work: Dimension-wise integration of high-dimensional functions with applications to finance
cites work: The smoothing effect of the ANOVA decomposition
cites work: The smoothing effect of integration in $\mathbb {R}^d$ and the ANOVA decomposition
cites work: Monte Carlo complexity of global solution of integral equations
cites work: Multi-level Monte Carlo algorithms for infinite-dimensional integration on \(\mathbb R^{\mathbb N}\)
cites work: The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension
cites work: Quasi-Monte Carlo Finite Element Methods for a Class of Elliptic Partial Differential Equations with Random Coefficients
cites work: Liberating the dimension
cites work: On decompositions of multivariate functions
cites work: Estimating Mean Dimensionality of Analysis of Variance Decompositions
cites work: H = W
cites work: Low-discrepancy point sets obtained by digital constructions over finite fields
cites work: Toward real-time pricing of complex financial derivatives
cites work: Monte Carlo Simulation of Stochastic Integrals when the Cost of Function Evaluation Is Dimension Dependent
cites work: Deterministic multi-level algorithms for infinite-dimensional integration on \(\mathbb R^{\mathbb N}\)
cites work: Deterministic and stochastic error bounds in numerical analysis
cites work: Tractability of multivariate problems. Volume I: Linear information
cites work: Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces
cites work: Q5482377
cites work: Q4856469
cites work: Tractability of infinite-dimensional integration in the worst case and randomized settings
cites work: When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?
cites work: Q4040428
cites work: Randomization for continuous problems
cites work: Liberating the dimension for \(L_2\)-approximation
cites work: On tractability of path integration
cites work: Liberating the dimension for function approximation
cites work: Liberating the dimension for function approximation: standard information
DOI: 10.1016/J.JAT.2014.04.014
description: scientific article