FoCM 2014 conference

Workshop B5 - Information Based Complexity

December 16, 17:00 ~ 17:30 - Room B23

Preasymptotic estimates for approximation of multivariate Sobolev functions

Thomas Kühn

Universität Leipzig, Germany   -

The talk is concerned with optimal linear approximation of functions in isotropic periodic Sobolev spaces $H^s(\mathbb{T}^d)$ of fractional smoothness $s>0$ on the $d$-dimensional torus, where the error is measured in the $L_2$-norm. The asymptotic rate -- up to multiplicative constants -- of the approximation numbers is well known. For any fixed dimension $d\in\mathbb{N}$ and smoothness $s>0$ one has $$ (\star)\qquad a_n(I_d: H^s(\mathbb{T}^d)\to L_2(\mathbb{T}^d))\sim n^{-s/d}\qquad\text{as}\quad n\to \infty\,. $$ In the language of IBC, the n-th approximation number $a_n(I_d)$ is nothing but the worst-case error of linear algorithms that use at most $n$ arbitrary linear informations. Clearly, for numerical issues and questions of tractability one needs precise information on the constants that are hidden in $(\star)$, in particular their dependence on $d$.

For any fixed smoothness $s>0$, the exact asymptotic behavior of the constants as $d\to\infty$ will be given in the talk. Moreover, I will present sharp two-sided estimates in the preasymptotic range, that means for `small' $n$. Hereby an interesting connection to entropy numbers in finite-dimensional $\ell_p$-spaces turns out to be very useful.

Joint work with Sebastian Mayer (Bonn), Winfried Sickel (Jena) and Tino Ullrich (Bonn).

View abstract PDF