Construction of interlaced scrambled polynomial lattice rules of arbitrary high order

Abstract

Higher order scrambled digital nets are randomized quasi-Monte Carlo rules which have recently been introduced in [J. Dick, Ann. Statist., 39 (2011), 1372--1398] and shown to achieve the optimal rate of convergence of the root mean square error for numerical integration of smooth functions defined on the $s$-dimensional unit cube. The key ingredient there is a digit interlacing function applied to the components of a randomly scrambled digital net whose number of components is $ds$, where the integer $d$ is the so-called interlacing factor. In this paper, we replace the randomly scrambled digital nets by randomly scrambled polynomial lattice point sets, which allows us to obtain a better dependence on the dimension while still achieving the optimal rate of convergence. Our results apply to Owen's full scrambling scheme as well as the simplifications studied by Hickernell, Matoušek and Owen. We consider weighted function spaces with general weights, whose elements have square integrable partial mixed derivatives of order up to $\alpha \ge 1$, and derive an upper bound on the variance of the estimator for higher order scrambled polynomial lattice rules. Employing our obtained bound as a quality criterion, we prove that the component-by-component construction can be used to obtain explicit constructions of good polynomial lattice point sets. By first constructing classical polynomial lattice point sets in base $b$ and dimension $ds$, to which we then apply the interlacing scheme of order $d$, we obtain a construction cost of the algorithm of order $\mathcal{O}(dsm{b}^m)$ operations using $\mathcal{O}(b^m)$ memory in case of product weights, where $b^m$ is the number of points in the polynomial lattice point set.

References in corpus (3)

• Walsh spaces containing smooth functions and quasi-Monte Carlo rules of arbitrary high order
• Explicit constructions of quasi-Monte Carlo rules for the numerical integration of high dimensional periodic functions
• Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition

Cited by in corpus (18)

• The construction of good lattice rules and polynomial lattice rules
• Good interlaced polynomial lattice rules for numerical integration in weighted Walsh spaces
• Construction-free median quasi-Monte Carlo rules for function spaces with unspecified smoothness and general weights
• Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition
• Higher order Quasi-Monte Carlo integration for Bayesian Estimation
• Embeddings of Weighted Hilbert Spaces and Applications to Multivariate and Infinite-Dimensional Integration
• Digital nets with infinite digit expansions and construction of folded digital nets for quasi-Monte Carlo integration
• Richardson extrapolation of polynomial lattice rules
• Component-by-component construction of randomized rank-1 lattice rules achieving almost the optimal randomized error rate
• Construction of interlaced polynomial lattice rules for infinitely differentiable functions
• Recent advances in higher order quasi-Monte Carlo methods
• Convergence Analysis of Deterministic Kernel-Based Quadrature Rules in Misspecified Settings
• Multi-level higher order QMC Galerkin discretization for affine parametric operator equations
• Super-polynomial accuracy of one dimensional randomized nets using the median-of-means
• Richardson extrapolation allows truncation of higher order digital nets and sequences
• Constructing good higher order polynomial lattice rules with modulus of reduced degree
• Higher order Quasi-Monte Carlo integration for holomorphic, parametric operator equations
• On a projection-corrected component-by-component construction