Average case tractability of non-homogeneous tensor product problems (Q454823)

The authors consider nonhomogeneous linear multivariate tensor product problems in the average case with the normalized error criterion, i.e., they measure the error of an algorithm to the error of the zero algorithm. In the introduction, the authors say that the study of the nonhomogeneous case is necessary since homogeneous linear multivariate tensor product problems are intractable with this error criterion. The authors define four types of tractability: weak tractability, quasi-polynomial tractability, polynomial tractability and strong polynomial tractability. They recall spectral conditions for these types of tractability and prove some new conditions. They show and prove bounds of the average case information complexity and give sufficient conditions for each type of tractability. The conditions are given in terms of the eigenvalues of the covariance operator of the corresponding Gaussian measure. The authors apply these conditions to nonhomogeneous tensor product approximation problems. The results are illustrated on the multivariate approximation problem defined over the space of continuous real functions equipped with a zero-mean Gaussian measure whose covariance is given as Korobov kernel.