Average case tractability of approximating ∞-variate functions

G. W. Wasilkowski

Research output: Contribution to journalArticlepeer-review

5 Scopus citations


We study function approximation in the average case setting for spaces of ∞-variate functions that have a weighted tensor product form and are endowed with a Gaussian measure that also has a weighted tensor product form. Moreover, we assume that the cost of function evaluation depends on the number of active variables and we allow it to be from linear to exponential. We provide a necessary and sufficient condition for the problem to be polynomially tractable and derive the exact value of the tractability exponent. In particular, the approximation problem is polynomially tractable under modest conditions on weights even if the function evaluation cost is exponential in the number of active variables. The problem is weakly tractable even if this cost is doubly exponential. These results hold for algorithms that can use unrestricted linear information. Similar results hold for weighted L2 approximation, a special case of function approximation problems considered in this paper, and algorithms restricted to those that use only function samplings.

Original languageEnglish
Pages (from-to)1319-1336
Number of pages18
JournalMathematics of Computation
Issue number287
StatePublished - May 2014

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Computational Mathematics
  • Applied Mathematics


Dive into the research topics of 'Average case tractability of approximating ∞-variate functions'. Together they form a unique fingerprint.

Cite this