Average case tractability of non-homogeneous tensor product problems

We study dd-variate approximation problems in the average case setting with respect to a zero-mean Gaussian measure νdνd. Our interest is focused on measures having the structure of a non-homogeneous tensor product, where the covariance kernel of νdνd is a product of univariate kernels: Kd(s,t)=∏k=1dRk(sk,tk)for s,t∈[0,1]d. We consider the normalized average error of algorithms that use finitely many evaluations of arbitrary linear functionals. The information complexity is defined as the minimal number navg(ε,d) of such evaluations for error in the dd-variate case to be at most εε. The growth of navg(ε,d) as a function of ε−1ε−1 and dd depends on the eigenvalues of the covariance operator of νdνd and determines whether a problem is tractable or not. Four types of tractability are studied and for each of them we find the necessary and sufficient conditions in terms of the eigenvalues of the integral operator with kernel RkRk.We illustrate our results by considering approximation problems related to the product of Korobov kernels RkRk. Each RkRk is characterized by a weight gkgk and a smoothness rkrk. We assume that weights are non-increasing and smoothness parameters are non-decreasing. Furthermore they may be related; for instance gk=g(rk)gk=g(rk) for some non-increasing function gg. In particular, we show that the approximation problem is strongly polynomially tractable, i.e., navg(ε,d)≤Cε−p for all d∈N,ε∈(0,1]d∈N,ε∈(0,1], where CC and pp are independent of εε and dd, iff lim infk→∞ln1gklnk>1. For other types of tractability we also show necessary and sufficient conditions in terms of the sequences gkgk and rkrk.