Universal $L^2$-approximation using median digital-net algorithms
This work provides a parameter-free algorithm for high-dimensional function approximation with theoretical guarantees, addressing a bottleneck in non-periodic settings.
The paper proposes a median digital-net algorithm for L2-approximation of non-periodic functions over [0,1]^s, achieving an error of O(M^{-α-λ+ε}) with high probability, where M is the number of function evaluations, and the constant grows polynomially in dimension under suitable conditions.
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 $α$, all having finite Vitali variation of fractional order $λ$, then the algorithm achieves an $L^2$-error of $\mathcal{O}(M^{-α-λ+ε})$ with high probability, where $M$ is the total number of function evaluations and $ε>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 to accelerate the algorithm. Numerical experiments support the theoretical analysis and demonstrate that the proposed algorithm remains effective in high-dimensional settings.