Walsh Figure of Merit

Walsh Figure of Merit (WAFOM) is a criterion for digital nets introduced by Matsumoto, Saito and Matoba (full-text PDF on arXiv). This page briefly recalls and expands the definition in my notation.


A digital net in base 2 is a linear subspace P of F2s×n, which is identified with a subset of [0 .. 1)s by the map φ. P is considered as a subspace of (F2⊕∞)s and let P be the orthogonal complement of P.

For a function f: [0 .. 1)sR, define the quasi-Monte Carlo integration of f by P as IPf := |P|−1xP f(x), by which we want to approximate the integral If := ∫[0 .. 1)s f(x) dx. We consider the (signed) QMC error errPf := IPf − If. Our goal is to obtain a good P which attains small |errPf| for many functions f.


The (continuous version of) Walsh Figure of Merit (WAFOM) of P is defined as the infinite sum Wμ(P) := ∑kP∖0is; jN 2μijkij of finite products. By Fourier inversion formula or Poisson summation formula, it is calculated as the finite sum Wμ(P) = −1 + |P|−1xPis; jN (1 + (−1)xij2μij) of infinite products.

Under a certain assumption Wμ(P) is well approximated by replacing P with {kP : ∀is ki < 2n}, and then it becomes computable as the sum of reasonable number of finite products Wμn(P) = −1 + |P|−1xPis; jn (1 + (−1)xij2μij). This is the discretized Walsh Figure of Merit introduced by Matsumoto, Saito and Matoba.

The weight μ determines the function class WAFOM deals with. Originally μij = j+1 was used, and the corresponding function class is introduced by Dick (full-text PDF on arXiv).


By replacing μij by j+2, Yoshiki showed another bound for the function class {f : [0 .. 1) → R; sup{||f(N)|| : NNs; 0 ≤ N < n; N ≠ 0} < +∞}. The supremum above times Wμ(P) bounds the QMC error.

Another direction of extension is done by considering the randomized QMC integration. The (discretized) Walsh Figure of Merit for root mean square error with respect to digital shifts, or root mean square (RMS) WAFOM in short, is defined similarly and calculated as W2μn(P) = √(−1 + |P|−1xPis; jn (1+(−1)xij2−2μij)). It bounds the root mean square error with respect to digital shift. This is the work of T. Goda, R. O., K. Suzuki and T. Yoshiki, presented in MCQMC2014 (article submitted to the proceedings is under review).