Adaptive algorithms in sampling recovery

We study optimal algorithms in adaptive sampling recovery of smooth functions defined on the unit $d$-cube ${\text{II}}^d:=[0,1{]}^d$. The recovery error is measured in the quasi-norm $\mathrm{\parallel }\cdot {\mathrm{\parallel }}_q$ of $L_q:=L_q({\text{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^\alpha_{p,\theta}$definesa$n$-samplingalgorithm$S_n^B$ by functions in $B$. If $\mathrm{\Phi }=\{{\varphi }_k{\}}_{k\in K}$ is a family of elements in $L_q$, let ${\mathrm{\Sigma }}_n(\mathrm{\Phi })$ be the non-linear set of linear combinations of $n$ free terms from $\mathrm{\Phi },$ that is $\Sigma_n(\Phi):= {, \phi = \sum_{j=1}^n a_j \phi_{k_j}: \ k_j \in K , }$\mathrm{.}Denoteby${\mathcal G}$thesetofallfamilies$\Phi$in$L_q$suchthattheintersectionof$\Phi$ with any finite dimensional subspace in $L_q$ is a finite set, and by $\text{Cc}(B_{p,\theta }^{\alpha },L_q)$ the set of all continuous mappings from $B_{p,\theta }^{\alpha }$ into $L_q$. We define the quantity $${\nu }_n(B_{p,\theta }^{\alpha },L_q):=\underset{\mathrm{\Phi }\in \mathcal{G}}{\inf }\underset{S_n^B\in \text{Cc}(X,L_q):B={\mathrm{\Sigma }}_n(\mathrm{\Phi })}{\inf }\underset{\mathrm{\parallel }f{\mathrm{\parallel }}_{B_{p,\theta }^{\alpha }}\le 1}{\sup }\mathrm{\parallel }f-S_n^B(f){\mathrm{\parallel }}_q\mathrm{.}$$ Let $0 < p,q, \theta \le \infty $and$\alpha > d/p$\mathrm{.}Thenweprovetheasymptoticorder$${\nu }_n(B_{p,\theta }^{\alpha },L_q)\asymp n^{-\alpha \mathrm{/}d}\mathrm{.}$$ 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.