$L_2$-approximation using randomized lattice algorithms
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915458406416384 |
|---|---|
| author | Cai, Mou Goda, Takashi Kazashi, Yoshihito |
| author_facet | Cai, Mou Goda, Takashi Kazashi, Yoshihito |
| contents | 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,\ldots\in [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 $L_2$-approximation error of order $M^{-α(2α+1)/(4α+1)+\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 γ_j^{1/α} < \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ä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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_18757 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | $L_2$-approximation using randomized lattice algorithms Cai, Mou Goda, Takashi Kazashi, Yoshihito Numerical Analysis 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,\ldots\in [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 $L_2$-approximation error of order $M^{-α(2α+1)/(4α+1)+\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 γ_j^{1/α} < \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ä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. |
| title | $L_2$-approximation using randomized lattice algorithms |
| topic | Numerical Analysis |
| url | https://arxiv.org/abs/2409.18757 |