A computable figure of merit for quasi-Monte Carlo point sets

DOI10.1090/S0025-5718-2013-02774-3MaRDI QIDQ5401700zbMATH OpenFDO

Authors Makoto Matsumoto, Mutsuo Saito, Kyle Matoba

Publication date 12 March 2014

Published in Mathematics of Computation (Search for Journal in Brave)

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

zbMATH Keywords

numerical integrationquasi-Monte Carlodigital netsWalsh functionscomputational financefigure of meritlow discrepancy sequencesWAFOM

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Numerical integration (65D30) Irregularities of distribution, discrepancy (11K38) Pseudo-random numbers; Monte Carlo methods (11K45) Numerical methods for discrete and fast Fourier transforms (65T50)

Abstract: Let $mathcalPsubset[0,1{)}^S$ be a finite point set of cardinality $N$ in an $S$-dimensional cube, and let $f:[0,1{)}^{S}omathbbR$ be an integrable function. A QMC integration of $f$ by $mathcalP$ is the average of values of $f$ at each point in $mathcalP$, which approximates the integration of $f$ over the cube. Assume that $mathcalP$ is constructed from an $mathbbF2$-vector space $Psubset(F{2}^n{)}^S$ by means of a digital net with $n$-digit precision. As an $n$-digit discretized version of Josef Dick's method, we introduce Walsh figure of merit (WAFOM) $extnormalWF(P)$ of $P$, which satisfies a Koksma-Hlawka type inequality, namely, QMC integration error is bounded by $C_{S,n}||f|{|}_{n}extnormalWF(P)$ under $n$-smoothness of $f$, where $C_{S,n}$ is a constant depending only on $S,n$. We show a Fourier inversion formula for $extnormalWF(P)$ which is computable in $O(nSN)$ steps. This effectiveness enables us a random search for $P$ with small value of $extnormalWF(P)$, which would be difficult for other figures of merit such as discrepancy. From an analogy to coding theory, we expect that random search may find better point sets than mathematical constructions. In fact, a na"{i}ve search finds point sets $P$ with small $extnormalWF(P)$. In experiments, we show better performance of these point sets in QMC integration than widely used QMC rules. We show some experimental evidence on the effectiveness of our point sets to even non-smooth integrands appearing in finance.

Recommendations

• Walsh figure of merit for digital nets: an easy measure for higher order convergent QMC
• Existence of higher order convergent quasi-Monte Carlo rules via Walsh figure of merit
• Quasi-Monte Carlo point sets with small t-values and WAFOM
• WAFOM over abelian groups for quasi-Monte Carlo point sets
• A lower bound on WAFOM

Cites work

• scientific article; zbMATH DE number 2127877 (Why is no real title available?)
• scientific article; zbMATH DE number 5797591 (Why is no real title available?)
• scientific article; zbMATH DE number 3654722 (Why is no real title available?)
• scientific article; zbMATH DE number 53679 (Why is no real title available?)
• scientific article; zbMATH DE number 1151379 (Why is no real title available?)
• scientific article; zbMATH DE number 3440485 (Why is no real title available?)
• scientific article; zbMATH DE number 3082934 (Why is no real title available?)
• A Mathematical Theory of Communication
• Construction algorithms for higher order polynomial lattice rules
• Duality theory and propagation rules for generalized digital nets
• Duality theory and propagation rules for higher order nets
• Dyadic diaphony
• Efficient calculation of the worst-case error and (fast) component-by-component construction of higher order polynomial lattice rules
• Existence of higher order convergent quasi-Monte Carlo rules via Walsh figure of merit
• Explicit constructions in the classical mean squares problem in irregularities of point distribution
• Good error-correcting codes based on very sparse matrices
• Harmonic analysis on totally disconnected groups and irregularities of point distributions
• On quasi-Monte Carlo rules achieving higher order convergence
• Walsh Spaces Containing Smooth Functions and Quasi–Monte Carlo Rules of Arbitrary High Order

Cited in

(16)

• Existence of higher order convergent quasi-Monte Carlo rules via Walsh figure of merit
• Walsh figure of merit for digital nets: an easy measure for higher order convergent QMC
• The mean square quasi-Monte Carlo error for digitally shifted digital nets
• A lower bound on WAFOM
• An explicit construction of point sets with large minimum Dick weight
• scientific article; zbMATH DE number 1390116 (Why is no real title available?)
• A Universal Median Quasi-Monte Carlo Integration
• A New Quasi-Monte Carlo Technique Based on Nonnegative Least Squares and Approximate Fekete Points
• A quasi-Monte Carlo method for computing areas of point-sampled surfaces
• A search for extensible low-WAFOM point sets
• Computing the probability of union in the $n$-dimensional Euclidean space for application of the multivariate quantile: $p$-level efficient points
• Super-polynomial convergence and tractability of multivariate integration for infinitely times differentiable functions
• WAFOM over abelian groups for quasi-Monte Carlo point sets
• Construction of interlaced polynomial lattice rules for infinitely differentiable functions
• Quasi-Monte Carlo point sets with small t-values and WAFOM
• Approximation of quasi-Monte Carlo worst case error in weighted spaces of infinitely times smooth functions

This page was built for publication: A computable figure of merit for quasi-Monte Carlo point sets

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