Tractability of Multivariate Problems for Standard and Linear Information in the Worst Case Setting: Part I
It provides a theoretical negative result for the tractability of multivariate problems, showing that the curse of dimensionality can arise from the restriction to function values.
The paper proves that multivariate approximation in the standard Sobolev space suffers the curse of dimensionality when using function values, even though it is tractable with linear functionals. This is achieved by deriving a lower error bound linking linear operators to linear functionals.
We present a lower error bound for approximating linear multivariate operators defined over Hilbert spaces in terms of the error bounds for appropriately constructed linear functionals as long as algorithms use function values. Furthermore, some of these linear functionals have the same norm as the linear operators. We then apply this error bound for linear (unweighted) tensor products. In this way we use negative tractability results known for linear functionals to conclude the same negative results for linear operators. In particular, we prove that $L_2$-multivariate approximation defined for standard Sobolev space suffers the curse of dimensionality if function values are used although the curse is not present if linear functionals are allowed.