Abstract
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 language | English |
|---|---|
| Pages (from-to) | 1-23 |
| Number of pages | 23 |
| Journal | Journal of Complexity |
| Volume | 6 |
| Issue number | 1 |
| DOIs | |
| State | Published - 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