Abstract
We study adaptive information of varying cardinality for linear problems defined on a separable Banach space. It is known that for linear problems adaptive information of fixed cardinality does not help in the worst case setting. It does not help also in the average case setting with Gaussian measures. We prove that in the worst case setting a similar result holds for information of varying cardinality. In the average case setting with Gaussian measures, information of varying cardinality can be more powerful than information of fixed cardinality. However, optimal information has a structure which is almost as simple as nonadaptive information of fixed cardinality. We also give a condition under which varying cardinality does not help. These results are useful for deriving tight bounds on complexity, which is also studied in this paper.
| Original language | English |
|---|---|
| Pages (from-to) | 204-228 |
| Number of pages | 25 |
| Journal | Journal of Complexity |
| Volume | 2 |
| Issue number | 3 |
| DOIs | |
| State | Published - Sep 1986 |
Bibliographical note
Funding Information:*This research was supported in part by the National Science Foundation under Grant DCR-82-14322 and by the Advanced Research Projects Agency under Contract NOOO39-82-C-0427.
ASJC Scopus subject areas
- Algebra and Number Theory
- Statistics and Probability
- Numerical Analysis
- General Mathematics
- Control and Optimization
- Applied Mathematics