Tractability of linear ill-posed problems in Hilbert space (Q6564671)

This interesting paper deals with tractability of linear ill-posed problems in Hilbert space. Roughly put, in computer science, an algorithm is tractable or not, based on the complexity (estimated number of steps) of the algorithm. Essentially, if the algorithm takes an exponential amount of time or worse for an input of size \(n\), it is labelled as intractable. This rule is rough, but it is used often and provides good guidance.\N\NThe authors introduce a notion of tractability for ill-posed operator equations in Hilbert space. More precisely, they consider a modeling of operator equations of the form \(y=Ax\) where some injective bounded linear operator \(A : X\to Y\) is acting between real infinite dimensional Hilbert spaces \(X\) and \(Y\).\N\NThe authors consider the noise model \(y^{\delta}:=Ax+\delta \eta\) where the unknown noise element \(\eta\) has norm bounded above by one such that \(\|Ax-y^{\delta}\|_{Y}\leq \delta\). For such operator equations the asymptotics of the best possible rate of reconstruction in terms of the underlying noise level is known in many cases.\N\NSee for example [\textit{H. W. Engl} et al., Regularization of inverse problems. Dordrecht: Kluwer Academic Publishers (1996; Zbl 0859.65054)].\N\NHowever, the question is, which level of discretization, driven by the noise level, is required in order to give this best possible accuracy. Several examples given show the relevance of this concept given the curse of dimensionality\N\NThe paper is well written with a good set of references.