Optimal sampling recovery of mixed order Sobolev embeddings via discrete Littlewood-Paley type characterizations
For researchers in approximation theory and numerical analysis, this closes gaps in the understanding of optimal sampling recovery for mixed smoothness spaces.
The paper provides sharp upper bounds for the asymptotic order of linear and nonlinear sampling widths for mixed order Sobolev embeddings, showing that in certain regimes linear Smolyak interpolation achieves optimal rates matching Gelfand or linear widths.
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.