On Approximation Complexity in Average Case Setting for Tensor Degrees of Random Processes

We consider a random field with a zero mean and a continuous covariance function that is a d-tensor degree of a second-order random process. The average case approximation complexity $${{{\mathbf{n}}}_{d}}(\varepsilon )$$ of a given random field is defined as the minimal number of evaluations of linear functionals needed to approximate the field with a relative r.m.s. error not exceeding a given threshold ε. This paper gives an upper estimate for $${{{\mathbf{n}}}_{d}}(\varepsilon )$$ that is always valid (without any criteria) for any ε and d. The logarithm of this estimate is in well agreement with the asymptotics obtained by us $${{{\mathbf{n}}}_{d}}(\varepsilon )$$ as d → ∞ with a threshold ε = εd, which can rather quickly converge to zero as d → ∞. The estimate and the asymptotics complement and generalize the results obtained by Lifshits and Tulyakova as well as by Kravchenko and Khartov in this direction.