Abstract:
We consider random fields that are tensor degrees of a random process of second order with continuous covariance function. The average case approximation complexity 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. In the present paper we estimate the growth of average case approximation complexity of random field for arbitrary high its parametric dimension and for arbitrary small error threshold. Under rather weak assumptions on the spectrum of covariance operator of the generating random process, we obtain necessary and sufficient condition that the average case approximation complexity has the upper estimate of a special form. We show that this condition covers a wide class of cases and the order of the estimate of the average case approximation complexity coincides with the order of its asymptotics, which were obtained earlier in the paper by Lifshits and Tulyakova.
Keywords:average case approximation complexity, random field, tensor degree, high dimension, tractability.
Fulltext:
PDF file (311 kB)