A lattice algorithm with multiple shifts for function approximation in Korobov spaces

In this paper, we propose a novel algorithm for function approximation in a weighted Korobov space based on shifted rank-1 lattice rules. To mitigate aliasing errors inherent in lattice-based Fourier coefficient estimation, we employ $\mathcal{O}((\log N{)}^d)$ good shifts and recover each Fourier coefficient via a least-squares procedure. We show that the resulting approximation achieves the optimal convergence rate for the $L_{\mathrm{\infty }}$-approximation error in the worst-case setting, namely $\mathcal{O}(N^{-\alpha +1\mathrm{/}2+\epsilon })$ for arbitrarily small $\epsilon >0$. Moreover, by incorporating random shifts, the algorithm attains the optimal rate for the $L_2$-approximation error in the randomized setting, which is $\mathcal{O}(N^{-\alpha +\epsilon })$. Numerical experiments are presented to support the theoretical results.