Exponential tractability of linear weighted tensor product problems in the worst-case setting for arbitrary linear functionals

Peter Kritzer, Friedrich Pillichshammer, Henryk Woźniakowski

Published 2020-01-31Version 1

We study the approximation of compact linear operators defined over certain weighted tensor product Hilbert spaces. The information complexity is defined as the minimal number of arbitrary linear functionals which is needed to obtain an $\varepsilon$-approximation for the $d$-variate problem. It is fully determined in terms of the weights and univariate singular values. Exponential tractability means that the information complexity is bounded by a certain function which depends polynomially on $d$ and logarithmically on $\varepsilon^{-1}$. The corresponding un-weighted problem was studied recently by Hickernell, Kritzer and Wo\'{z}niakowski with many negative results for exponential tractability. The product weights studied in the present paper change the situation. Depending on the form of polynomial dependence on $d$ and logarithmic dependence on $\varepsilon^{-1}$, we study exponential strong polynomial, exponential polynomial, exponential quasi-polynomial, and exponential $(s,t)$-weak tractability with $\max(s,t)\ge1$. For all these notions of exponential tractability, we establish necessary and sufficient conditions on weights and univariate singular values for which it is indeed possible to achieve the corresponding notion of exponential tractability. The case of exponential $(s,t)$-weak tractability with $\max(s,t)<1$ is left for future study.