We use an information-based complexity approach to study the complexity of approximation of linear operators. We assume that the values of a linear operator may be elements of an infinite dimensional space G. It seems reasonable to look for an approximation as a linear combination of some elements g_i's from the space G, and compute only the coefficients c_i's of this linear combination. We study the case when the elements g_i's are fixed and compare it with the case where the g_i's 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 better than all linear algorithms. We also provide an example of a linear problem for which the information complexity is one whereas an optimal (minimal cost) algorithm must use information of much higher cardinality.