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

DOI10.1016/j.jco.2013.04.003zbMath1308.46034arXiv1301.4794OpenAlexW2081394544MaRDI QIDQ2442807

Jan Vybíral

Publication date: 1 April 2014

Published in: Journal of Complexity (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1301.4794

zbMATH Keywords

uniform approximationcurse of dimensionalityinfinitely differentiable functionsweak tractabilityinformation based complexity

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Banach spaces of continuous, differentiable or analytic functions (46E15) Complexity and performance of numerical algorithms (65Y20) Numerical approximation and computational geometry (primarily algorithms) (65D99)

Related Items (14)

A note on optimal Hermite interpolation in Sobolev spaces ⋮ Uniform recovery of high-dimensional \(C^r\)-functions ⋮ Approximation in periodic Gevrey spaces ⋮ Some Results on the Complexity of Numerical Integration ⋮ Approximation numbers of Sobolev embeddings-sharp constants and tractability ⋮ The curse of dimensionality for numerical integration of smooth functions. II ⋮ On weak tractability of the Clenshaw-Curtis Smolyak algorithm ⋮ The difficulty of Monte Carlo approximation of multivariate monotone functions ⋮ Algorithms and complexity for functions on general domains ⋮ On weak tractability of the Smolyak algorithm for approximation problems ⋮ Unnamed Item ⋮ Entropy and sampling numbers of classes of ridge functions ⋮ EC-tractability of approximation problems in function spaces defined over products of simplices ⋮ Recovery of regular ridge functions on the ball

Cites Work

• Quasi-polynomial tractability
• Tractability results for weighted Banach spaces of smooth functions
• Optimal order of convergence and (in)tractability of multivariate approximation of smooth functions
• Function spaces in Lipschitz domains and optimal rates of convergence for sampling
• Approximation of infinitely differentiable multivariate functions is not strongly tractable
• Tractability of multivariate problems. Volume I: Linear information
• Widths of embeddings in function spaces
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• Deterministic and stochastic error bounds in numerical analysis
• Open problems for tractability of multivariate integration.
• Multivariate integration in \(C^{\infty}([0,1^{d})\) is not strongly tractable.]
• Approximation of infinitely differentiable multivariate functions is intractable
• Sampling numbers and function spaces
• The curse of dimensionality for numerical integration of smooth functions
• The best accuracy of reconstruction of finitely smooth functions from their values at a given number of points
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Weak and quasi-polynomial tractability of approximation of infinitely differentiable functions