On efficient algorithms for computing near-best polynomial approximations to high-dimensional, Hilbert-valued functions from limited samples

Understand

Sparse polynomial approximation has become indispensable for approximating smooth, high- or infinite-dimensional functions from limited samples.

• This is a key task in computational science and engineering, e.g., surrogate modelling in uncertainty quantification where the function is the solution map of a parametric or stochastic differential equation (DE).
• Yet, sparse polynomial approximation lacks a complete theory.
• On the one hand, there is a well-developed theory of best $s$-term polynomial approximation, which asserts exponential or algebraic rates of convergence for holomorphic functions.