Worst-case Lp-approximation of periodic functions using median lattice algorithms

Abstract

We study the worst-case approximation of multivariate periodic functions from weighted Korobov spaces H d , α , γ with smoothness α > 1 / 2 and weights γ in L p ( [ 0 , 1 ] d ) , 1 ≤ p ≤ ∞ . We analyze a median lattice algorithm that reconstructs a truncated Fourier series by estimating coefficients on a hyperbolic-cross-type index set using R rank-1 lattice sampling rules with independent randomly chosen generating vectors, and then aggregating the coefficient estimators via the componentwise median. For odd R and odd prime lattice size N , where R depends logarithmically on N , we prove high-probability error bounds in both L ∞ and L 2 . Interpolation then yields the result for all p ∈ [ 1 , ∞ ] . In particular, with high probability, the worst-case L p -error is bounded, for any β > 0 , by C d , α , β , γ , τ , p R 1 2 + ( 1 2 − 1 p ) + N − α + ( 1 2 − 1 p ) + + β , where ( x ) + = max ⁡ { x , 0 } , and the constant C d , α , β , γ , τ , p is independent of N and R . For p = ∞ , the constant is dimension-independent under the summability condition ∑ j = 1 ∞ γ j 1 / ( 2 α ) < ∞ .

The authors' abstract, as published at the source. Journal of Complexity, 2026 · DOI ↗