Walsh Figure of Merit

Preliminaries

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

For a function f: [0 .. 1)^s → R, define the quasi-Monte Carlo integration of f by P as I^P_f := |P|⁻¹∏_{x ∈ P} f(x), by which we want to approximate the integral I_f := ∫_{[0 .. 1)^s} f(x) dx. We consider the (signed) QMC error err^P_f := I^P_f − I_f. Our goal is to obtain a good P which attains small |err^P_f| for many functions f.

Definition

The (continuous version of) Walsh Figure of Merit (WAFOM) of P is defined as the infinite sum W_μ(P) := ∑_{k ∈ P^⊥∖0} ∏_{i ∈ s; j ∈ N} 2^−μ_ijk_ij of finite products. By Fourier inversion formula or Poisson summation formula, it is calculated as the finite sum W_μ(P) = −1 + |P|⁻¹∑_{x ∈ P} ∏_{i ∈ s; j ∈ N} (1 + (−1)^x_ij2^−μ_ij) of infinite products.

Under a certain assumption W_μ(P) is well approximated by replacing P^⊥ with {k ∈ P^⊥ : ∀i∈s k_i < 2ⁿ}, and then it becomes computable as the sum of reasonable number of finite products W_μⁿ(P) = −1 + |P|⁻¹∑_{x ∈ P} ∏_{i ∈ s; j ∈ n} (1 + (−1)^x_ij2^−μ_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).

Extension

By replacing μ_ij by j+2, Yoshiki showed another bound for the function class {f : [0 .. 1) → R; sup{||f^(N)||_∞ : N ∈ N^s; 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 W_2μⁿ(P) = √(−1 + |P|⁻¹∑_{x ∈ P} ∏_{i ∈ s; j ∈ n} (1+(−1)^x_ij2^−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).