An Estimate of Average Case Approximation Complexity for Tensor Degrees of Random Processes
Tóm tắt
We consider random fields that are tensor degrees of a random process of second order with a 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 a relative twofold average error not exceeding a given threshold. In the present paper, we estimate the growth of average case approximation complexity of random field for an arbitrarily high parametric dimension and for an arbitrarily small error threshold. Using rather weak assumptions concerning the spectrum of covariance operator of the generating random process, we obtain the necessary and sufficient condition that the average case approximation complexity has an upper estimate of 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 asymptotic representation obtained by Lifshits and Tulyakova earlier.
Tài liệu tham khảo
J. L. Brown, “Mean square truncation error in series expansions of random functions,” J. Soc. Ind. Appl. Math. 8, 28–32 (1960).
K. Ritter, Average-Case Analysis of Numerical Problems (Springer-Verlag, Berlin, 2000), in Ser.: Lecture Notes in Mathematics, Vol. 1733.
G. W. Wasilkowski and H. Woźniakowski, “Average case optimal algorithms in Hilbert spaces,” J. Approximation Theory 47, 17–25 (1986).
I. I. Gikhman and A. V. Skorokhod, The Theory of Stochastic Processes (Nauka, Moscow, 1971), Vol. 1 [in Russian].
E. Novak and H. Woźniakowski, Tractability of Multivariate Problems, Vol. 1: Linear Information (European Mathematical Sosiety, Zűrich, 2008), in Ser.: EMS Tracts in Mathematics, Vol. 6.
M. A. Lifshits and E. V. Tulyakova, “Curse of dimensionality in approximation of random fields,” Probab. Math. Stat. 26, 97–112 (2006).
M. A. Lifshits, A. Papageorgiou, and H. Woźniakowski, “Tractability of multi-parametric Euler and Wiener integrated processes,” Probab. Math. Stat. 32, 131–165 (2012).
A. Karol, A. Nazarov, and Ya. Nikitin, “Small ball probabilities for Gaussian random fields and tensor products of compact operators,” Trans. Am. Math. Soc. 360, 1443–1474 (2008).
S. Corlay and G. Pagés, “Functional quantization-based stratified sampling methods,” Monte Carlo Methods Appl. 21, 1–32 (2015).
A. A. Khartov, “Asymptotic analysis of average case approximation complexity of Hilbert space valued random elements,” J. Complexity 31, 835–866 (2015).