Integration and Approximation of Multivariate Functions: Average Case Complexity with Isotropic Wiener Measure

G. W. Wasilkowski

Research output: Contribution to journalArticlepeer-review

14 Scopus citations


We study the average case complexity of multivariate integration and L2 function approximation for the class F = C([0, 1]d) of continuous functions of d variables. The class F is endowed with the isotropic Wiener measure (Brownian motion in Lévy′s sense). For the integration problem, the average case complexity of solving the problem to within ε is proportional to ε(lunate)-2/(1 + 1/d). This is a negative result since for a large number d of variables, the average case complexity is close to ε-2; the latter is also achieved by the classical Monte Carlo method in the randomized worst case setting. Furthermore, Θ(ε-2) is the highest possible average case complexity among all probability measures with finite expectation of ||f2L2. Thus, for large d, the average case complexity of the integration problem with isotropic Wiener measure behaves as the worst possible average complexity. For the function approximation problem, the complexity is even higher since it is proportional to ε-2d. These two negative results are in a sharp contrast to (H. Woźniakowski, Bull. Amer. Math. Soc.24, No. 1 (1991), 185-194; Bull. Amer. Math. Soc., to appear), where, for F endowed with the Wiener sheet measure, small average case complexities have been proven. Indeed, they are of order ε-1(log ε-1)(d-1)/2 and ε(lunate)-2(log ε-1)2(d-1) for the integration and function approximation problems, respectively. cccc.

Original languageEnglish
Pages (from-to)212-227
Number of pages16
JournalJournal of Approximation Theory
Issue number2
StatePublished - May 1994

ASJC Scopus subject areas

  • Analysis
  • Numerical Analysis
  • Mathematics (all)
  • Applied Mathematics


Dive into the research topics of 'Integration and Approximation of Multivariate Functions: Average Case Complexity with Isotropic Wiener Measure'. Together they form a unique fingerprint.

Cite this