On the average complexity of multivariate problems

A. Papageorgiou, G. W. Wasilkowski

Research output: Contribution to journalArticlepeer-review

58 Scopus citations


We study the average complexity of linear problems, on a separable Banach space equipped with an orthogonally invariant measure μ. The error and the cost of the algorithms are defined on the average. We exhibit an information operator which is optimal among any linear information operators. We apply the general results to the approximation problem of real functions of d variables. The space is now equipped with a Wiener measure placed on partial derivatives. We show that the average complexity of this problem is almost independent of the dimension d if arbitrary linear functionals are permitted in the information. We conjecture that the same result holds if the information is restricted to function and/or partial derivative evaluations only.

Original languageEnglish
Pages (from-to)1-23
Number of pages23
JournalJournal of Complexity
Issue number1
StatePublished - Mar 1990

Bibliographical note

Funding Information:
* This work was supported in part by the National Science Foundation under Grant CCR-86-03674. t Current address: Dept. of Computer Science, 915 Patterson Office Tower, University of Kentucky, Lexington, KY 40506-0027.

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 'On the average complexity of multivariate problems'. Together they form a unique fingerprint.

Cite this