Sparse grids vs. random points for high-dimensional polynomial approximation
Abstract
Abstract 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 [4]. We repeat and extend their theoretical analysis and numerical experiments for SA and compare them 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.
Fields of Study & Subjects
Stochastic Gradient Optimization Techniques
Markov Chains and Monte Carlo Methods
Mathematical Approximation and Integration
Publication details
- Journal / source
- Advances in Computational Mathematics
- Publisher
- Springer Science and Business Media LLC
- Volume
- 52
- Issue
- 3
- Publication date
- 1 June 2026
- Language
- EN