On approximation complexity in average case setting for tensor degrees of random processes

Abstract

We consider a random field with a zero mean and a continuous covariance function that is a $d$-tensor degree of a random process of second order. The average case approximation complexity $n_d\(\varepsilon\)$ of a random field is defined as the minimal number of evaluations of linear functionals needed to approximate the field with relative 2-average error not exceeding a given threshold $\varepsilon$. In the present paper we obtain an upper estimate for $n_d\(\varepsilon\)$ that is always valid (without any criteria) for any $\varepsilon$ and $d$. The logarithm of this estimate agrees well with the asymptotics that we obtain for ln $n_d\(\varepsilon\)$ as $d \to \infty$ with a threshold $\varepsilon = \varepsilon_d$, which can be rather quickly convergent to zero at $d \to \infty$. The estimate and the asymptotics complement and generalize the results by Lifshits and Tulyakova, by Kravchenko and Khartov in this direction.

Keywords:

approximation complexity, average case setting, random fields, tensor degree, high dimension, tractability