On the average complexity of multivariate problems
Anargyros Papageorgiou, G.W. Wasilkowski · Journal of Complexity · 1990
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.