An Information-Based Approach to III-Posed Problems

A problem is said to be ill-posed if the solution of the problem does not depend continuously on the input data. In this survey paper, we consider two different information-based settings for the optimal computation of approximate solution of ill-posed linear problems, namely the worst case and average case settings. These settings are studied for two different error criteria, namely, the absolute error and the residual error criteria. The main result for the absolute-error criterion is that algorithms having finite error exist for a given setting if and only if the solution operator is bounded in that setting. In the worst case setting with an absolute error criterion, this means that there is no algorithm for solving ill-posed problems having finite error. In the average case setting with an absolute error criterion, this means that algorithms having finite error exist if and only if the solution operator is "bounded on the average." Furthermore, when this holds, we exhibit optimal information of cardinality n, finding that the nth minimal average error goes to zero as n → ∞. The main result for the residual error criterion is that the problem may be formally reduced to the approximation problem. Hence, finite-error algorithms always exist. We exhibit optimal information of cardinality n. In the worst case setting, we give a necessary and sufficient condition for the nth minimal error to go to zero as n → ∞; in the average case setting, this always occurs. We use these results to determine the ε-complexity of ill-posed problems. The ε-complexity is infinite for anyε > 0 in the worst case setting with the absolute criterion. However, in the average case setting with either error criterion and the worst case setting with the residual error criterion, we determine necessary and sufficient conditions for the ε-complexity to be finite for all ε > 0; moreover, we find algorithms yielding ε-approximations with almost-minimal cost