On Tractability of Approximation for a Special Space of Functions

2012/01/23 by Markus Hegland, Hegland, Markus, Wasilkowski, Greg W.
Computer Science · Engineering · Mathematics · #Advanced Mathematical Modeling in Engineering #Advanced Numerical Analysis Techniques #FOS: Mathematics #Mathematical Approximation and Integration #Numerical Analysis (math.NA)

paper · pdf · doi:10.48550/arxiv.1201.4886

openalex publication_date 2012/01/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We consider approximation problems for a special space of d variate functions. We show that the problems have small number of active variables, as it has been postulated in the past using concentration of measure arguments. We also show that, depending on the norm for measuring the error, the problems are strongly polynomially or quasi-polynomially tractable even in the model of computation where functional evaluations have the cost exponential in the number of active variables.

Related

• Weak and quasi-polynomial tractability of approximation of infinitely\n differentiable functions
• On the power of standard information for tractability for L_∞ approximation of periodic functions in the worst case setting
• On the power of standard information for tractability for L₂-approximation in the average case setting
• Breaking the Curse for Uniform Approximation in Hilbert Spaces via Monte Carlo Methods
• Notes on tractability conditions for linear multivariate problems