A lattice algorithm with multiple shifts for function approximation in Korobov spaces
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914153251209216 |
|---|---|
| author | Cai, Mou Dick, Josef Goda, Takashi |
| author_facet | Cai, Mou Dick, Josef Goda, Takashi |
| contents | 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_{\infty}$-approximation error in the worst-case setting, namely $\mathcal{O}(N^{-α+1/2+\varepsilon})$ for arbitrarily small $\varepsilon>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^{-α+\varepsilon})$. Numerical experiments are presented to support the theoretical results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_09071 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | A lattice algorithm with multiple shifts for function approximation in Korobov spaces Cai, Mou Dick, Josef Goda, Takashi Numerical Analysis 41A25, 41A63, 65D15, 65D30, 65Y20 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_{\infty}$-approximation error in the worst-case setting, namely $\mathcal{O}(N^{-α+1/2+\varepsilon})$ for arbitrarily small $\varepsilon>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^{-α+\varepsilon})$. Numerical experiments are presented to support the theoretical results. |
| title | A lattice algorithm with multiple shifts for function approximation in Korobov spaces |
| topic | Numerical Analysis 41A25, 41A63, 65D15, 65D30, 65Y20 |
| url | https://arxiv.org/abs/2511.09071 |