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.
翻译:带函数值的L2逼近具有指数可解性
翻译摘要:
我们研究了当具有不同类别的信息时,在L2范数下高维逼近的复杂度,我们比较了函数评估的能力与任意连续线性测量的能力。在这里,我们讨论了在线性测量数目不超过多项式对数$\varepsilon^{-1}$时,在维度$d\in\mathbb{N}$的情况下实现误差$\varepsilon\in(0,1)$的情况。这对应于逼近误差的指数级收敛阶,这在应用中经常发生。但是,这并不意味着高维逼近问题很容易,主要的困难通常在于对维度$d$的依赖。我们确定了如果我们只允许函数评估而不是任意线性信息,要求的信息量将发生何种程度的变化。结果表明,在这种情况下,我们只会失去非常少的信息,我们甚至可以限制为线性算法。特别地,多种可解性概念同时适用于两种可用信息。