Sparse representation of multivariate functions based on discrete point evaluations

Abstract

Functions provide one of the most important building blocks for model descriptions of reality. Central point of this thesis is the approximation of multivariate functions using Faber-Schauder hat functions. In the first part we describe mixed smoothness Sobolev-Besov-Triebel-Lizorkin spaces by decreasing properties of Faber-Schauder coefficients. This allows us to provide equivalent norm representations based on discrete function values. In the second part we apply this theory to study sparse grid sampling or more generally the problem of sampling recovery for Sobolev classes (especially with integrability $pneq 2$). We provide new convergence estimates for a Faber-Schauder based sparse grid method measuring errors in $L_{q}([0,1]^d)$ with $p<q$. This method turns out to be optimal in certain situations. In the third part best $m$-term approximation with respect to hat functions is considered. A special parameter range for smoothness appears, the so called small smoothness regime. Here we provide an optimal constructive method that is able to generate, based on the knowledge of finitely many functions values, a m-term having a purely polynomial $L_{infty}([0,1]^d)$ approximation rate in $m$. Finally in the last part we switch to the periodic setting and overcome regularity restrictions of hat functions by introducing a new scale of fast decreasing sampling kernels.