On the average complexity of multivariate problems (Q757054)

A linear problem is the approximation of S(f), where S is a continuous linear operation S: \(F_ 1\to F_ 2\). It is typically assumed that \(F_ 2\) is a separable Hilbert space, and either \(F_ 1\) is also a separable Hilbert space or S is of some special form. Known results are extended for the case where \(F_ 1\) is a separable Banach space equipped with a Gaussian or orthogonally invariant measure, and S is an arbitrary continuous linear operator. The results are applied to the approximation of real functions of d variables. In particular, it is shown that the average complexity of this problem is almost independent of the dimension d if arbitrary linear functionals are permitted in the information.