## Abstract

We study the tractability of ω-weighted ^{Ls} approximation for γ-weighted Banach spaces of ∞-variate functions with mixed partial derivatives of order r bounded in a ψ-weighted ^{Lp} norm. Functions from such spaces have a natural decomposition f=∑_{u} ^{fu}, where the summation is with respect to finite subsets u∩^{N+} and each ^{fu} depends only on variables listed in u. We derive corresponding multivariate decomposition methods and show that they lead to polynomial tractability under suitable assumptions concerning γ weights as well as the probability density functions ω and ψ. For instance, suppose that the cost of evaluating functions with d variables is at most exponential in d and the weights γ decay to zero sufficiently quickly. Then the cost of approximating such functions with the error at most ε is proportional to ε-^{1/(r+min(1/s-1/p,0))} ignoring logarithmic terms. This is a nearly-optimal result, since (once again ignoring logarithmic terms) it equals the complexity of the same approximation problem in the univariate case.

Original language | English |
---|---|

Pages (from-to) | 325-346 |

Number of pages | 22 |

Journal | Journal of Complexity |

Volume | 30 |

Issue number | 3 |

DOIs | |

State | Published - Jun 2014 |

## Keywords

- Function approximation
- Tractability

## ASJC Scopus subject areas

- Algebra and Number Theory
- Statistics and Probability
- Numerical Analysis
- General Mathematics
- Control and Optimization
- Applied Mathematics