Tractability of approximation of ∞-variate functions with bounded mixed partial derivatives

G. W. Wasilkowski

Research output: Contribution to journalArticlepeer-review

17 Scopus citations


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 languageEnglish
Pages (from-to)325-346
Number of pages22
JournalJournal of Complexity
Issue number3
StatePublished - Jun 2014


  • Function approximation
  • Tractability

ASJC Scopus subject areas

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


Dive into the research topics of 'Tractability of approximation of ∞-variate functions with bounded mixed partial derivatives'. Together they form a unique fingerprint.

Cite this