A unified treatment of tractability for approximation problems defined on Hilbert spaces (Q6564668)

The paper first presents a framework to study the information complexity of numerical problems. The framework assumes that the space of available information consists of all linear functionals, and the problems are defined as linear operator mappings between Hilbert spaces. Specifically, let \(\left\{\mathcal{F}_{d}\right\}_{d\in \mathbb{N}}\) and \(\left\{\mathcal{G}_{d}\right\}_{d\in \mathbb{N}}\) be sequences of Hilbert spaces, and let \(\left\{SOL_{d}:\mathcal{F}_{d}\rightarrow\mathcal{G}_{d}\right\}_{d\in \mathbb{N}}\) be a sequence of linear solution operators. The goal is to find a sequence of approximate solution operators: \N\[\N\left\{\operatorname{APP}_d:\mathcal{B}_d \times (0,\infty) \rightarrow \mathcal{G}_d\right\}_{d\in \mathbb{N}}, \N\]\Ndefined on the unit ball \(\mathcal{B}_{d}\) of \(\mathcal{F}_{d}\), which satisfy an absolute error criterion:\N\[\N\left\|\operatorname{SOL}_d(f) - \operatorname{APP}_d(f,\varepsilon)\right\|_{\mathcal{G}_d} \leq \varepsilon \quad \forall f \in \mathcal{B}_d, \varepsilon \in (0,\infty).\N\]\NThe information complexity of the problem \(SOL_{d}\) is to estimate the number of linear functionals required by the best admissible algorithm to satisfy the error criterion. If the information complexity grows at a modest rate as \(\varepsilon\) decreases to zero, the associated numerical problem in \(SOL_{d}\) is said to be tractable.\N\NUnder the framework, the authors unify the proofs of known tractability results and generalize a number of existing results.