Universal $L^2$-approximation using median digital-net algorithms

Abstract

We propose a median digital-net algorithm for $L^2$-approximation of non-periodic functions over $[0,1{]}^s$, inspired by the recently developed median lattice algorithms for the periodic setting. The algorithm requires no smoothness or weight parameters but only a sufficiently large candidate Walsh index set $K$. It proceeds in three stages: generating multiple estimates of the Walsh coefficients in $K$ using independent randomized digital-net samples; taking the respective median of both the estimates and their absolute values; then, based on these median values, identifying the dominant coefficients and constructing a truncated Walsh series as the final approximation. We prove that if the target function has dominating mixed partial derivatives up to order $\hat{I}\pm$, all having finite Vitali variation of fractional order $\hat{I}»$, then the algorithm achieves an $L^2$-error of $\mathcal{O}(M^{-\hat{I}\pm -\hat{I}»+\hat{I}\cdot })$ with high probability, where $M$ is the total number of function evaluations and $\hat{I}\cdot >0$ is arbitrarily small. Furthermore, the implied constant grows at most polynomially in the dimension $s$ under suitable decay conditions on the ANOVA components of the target function. On the implementation side, we provide both parameter-dependent and -independent constructions of the index set $K$, and employ the fast Walsh--Hadamard transform and Gray code ordering to accelerate the algorithm. Numerical experiments support the theoretical analysis and demonstrate that the proposed algorithm remains effective in high-dimensional settings.

Topics & keywords