Linearity of algorithms and a result of Ando

Normed linear spaces and Banach spaces; Banach lattices (46B99) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Abstract computational complexity for mathematical programming problems (90C60)

Review text

Let us have a Banach space \(F\) (space of problem elements) with a unit ball \(F_ 0\subset F\) and a linear operator (solution operator) \(S: F\to Z\), \(Z\) being a Banach space. Define a bounded linear opertor \(N: F\to Y\), \(Y\) being a finite dimensional linear space (information operator). An algorithm is defined as a transformation \(\Phi: Y\to Z\), which provides an approximation \(\Phi(y)\) of \(Sf\) using information \(y=Nf\). If \(T(y)=\{f\in F_ 0:\;Nf=y\}\), define the local error of \(\Phi\) as \[ E(\Phi,y)=\sup_{f'\in T(y)}\| Sf'-\Phi(y)\|. \] An algorithm \(\Phi_ 0\) is strongly optimal if \(E(\Phi_ 0,y)=\inf_{\phi} E(\Phi,y)\) for all \(y\in N(F_ 0)\). An algorithm \(\Phi\) is called almost strongly optimal if there exists a \(k\) such that \[ E(\Phi,y)\leq k\cdot E(\Phi_ 0,y)\hbox { for all } y\in N(F_ 0); \] it is called interpolatory if \(\Phi(y)\in S(T*(y))\) for all \(y\in N(F_ 0)\) and it is called spline algorithm if \(\Phi(y)=S\sigma(y)\), where \(\|\sigma(y)\|=\inf_{f'\in T(y)}\| f'\|\). The authors prove the following theorem: Let \(F=L^ p(\mu)\) be a \(L^ p\) space (\(1<p<\infty\)) on some measure space \((M,\mu)\) and let \(N: F\to Y\) be a given linear bounded information operator. Then the following statements are equivalent: 1. \(F/\ker N\) is isomorphic to a \(L^ p\) space. For any bounded linear operator \(S\) there exists 2. a linear interpolatory algorithm, 3. a linear spline algorithm, 4. a linear almost strongly optimal algorithm.

Recommendations

Cites work

Cited in

(10)

This page was built for publication: Linearity of algorithms and a result of Ando

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1179033)