Weak and quasi-polynomial tractability of approximation of infinitely differentiable functions
For researchers in information-based complexity, this work redefines tractability boundaries for infinitely differentiable functions, though the approach is incremental.
The paper shows that by renorming the space of infinitely differentiable functions, weak tractability for uniform approximation using function values is achievable, contrary to previous results indicating intractability. The algorithm uses Taylor expansion at the center of the unit cube.
We comment on recent results in the field of information based complexity, which state (in a number of different settings), that approximation of infinitely differentiable functions is intractable and suffers from the curse of dimensionality. We show that renorming the space of infinitely differentiable functions in a suitable way allows weakly tractable uniform approximation by using only function values. Moreover, the approximating algorithm is based on a simple application of Taylor's expansion at the center of the unit cube. We discuss also the approximation on the Euclidean ball and the approximation in the $L_1$-norm, which is closely related to the problem of numerical integration.