Adaptive algorithms in sampling recovery

Abstract

We study optimal algorithms in adaptive sampling recovery of smooth functions defined on the unit $d$-cube ${\II}^d:= [0,1]^d$. The recovery error is measured in the quasi-norm $\Vert \cdot {\Vert }_q$ of $L_q := L_q(\II^d)$. For $B$ a subset in $L_q,$ we define a sampling algorithm of recovery with the free choice of sample points and recovering functions from $B$ as follows. For each $f$ from the quasi-normed Besov space $B_{p,\theta }^{\alpha }$, we choose $n$ sample points. This choice defines $n$ sampled values. Based on these sample points and sampled values, we choose a function from $B$ for recovering $f$. The choice of $n$ sample points and a recovering function from $B$ for each $f\in B_{p,\theta }^{\alpha }$ defines a $n$-sampling algorithm $S_n^B$ by functions in $B$. If $\Phi =\{{\varphi }_k{\}}_{k\in K}$ is a family of elements in $L_q$, let ${\Sigma }_n(\Phi )$ be the non-linear set of linear combinations of $n$ free terms from $\Phi ,$ that is ${\Sigma }_n(\Phi ):=\{\varphi ={\sum }_{j=1}^n{a}_j{\varphi }_{k_j}:k_j\in K\}$. Denote by $\mathcal{G}$ the set of all families $\Phi$ in $L_q$ such that the intersection of $\Phi$ with any finite dimensional subspace in $L_q$ is a finite set, and by $\Cc(B^α_{p,θ}, L_q)$ the set of all continuous mappings from $B_{p,\theta }^{\alpha }$ into $L_q$. We define the quantity $$ν_n(B^α_{p,θ},L_q) := \inf_{Φ\in {\mathcal G}} \inf_{S_n^B \in \Cc(X, L_q): B= Σ_n(Φ)} \sup_{\|f\|_{B^α_{p,θ}} \le 1} \ \|f - S_n^B(f)\|_q.$$ Let $0<p,q,\theta \le \infty$ and $\alpha >d/p$. Then we prove the asymptotic order $${\nu }_n(B_{p,\theta }^{\alpha },L_q)\asymp n^{-\alpha /d}.$$ We also obtained the asymptotic order of quantities of optimal recovery by $S_n^B$ in terms of best $n$-term approximation as well of other non-linear $n$-widths.