Linear problems (with extended range) have linear optimal algorithms
Let \(F_ 1\) and \(F_ 2\) be normed linear spaces and \(S: F_ 0\to F_ 2\) a linear operator on a balanced subset \(F_ 0\) of \(F_ 1\). If N denotes a finite dimensional linear information operator on \(F_ 0\), it is known that there need not be a linear algorithm \(\phi\) : N(F\({}_ 4)\to F_ 2\) which is optimal in the sense that \(\| \phi (N(f))- S(f)\|\) is minimized. We show that the linear problem defined by S and N can be regarded as having a linear optimal algorithm if we allow the range of \(\phi\) to be extended in a natural way. The result depends upon imbedding \(F_ 2\) isometrically in the space of continuous functions on a compact Hausdorff space X. This is done by making use of a consequence of the classical Banach-Alaoglu theorem.
- Are linear algorithms always good for linear problems?
- On the existence of optimal affine methods for approximating linear functionals
- Linearity of algorithms and a result of Ando
- On linearity of spline algorithms
- Recent developments in information-based complexity
- Homogeneous algorithms and solvable problems on cones
- Linear vs. nonlinear algorithms for linear problems
- s-numbers in information-based complexity
This page was built for publication: Linear problems (with extended range) have linear optimal algorithms
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1099022)