Exponential tractability of $L_2$-approximation with function values

Abstract

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 $\epsilon \in (0,1)$ in dimension $d\in \mathbb{N}$ depends only poly-logarithmically on ${\epsilon }^{-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.

References in corpus (9)

• Rate of Convergence and Tractability of the Radial Function Approximation Problem
• A sharp upper bound for sampling numbers in $L_2$
• Nonlinear Approximation Using Gaussian Kernels
• The curse of dimensionality for numerical integration on general domains
• Random sections of ellipsoids and the power of random information
• The Curse of Dimensionality for Numerical Integration of Smooth Functions
• On the worst-case error of least squares algorithms for $L_2$-approximation with high probability
• On Weak Tractability of the Clenshaw-Curtis Smolyak Algorithm
• Product rules are optimal for numerical integration in classical smoothness spaces

Cited by in corpus (5)

• On the power of iid information for linear approximation
• Sampling projections in the uniform norm
• On the power of adaption and randomization
• Sampling recovery in $L_2$ and other norms
• Approximation of Functions: Optimal Sampling and Complexity