H. Woznakowski

Tractability of Tensor Product Linear Operators in Weighted Hilbert Spaces

We study tractability in the worst case setting of tensor product linear operators defined over weighted tensor product Hilbert spaces. Tractability means that the minimal number of evaluations needed to reduce the initial error by a factor of $\e$ in the $d$-dimensional case has a polynomial bound in both $\e^{-1}$ and $d$. By one evaluation we mean the computation of an arbitrary continuous linear functional, and the initial error is the norm of the linear operator~$S_d$ specifying the $d$-dimensional problem. We prove that nontrivial problems are tractable iff the dimension of the image under~$S_1$ (the one-dimensional version of~$S_d$) of the unweighted part of the Hilbert space is one, and the weights of the Hilbert spaces, as well as the singular values of the linear operator $S_1$, go to zero polynomially fast with their indices.