Orthogonal projections are optimal algorithms

Abstract

Some results on worst case optimal algorithms and recent results of J. Traub, G. Wasilkowski, and H. Woźniakowski on average case optimal algorithms are unified. By the use of Housholder transformations it is shown that orthogonal projections onto the range of the adjoint of the information operator are, in a very general sense, optimal algorithms. This allows a unified presentation of average case optimal algorithms relative to Gaussian measures on infinite dimensional Hilbert spaces. The choice of optimal information is also discussed. © 1984.