Sparse grids vs. random points for high-dimensional polynomial approximation
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_ | 1866911030013067264 |
|---|---|
| author | Eggl, Jakob Mindlberger, Elias Ullrich, Mario |
| author_facet | Eggl, Jakob Mindlberger, Elias Ullrich, Mario |
| contents | We study polynomial approximation on a $d$-cube, where $d$ is large, and compare interpolation on sparse grids, aka Smolyak's algorithm (SA), with a simple least squares method based on randomly generated points (LS) using standard benchmark functions. Our main motivation is the influential paper [Barthelmann, Novak, Ritter: High dimensional polynomial interpolation on sparse grids, Adv. Comput. Math. 12, 2000]. We repeat and extend their theoretical analysis and numerical experiments for SA and compare to LS in dimensions up to 100. Our extensive experiments demonstrate that LS, even with only slight oversampling, consistently matches the accuracy of SA in low dimensions. In high dimensions, however, LS shows clear superiority. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2506_24054 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sparse grids vs. random points for high-dimensional polynomial approximation Eggl, Jakob Mindlberger, Elias Ullrich, Mario Numerical Analysis 65D05 (Primary) We study polynomial approximation on a $d$-cube, where $d$ is large, and compare interpolation on sparse grids, aka Smolyak's algorithm (SA), with a simple least squares method based on randomly generated points (LS) using standard benchmark functions. Our main motivation is the influential paper [Barthelmann, Novak, Ritter: High dimensional polynomial interpolation on sparse grids, Adv. Comput. Math. 12, 2000]. We repeat and extend their theoretical analysis and numerical experiments for SA and compare to LS in dimensions up to 100. Our extensive experiments demonstrate that LS, even with only slight oversampling, consistently matches the accuracy of SA in low dimensions. In high dimensions, however, LS shows clear superiority. |
| title | Sparse grids vs. random points for high-dimensional polynomial approximation |
| topic | Numerical Analysis 65D05 (Primary) |
| url | https://arxiv.org/abs/2506.24054 |