$L_2$-approximation using randomized lattice algorithms
<|reference_start|>$L_2$-approximation using randomized lattice algorithms: 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 $\alpha > 1/2$ and product weights $\gamma_1,\gamma_2,\ldots\in [0,1]$. Building upon the deterministic lattice algorithm by Kuo, Sloan, and Wo\'{z}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 $L_2$-approximation error of order $M^{-\alpha/2 - 1/8 + \varepsilon}$ for an arbitrarily small $\varepsilon > 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 $\sum_{j=1}^\infty \gamma_j^{1/\alpha} < \infty$. Our upper bound converges faster than a lower bound on the worst-case $L_2$-approximation error for deterministic rank-1 lattice-based approximation proved by Byrenheid, K\"{a}mmerer, Ullrich, and Volkmer (2017). We also show a lower error bound of order $M^{-\alpha/2-1/2}$ for our randomized algorithm, leaving a slight gap between the upper and lower bounds open for future research.<|reference_end|>
@article{cai2024$l_2$-approximation,
    title={$L_2$-approximation using randomized lattice algorithms},
    author={Mou Cai, Takashi Goda, Yoshihito Kazashi},
    journal={arXiv preprint arXiv:2409.18757},
    year={2024},
    archivePrefix={arXiv},
    eprint={2409.18757},
    primaryClass={math.NA cs.NA}
}