An estimate of average case approximation complexity for tensor degrees of random processes
DOI:
https://doi.org/10.21638/spbu01.2021.403Abstract
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
Downloads
Download data is not yet available.
References
Литература
1. Brown J.L. Mean square truncation error in series expansions of random functions. J. Soc. Indust. Appl. Math. 8 (1), 28–32 (1960).
2. Ritter K. Average-case Analysis of Numerical Problems. In Ser.: Lecture Notes in Math., no. 1733. Berlin, Springer (2000).
3. Wasilkowski G.W., Wo´zniakowski H. Average case optimal algorithms in Hilbert spaces. J. Approx. Theory 47, 17–25 (1986).
4. Гихман И.И., Скороход А.В. Теория случайных процессов. Т. 1. Москва, Наука (1971).
5. Novak E., Wo´zniakowski H. Tractability of Multivariate Problems. Vol. 1: Linear Information. In Ser.: EMS Tracts. Math., vol. 6. Z˝urich, EMS (2008).
6. Lifshits M.A., Tulyakova E.V. Curse of dimensionality in approximation of random fields. Probab. Math. Stat. 26 (1), 97–112 (2006).
7. Lifshits M.A., Papageorgiou A., Wo´zniakowski H. Tractability of multi-parametric Euler and Wiener integrated processes. Probab. Math. Stat. 32 (1), 131–165 (2012).
8. Karol A., Nazarov A., Nikitin Ya. Small ball probabilities for Gaussian random fields and tensor products of compact operators. Trans. Amer. Math. Soc. 360 (3), 1443–1474 (2008).
9. Corlay S., Pag´es G. Functional quantization-based stratified sampling methods. Monte Carlo Methods Appl. 21 (1), 1–32 (2015).
10. Khartov A.A. Asymptotic analysis of average case approximation complexity of Hilbert space valued random elements. J. Complexity 31, 835–866 (2015).
References
1. Brown J.L. Mean square truncation error in series expansions of random functions. J. Soc. Indust. Appl. Math. 8 (1), 28–32 (1960).
2. Ritter K. Average-case Analysis of Numerical Problems. In Ser.: Lecture Notes in Math., no. 1733. Berlin, Springer (2000).
3. Wasilkowski G.W., Wo´zniakowski H. Average case optimal algorithms in Hilbert spaces. J. Approx. Theory 47, 17–25 (1986).
4. Gikhman I.I., Skorokhod A.V. The Theory of Stochastic Processes. Vol. 1. Moscow, Nauka Publ. (1971). (In Russian)
5. Novak E., Wo´zniakowski H. Tractability of Multivariate Problems. Vol. 1: Linear Information. In Ser.: EMS Tracts. Math., vol. 6. Z˝urich, EMS (2008).
6. Lifshits M.A., Tulyakova E.V. Curse of dimensionality in approximation of random fields. Probab. Math. Stat. 26 (1), 97–112 (2006).
7. Lifshits M.A., Papageorgiou A., Wo´zniakowski H. Tractability of multi-parametric Euler and Wiener integrated processes. Probab. Math. Stat. 32 (1), 131–165 (2012).
8. Karol A., Nazarov A., Nikitin Ya. Small ball probabilities for Gaussian random fields and tensor products of compact operators. Trans. Amer. Math. Soc. 360 (3), 1443–1474 (2008).
9. Corlay S., Pag´es G. Functional quantization-based stratified sampling methods. Monte Carlo Methods Appl. 21 (1), 1–32 (2015).
10. Khartov A.A. Asymptotic analysis of average case approximation complexity of Hilbert space valued random elements. J. Complexity 31, 835–866 (2015).
Downloads
Published
2022-01-04
How to Cite
Kravchenko А. А., & Khartov, A. A. (2022). An estimate of average case approximation complexity for tensor degrees of random processes. Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy, 8(4), 580–592. https://doi.org/10.21638/spbu01.2021.403
Issue
Section
Mathematics
License
Articles of "Vestnik of Saint Petersburg University. Mathematics. Mechanics. Astronomy" are open access distributed under the terms of the License Agreement with Saint Petersburg State University, which permits to the authors unrestricted distribution and self-archiving free of charge.
