Walsh Figure of Merit for Digital Nets: An Easy Measure for Higher Order Convergent QMC

Abstract

Fix an integer $s$. Let $f:[0,1{)}^s\to \mathbb{R}$ be an integrable function. Let $P\subset [0,1{]}^s$ be a finite point set. Quasi-Monte Carlo integration of $f$ by $P$ is the average value of $f$ over $P$ that approximates the integration of $f$ over the $s$-dimensional cube. Koksma-Hlawka inequality tells that, by a smart choice of $P$, one may expect that the error decreases roughly $O(N^{-1}(\log N{)}^s)$. For any $\alpha \ge 1$, J.\ Dick gave a construction of point sets such that for $\alpha$-smooth $f$, convergence rate $O(N^{-\alpha }(\log N{)}^{s\alpha })$ is assured. As a coarse version of his theory, M-Saito-Matoba introduced Walsh figure of Merit (WAFOM), which gives the convergence rate $O(N^{-C\log N/s})$. WAFOM is efficiently computable. By a brute-force search of low WAFOM point sets, we observe a convergence rate of order $N^{-\alpha }$ with $\alpha >1$, for several test integrands for $s=4$ and $8$.

17 pages, 4 figures. Submitted to: Monte Carlo and Quasi-Monte Carlo Methods 2014

References in corpus (4)

• WAFOM on abelian groups for quasi-Monte Carlo point sets
• Quasi-Monte Carlo point sets with small $t$-values and WAFOM
• The Mean Square Quasi-Monte Carlo Error for Digitally Shifted Digital Nets
• Bounds on Walsh coefficients by dyadic difference and a new Koksma-Hlawka type inequality for Quasi-Monte Carlo integration

Cited by in corpus (1)

• Quasi-Monte Carlo point sets with small $t$-values and WAFOM