论文标题
$ l_2 $ - approximation带有功能值的指数障碍性
Exponential tractability of $L_2$-approximation with function values
论文作者
论文摘要
当有不同类别的信息可用时，我们研究$ L_2 $ norm中高维近似的复杂性；我们将功能评估的力量与任意连续线性测量的力量进行比较。在这里，我们讨论了实现错误$ \ varepsilon \ in（0,1）$ in dimension $ d \ in \ mathbb {n} $中的（0,1）$所需的线性测量数量的情况。这对应于近似误差的收敛指数顺序，该近似误差通常发生在应用程序中。但是，这并不意味着高维近似问题很容易，主要难度通常在于对尺寸$ d $的依赖性。如果我们仅允许函数评估而不是任意线性信息，我们确定所需的信息更改的程度。事实证明，在这种情况下，我们只损失很少，甚至可以限于线性算法。特别是，对于两种可用的信息，同时存在几种障碍性概念。
We study the complexity of high-dimensional approximation in the $L_2$-norm when different classes of information are available; we compare the power of function evaluations with the power of arbitrary continuous linear measurements. Here, we discuss the situation when the number of linear measurements required to achieve an error $\varepsilon \in (0,1)$ in dimension $d\in\mathbb{N}$ depends only poly-logarithmically on $\varepsilon^{-1}$. This corresponds to an exponential order of convergence of the approximation error, which often happens in applications. However, it does not mean that the high-dimensional approximation problem is easy, the main difficulty usually lies within the dependence on the dimension $d$. We determine to which extent the required amount of information changes, if we allow only function evaluation instead of arbitrary linear information. It turns out that in this case we only lose very little, and we can even restrict to linear algorithms. In particular, several notions of tractability hold simultaneously for both types of available information.
