id: 06092442
dt: j
an: 06092442
au: Lifshits, M.A.; Papageorgiou, A.; Woźniakowski, H.
ti: Average case tractability of non-homogeneous tensor product problems.
so: J. Complexity 28, No. 5-6, 539-561 (2012).
py: 2012
pu: Elsevier Science (Academic Press), San Diego, CA
la: EN
cc: 
ut: tractability; multivariate problems
ci: 
li: doi:10.1016/j.jco.2012.05.003
ab: Summary: We study $d$-variate approximation problems in the average case
    setting with respect to a zero-mean Gaussian measure $ν_{d}$. Our
    interest is focused on measures having the structure of a
    non-homogeneous tensor product, where the covariance kernel of $ν_{d}$
    is a product of univariate kernels: $$ K_d(s,t)=\prod^d_{k=1}\Cal
    R_k(s_k,t_k) \quad \text {for} s, t \in [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 $n^{\text{avg}}(ε, d)$ of such
    evaluations for error in the $d$-variate case to be at most $ε$. The
    growth of $n^{\text{avg}}(ε,d)$ as a function of $ε^{-1}$ and $d$
    depends on the eigenvalues of the covariance operator of $ν_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 $\Cal R_k$. We illustrate our results by
    considering approximation problems related to the product of Korobov
    kernels $\Cal R_k$. Each $\Cal R_k$ is characterized by a weight $g_k$
    and a smoothness $r_k$. We assume that weights are non-increasing and
    smoothness parameters are non-decreasing. Furthermore they may be
    related; for instance $g_k=g(r_k)$ for some non-increasing function
    $g$. In particular, we show that the approximation problem is strongly
    polynomially tractable, i.e., $n^{\text{avg}}(ε, d) \leq C ε^{-p}$
    for all $d\in \Bbb N, ε\in (0,1]$, where $C$ and $p$ are independent
    of $ε$ and $d$, iff $$ \liminf_{k\rightarrow \infty}\frac
    {\text{ln}\frac{1}{g_k}}{\text {ln}\, k}>1.$$ For other types of
    tractability we also show necessary and sufficient conditions in terms
    of the sequences $g_k$ and $r_k$.
rv: