Tractability of multi-parametric Euler and Wiener integrated processes

• Autorzy: Lifshits M. A. , Papageorgiou A. , Woźniakowski H.
• Języki publikacji: EN

Abstrakty

EN

We study average case approximation of Euler and Wiener integrated processes of d variables which are almost surely r_k-times continuously differentiable with respect to the k-th variable and 0 ≤ r_k ≤ r_k+1. Let n(ε; d) denote the minimal number of continuous linear functionals which is needed to find an algorithm that uses n such functionals and whose average case error improves the average case error of the zero algorithm by a factor ε. Strong polynomial tractability means that there are nonnegative numbers C and p such that [formula]. We prove that the Wiener process is much more difficult to approximate than the Euler process. Namely, strong polynomial tractability holds for the Euler case iff ...[formula]. Other types of tractability are also studied.

Słowa kluczowe

EN

tractability; Wiener process; Euler process; integrated processes; linear approximation

• Wydawca: Wrocław University of Science and Technology
• Czasopismo: Probability and Mathematical Statistics
• Rocznik: 2012
• Tom: Vol. 32, Fasc. 1
• Strony: 131--165
• Opis fizyczny: Bibliogr. 15 poz.

Twórcy

autor

Lifshits M. A.

• Department of Mathematics and Mechanics, St. Petersburg State University, 198504 St. Petersburg, Russia

autor

Papageorgiou A.

• Department of Computer Science, Columbia University, New York, NY 10027, USA

autor

Woźniakowski H.

• Department of Computer Science, Columbia University, New York, NY 10027, USA
• Institute of Applied Mathematics and Mechanics, University of Warsaw, ul. Banacha 2, 02-097 Warszawa, Poland

Bibliografia

• [1] C.-H. Chang and C.-W. Ha, The Green’s functions of some boundary value problems via Bernoulli and Euler polynomials, Arch. Math. (Basel) 76 (2001) pp. 360-365.
• [2] D. E. Edmunds and H. Triebel, Function Spaces, Entropy Numbers and Differential Operators, Cambridge University Press, Cambridge 1996.
• [3] F. Gao, J. Hanning and F. Torcaso, Integrated Brownian motions and exact L2-small balls, Ann. Probab. 31 (2003), pp. 1320-1337.
• [4] M. Gnewuch and H. Woźniakowski, Quasi-polynomial tractability, J. Complexity 27 (2011), pp. 312-330.
• [5] F. J. Hickernell, G. W. Wasilkowski and H. Woźniakowski, Tractability of linear multivariate problems in the average case setting, in: Monte Carlo and Quasi-Monte Carlo Methods 2006, A. Keller, S. Heinrich and H. Niederreiter (Eds.), Springer, Berlin 2008, pp. 461-494.
• [6] M. A. Lifshits, Gaussian Random Functions, Kluwer, Dordrecht 1996.
• [7] M. A. Lifshits, A. Papageorgiou and H. Woźniakowski, Average case tractability of non-homogeneous tensor products problems, J. Complexity (to appear). Preprint www.arxiv.org/abs/1112.4251.
• [8] A. I. Nazarov, On the sharp constant in the small ball asymptotics of some Gaussian processes under L2-norm, J. Math. Sci. 117 (2003), pp. 4185-4210.
• [9] A. I. Nazarov and Ya. Yu. Nikitin, Exact L2-small ball behavior of integrated Gaussian processes and spectral asymptotics of boundary value problems, Probab. Theory Related Fields 129 (2004), pp. 469-494.
• [10] E. Novak and H. Woźniakowski, Tractability of Multivariate Problems, Volume I: Linear Information, European Mathematical Society, Zürich 2008.
• [11] E. Novak and H. Woźniakowski, Tractability of Multivariate Problems, Volume II: Standard Information for Functionals, European Mathematical Society, Zürich 2010.
• [12] E. Novak and H. Woźniakowski, Tractability of Multivariate Problems, Volume III: Standard Information for Operators, European Mathematical Society, Zürich (to appear).
• [13] A. Papageorgiou and H. Woźniakowski, Tractability through increasing smoothness, J. Complexity 20 (2010), pp. 409-421.
• [14] A. Pietsch, Eigenvalues and s-Numbers, Cambridge University Press, Cambridge 1987.
• [15] J. F. Traub, G. W. Wasilkowski and H. Woźniakowski, Information-Based Complexity, Academic Press, New York 1988.