On the average complexity of multivariate problems

✍ Scribed by A Papageorgiou; G.W Wasilkowski

• Publisher: Elsevier Science
• Year: 1990
• Tongue: English
• Weight: 904 KB
• Volume: 6
• Category: Article
• ISSN: 0885-064X
• DOI: 10.1016/0885-064x(90)90009-3

✦ Synopsis

We study the average complexity of linear problems, on a separable Banach space equipped with an orthogonally invariant measure CL. 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. 0 1990 Academic press, hc.