Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition
From MaRDI portal
(Redirected from Publication:2016136)
Abstract: We study the numerical integration problem for functions with infinitely many variables. The function spaces of integrands we consider are weighted reproducing kernel Hilbert spaces with norms related to the ANOVA decomposition of the integrands. The weights model the relative importance of different groups of variables. We investigate randomized quadrature algorithms and measure their quality by estimating the randomized worst-case integration error. In particular, we provide lower error bounds for a very general class of randomized algorithms that includes non-linear and adaptive algorithms. Furthermore, we propose new randomized changing dimension algorithms and present favorable upper error bounds. For product weights and finite-intersection weights our lower and upper error bounds match and show that our changing dimension algorithms are optimal in the sense that they achieve convergence rates arbitrarily close to the best possible convergence rate. As more specific examples, we discuss unanchored Sobolev spaces of different degrees of smoothness and randomized changing dimension algorithms that use as building blocks scrambled polynomial lattice rules. Our analysis extends the analysis given in [J. Baldeaux, M. Gnewuch. Optimal randomized multilevel algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition. arXiv:1209.0882v1 [math.NA], Preprint 2012]. In contrast to the previous article we now investigate a different cost model for algorithms. With respect to that cost model, randomized multilevel algorithms cannot, in general, achieve optimal convergence rates, but, as we prove for important classes of weights, changing dimension algorithms actually can.
Recommendations
- Optimal randomized multilevel algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition
- Infinite-dimensional integration in weighted Hilbert spaces: anchored decompositions, optimal deterministic algorithms, and higher-order convergence
- The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension
- Lower error bounds for randomized multilevel and changing dimension algorithms
- Multi-level Monte Carlo algorithms for infinite-dimensional integration on \(\mathbb R^{\mathbb N}\)
Cites work
- scientific article; zbMATH DE number 5797591 (Why is no real title available?)
- scientific article; zbMATH DE number 193625 (Why is no real title available?)
- scientific article; zbMATH DE number 1103058 (Why is no real title available?)
- scientific article; zbMATH DE number 822320 (Why is no real title available?)
- A class of generalized Walsh functions
- Deterministic and stochastic error bounds in numerical analysis
- Deterministic multi-level algorithms for infinite-dimensional integration on \(\mathbb R^{\mathbb N}\)
- Dimension-wise integration of high-dimensional functions with applications to finance
- Estimating Mean Dimensionality of Analysis of Variance Decompositions
- Fast algorithms for component-by-component construction of rank-1 lattice rules in shift-invariant reproducing kernel Hilbert spaces
- Fast component-by-component construction, a reprise for different kernels
- Good lattice rules in weighted Korobov spaces with general weights
- H = W
- High-dimensional integration: The quasi-Monte Carlo way
- Higher order scrambled digital nets achieve the optimal rate of the root mean square error for smooth integrands
- Infinite-dimensional integration in weighted Hilbert spaces: anchored decompositions, optimal deterministic algorithms, and higher-order convergence
- Infinite-dimensional integration on weighted Hilbert spaces
- Infinite-dimensional quadrature and approximation of distributions
- Liberating the dimension
- Liberating the dimension for \(L_2\)-approximation
- Liberating the dimension for function approximation
- Liberating the dimension for function approximation: standard information
- Low-discrepancy point sets obtained by digital constructions over finite fields
- Lower error bounds for randomized multilevel and changing dimension algorithms
- Monte Carlo complexity of global solution of integral equations
- Monte Carlo simulation of stochastic integrals when the cost of function evaluation is dimension dependent
- Multi-level Monte Carlo algorithms for infinite-dimensional integration on \(\mathbb R^{\mathbb N}\)
- Multilevel Monte Carlo Path Simulation
- On decompositions of multivariate functions
- On tractability of path integration
- On weighted Hilbert spaces and integration of functions of infinitely many variables
- Optimal randomized multilevel algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition
- QMC rules of arbitrary high order: Reproducing kernel Hilbert space approach
- Quasi-Monte Carlo finite element methods for a class of elliptic partial differential equations with random coefficients
- Randomization for continuous problems
- Scrambled polynomial lattice rules for infinite-dimensional integration
- Smoothing noisy data with spline functions: Estimating the correct degree of smoothing by the method of generalized cross-validation
- The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension
- The smoothing effect of integration in \(\mathbb R^d\) and the ANOVA decomposition
- The smoothing effect of the ANOVA decomposition
- Theory of Reproducing Kernels
- Toward real-time pricing of complex financial derivatives
- Tractability of infinite-dimensional integration in the worst case and randomized settings
- Tractability of multivariate problems. Volume I: Linear information
- When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?
Cited in
(18)- 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
- Countable tensor products of Hermite spaces and spaces of Gaussian kernels
- Hyperbolic cross approximation in infinite dimensions
- Multi-level Monte Carlo algorithms for infinite-dimensional integration on \(\mathbb R^{\mathbb N}\)
- On equivalence of weighted anchored and ANOVA spaces of functions with mixed smoothness of order one in \(L_1\) or \(L_\infty\)
- Variable subspace sampling and multi-level algorithms
- MDFEM: multivariate decomposition finite element method for elliptic PDEs with uniform random diffusion coefficients using higher-order QMC and FEM
- Infinite-dimensional integration in weighted Hilbert spaces: anchored decompositions, optimal deterministic algorithms, and higher-order convergence
- Explicit error bounds for randomized Smolyak algorithms and an application to infinite-dimensional integration
- A note on the periodic \(L_2\)-discrepancy of Korobov's \(p\)-sets
- Infinite-dimensional integration and the multivariate decomposition method
- The ANOVA decomposition of a non-smooth function of infinitely many variables can have every term smooth
- 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
- An algorithm-driven approach to error analysis for multidimensional integration
- Some results on the complexity of numerical integration
- Construction of interlaced scrambled polynomial lattice rules of arbitrary high order
This page was built for publication: Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2016136)
