Optimal linear randomized methods for linear operators in Hilbert spaces

AbstractBasic questions of information-based complexity are strongly related to n-widths and s-numbers. In this paper we study Monte Carlo methods or randomized methods for linear operators. Similar as in the worst case, Mathé defined linear stochastic n-widths. Our main result is the characterization of these widths in the case of linear operators in Hilbert spaces