2024/09/27 by Cai, Mou, Goda, Takashi, Kazashi, Yoshihito · 1 citation
#FOS: Mathematics #Numerical Analysis (math.NA)
paper · doi:10.48550/arxiv.2409.18757
We propose a randomized lattice algorithm for approximating multivariate periodic functions over the d-dimensional unit cube from the weighted Korobov space with mixed smoothness α> 1/2 and product weights γ1,γ2,…∈ [0,1]. Building upon the deterministic lattice algorithm by Kuo, Sloan, and Woźniakowski (2006), we incorporate a randomized quadrature rule by Dick, Goda, and Suzuki (2022) to accelerate the convergence rate. This randomization involves drawing the number of points for function evaluations randomly, and selecting a good generating vector for rank-1 lattice points using the randomized component-by-component algorithm. We prove that our randomized algorithm achieves a worst-case root mean squared L2-approximation error of order M-α(2α+1)/(4α+1)+ε for an arbitrarily small ε > 0, where M denotes the maximum number of function evaluations, and that the error bound is independent of the dimension d if the weights satisfy ∑j=1^∞ γj1/α < ∞. Our upper bound converges faster than a lower bound on the worst-case L2-approximation error for deterministic rank-1 lattice-based approximation proved by Byrenheid, Kämmerer, Ullrich, and Volkmer (2017). We also show a lower error bound of order M-α/2-1/2 for our randomized algorithm, leaving a slight gap between the upper and lower bounds open for future research.