Weak and quasi-polynomial tractability of approximation of infinitely\n differentiable functions

2013/01/21 by Jan Vybíral, Vybiral, Jan
Mathematics · #Mathematical Approximation and Integration

paper · pdf · doi:10.48550/arxiv.1301.4794

Abstract

We comment on recent results in the field of information based complexity,\nwhich state (in a number of different settings), that approximation of\ninfinitely differentiable functions is intractable and suffers from the curse\nof dimensionality. We show that renorming the space of infinitely\ndifferentiable functions in a suitable way allows weakly tractable uniform\napproximation by using only function values. Moreover, the approximating\nalgorithm is based on a simple application of Taylor's expansion at the center\nof the unit cube. We discuss also the approximation on the Euclidean ball and\nthe approximation in the L₁-norm, which is closely related to the problem of\nnumerical integration.\n

Related

• On Tractability of Approximation for a Special Space of Functions
• Best Polynomial Approximation on the Unit Sphere and the Unit Ball
• Polynomial approximation avoiding values in sets II
• High-Dimensional Function Approximation: Breaking the Curse with Monte Carlo Methods
• Notes on (s,t)-weak tractability: A refined classification of problems\n with (sub)exponential information complexity