Linear vs. nonlinear algorithms for linear problems (Q706787)

The paper deals with comparison of linear and non-linear approximations for linear problems. Given a linear space \(X\) and a normed space \(Y\), let \(S: X \to Y\) and \(N: X \to R^n\) be linear mappings (using the concept of information-based complexity, \(N\) is called information). Let \(F\) be a balanced convex subset of \(X\) with respect to which the linear error err\({}^{\text{lin}}(S,N,F)\) and the non-linear error err\((S,N,F)\) are properly defined. Using extension properties of normed spaces, the authors prove that \[ \inf_N \text{ err}^{\text{lin}}(S,N,F)\leq (1+n^{1/2}) \, \inf_N \text{ err}(S,N,F) \] provided the target space \(Y\) is complete. Related problems are discussed.