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

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\leq p<q<\infty$ and $r>1/p$ the linear sampling widths $\varrho_n^{\text{lin}}(S^r_pW(\mathbb{T}^d),L_q(\mathbb{T}^d))$ and $\varrho^{\text{lin}}_n(S^r_{p,\infty}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 \leq 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.