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

DOI10.1090/S0025-5718-2013-02774-3zbMATH Open1330.11051arXiv1109.3873MaRDI QIDQ5401700FDOQ5401700

Authors: Makoto Matsumoto, Mutsuo Saito, Kyle Matoba 

Publication date: 12 March 2014

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

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.

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)
• 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)