Optimal sampling recovery of mixed order Sobolev embeddings via discrete Littlewood-Paley type characterizations

Abstract

In this paper we consider the $L_q$-approximation of multivariate periodic functions $f$ with $L_p$-bounded mixed derivative (difference). The (possibly non-linear) reconstruction algorithm is supposed to recover the function from function values, sampled on a discrete set of $n$ sampling nodes. The general performance is measured in terms of (non-)linear sampling widths ${\varrho }_n$. We conduct a systematic analysis of Smolyak type interpolation algorithms in the framework of Besov-Lizorkin-Triebel spaces of dominating mixed smoothness based on specifically tailored discrete Littlewood-Paley type characterizations. As a consequence, we provide sharp upper bounds for the asymptotic order of the (non-)linear sampling widths in various situations and close some gaps in the existing literature. For example, in case $2\le p<q<\infty$ and $r>1/p$ the linear sampling widths ${\varrho }_n^{\text{lin}}(S_p^{r}W({\mathbb{T}}^d),L_q({\mathbb{T}}^d))$ and ${\varrho }_n^{\text{lin}}(S_{p,\infty }^{r}B({\mathbb{T}}^d),L_q({\mathbb{T}}^d))$ show the asymptotic behavior of the corresponding Gelfand $n$-widths, whereas in case $1<p<q\le 2$ and $r>1/p$ the linear sampling widths match the corresponding linear widths. In the mentioned cases linear Smolyak interpolation based on univariate classical trigonometric interpolation turns out to be optimal.