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