DEPENDENCE ON THE DIMENSION FOR COMPLEXITY OF APPROXIMATION OF RANDOM FIELDS

We consider the epsilon-approximation by n-term partial sums of the Karhunen-Loeve expansion to d-parametric random fields of tensor product-type in the average case setting. We investigate the behavior, as d -> infinity, of the information complexity n(epsilon, d) of approximation with error not exceeding a given level epsilon. It was recently shown by Lifshits and Tulyakova that for this problem one observes the curse of dimensionality (intractability) phenomenon. The aim of this paper is to give the exact asymptotic expression for the information complexity n(epsilon, d).