A Characterization of Spaces Admitting Linear Algorithms

In systems and control it is important to know under what conditions a class of algorithms is linear, since linearity is a key property for problems requiring fast computations. In this paper we prove that for the purpose of function estimation, and more generally of approximation in normed spaces, a Hilbert structure for the class of functions being approximated is necessary as well as sufficient for linearity of the following classes of approximation algorithms: spline, interpolatory, strongly optimal, and almost strongly optimal. This provides a converse to the well-known result that a Hilbert structure is sufficient for such linearity properties.