Complexity of linear problems with a fixed output basis

We use an information-based complexity approach to study the complexity of approximation of linear operators. We assume that the values of a linear op erator may be elements of an infinite dimensional space G. It seems reasona ble to look for an approximation as a linear combination of some elements g (i) from the space G and compute only the coefficients c(i) of this linear combination. We study thr case when the elements g(i) are fixed and compare it with the case where the gi can be chosen arbitrarily. We show examples of linear problems where a significant output data compression is possible by the use of a nonlinear algorithm, and this nonlinear algorithm is much b etter than all linear algorithms. We also provide an example of a linear pr oblem for which one piece of information is enough whereas an optimal (mini mal cost) algorithm must use information of much higher cardinality. (C) 20 00 Academic Press