Tractability through increasing smoothness (Q708309)

It is proved that some multivariate linear tensor product problems are tractable in the worst case setting if they are defined as tensor products of univariate problems with logarithmically increasing smoothness. Tractability of linear multivariate problems that are defined for the \(d\)-variate case by the tensor product of \(d\) copies of a single univariate problem has been studied in previous works (see, for example, [\textit{E. Novak} and \textit{H. Wozniakovski}, Tractability of multivariate problems. Volume I: Linear information. EMS Tracts in Mathematics 6. Zürich: European Mathematical Society (EMS). (2008; Zbl 1156.65001)]). Assuming that this univariate problem is not a linear functional, it is known that polynomial tractability does not hold, no matter how smooth the univariate problem is, whereas weak tractability holds under weak assumptions on the smoothness of the univariate problem. The aim of the present paper is to verify whether we can regain polynomial tractability for linear multivariate problems that are tensor products of different univariate problems with increasing smoothness. The examples of such problems are the approximation problem defined over Korobov spaces and the approximation problem for certain diagonal operators. For these two problems necessary and sufficient conditions on the smoothness parameters of the univariate problems to obtain strong polynomial tractability are derived; note that weak tractability always holds for these problems. Under a mild assumption, the Korobov space consists of periodic functions. Periodicity is crucial since the approximation problem defined over Sobolev spaces with a special choice of the norm is not polynomially tractable for all smoothness parameters no matter how fast they go to infinity. Furthermore, depending of the choice of the norm we can even loose weak tractability.