English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Sparse polynomial approximation has become indispensable for approximatingsmooth, high- or infinite-dimensional functions from limited samples. This is akey task in computational science and engineering, e.g., surrogate modelling inuncertainty quantification where the function is the solution map of aparametric or stochastic differential equation (DE). Yet, sparse polynomialapproximation lacks a complete theory. On the one hand, there is awell-developed theory of best $s$-term polynomial approximation, which assertsexponential or algebraic rates of convergence for holomorphic functions. On theother, there are increasingly mature methods such as (weighted)$\ell^1$-minimization for computing such approximations. While the samplecomplexity of these methods has been analyzed with compressed sensing, whetherthey achieve best $s$-term approximation rates is not fully understood.Furthermore, these methods are not algorithms per se, as they involve exactminimizers of nonlinear optimization problems.  This paper closes these gaps. Specifically, we consider the followingquestion: are there robust, efficient algorithms for computing approximationsto finite- or infinite-dimensional, holomorphic and Hilbert-valued functionsfrom limited samples that achieve best $s$-term rates? We answer thisaffirmatively by introducing algorithms and theoretical guarantees that assertexponential or algebraic rates of convergence, along with robustness tosampling, algorithmic, and physical discretization errors. We tackle bothscalar- and Hilbert-valued functions, this being key to parametric orstochastic DEs. Our results involve significant developments of existingtechniques, including a novel restarted primal-dual iteration for solvingweighted $\ell^1$-minimization problems in Hilbert spaces. Our theory issupplemented by numerical experiments demonstrating the efficacy of thesealgorithms.

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