Curse of dimensionality in approximation of random fields

• Autorzy: Lifshits M. A. , Tulyakova V.
• Języki publikacji: EN

Abstrakty

EN

Consider a random field of tensor product-type X(t), t∈[0,1]^d, given by [formula] where (λ(i))_i>0∈l₂(φ_i)_i>0 is an orthonormal system in L₂ [0, 1] and (ξ_k)_k∈Nd are non-correlated random variables with zero mean and unit variance. We investigate the quality of approximation (both in the average and in the probabilistic sense) to X by the n-term partial sums X_n minimizing the quadratic error E‖X‒X_n‖², In the first part of the paper we consider the case of fixed dimension d. In the second part, following the suggestion of H. Woźniakowski, we consider the same problem for d→∞. We show that, for any fixed level of relative error, approximation complexity increases exponentially and we find the ex- plosion coefficient. We also show that the behavior of the probabilistic and average complexity is essentially the same in the large domain of parameters.

Słowa kluczowe

EN

random fields; Gaussian processes; fractional Brownian sheet; linear approximation error; complexity

• Wydawca: Wrocław University of Science and Technology
• Czasopismo: Probability and Mathematical Statistics
• Rocznik: 2006
• Tom: Vol. 26, Fasc. 1
• Strony: 97--112
• Opis fizyczny: Bibliogr. 13 poz.

Twórcy

autor

Lifshits M. A.

• St Petersburg State University, 198504 Stary Peterhof, Department of Mathematics and Mechanics, Bibliotechnaya pl. 2, Russia

autor

Tulyakova V.

• St Petersburg State University, 198504 Stary Peterhof, Department of Mathematics and Mechanics, Bibliotechnaya pl. 2, Russia

Bibliografia

• [1] A. P. Buslaev and О. V. Seleznjev, On certain extremal problems in the theory of approximation of random processes, East J. Approx. 5 (4) (1999), pp. 467-481.
• [2] Yu. A. Davydov, M. A. Lifshits and N. V. Smorodina, Local Properties of Distributions of Stochastic Functionals, Transí. Math. Monogr. 173, Amer. Math. Society, Providence 1998.
• [3] E. Csáki, On small values of the square integral of a multiparameter Wiener process, in: Statistics and Probability. Proceedings of the 3rd Pannonian Symposium on Mathematical Statistics, D. Reidel, Boston 1982, pp. 19-26.
• [4] A. I. Karol’, A. I. Nazarov and Ya. Yu. Nikitin, Tensor products of compact operators and logarithmic L2-small ball asymptotics for Gaussian random fields, Studi Statistici N. 74, Istituto di Metodi Quantitative Universitá ‘L. Bocconi’, Milano 2003, 30 pp.
• [5] Th. Kühn and W. Linde, Optimal series representation of fractional Brownian sheets, Bernoulli 8 (5) (2002), pp. 669-696.
• [6] W. V. Li, Comparison results for the lower tail of Gaussian seminorms, J. Theoret. Probab. 5 (1992), pp. 1-31.
• [7] M. A. Lifshits, Gaussian Random Functions, Kluwer, 1996.
• [8] A. Papageorgiou and G. W. Wasilkowski, On the average complexity of multivariate problems, J. Complexity 6 (1990), pp. 1-23.
• [9] K. Ritter, Average-case Analysis of Numerical Problems, Lecture Notes in Math. No 1733, Springer, Berlin 2000.
• [10] J. F. Traub, G. W. Wasilkowski and H. Woźniakowski, Information-based Complexity, Computer Science and Scientific Computing, Academic Press, Inc., Boston, MA, 1988.
• [11] E. V. Tulyakova, Curse of dimensionality in approximation of Gaussian random fields, Master Thesis, St. Petersburg University, 2005.
• [12] G. W. Wasilkowski and H. Woźniakowski, Weighted tensor-product algorithms for linear multivariate problems, J. Complexity 15 (1999), pp. 1-56.
• [13] H. Woźniakowski, Tractability and strong tractability of linear multivariate problems, J. Complexity 10 (1994), pp. 96-128.