zbMATH — the first resource for mathematics

Asymptotic analysis of average case approximation complexity of Hilbert space valued random elements. (English) Zbl 1333.60108
Summary: We study approximation properties of sequences of centered random elements \(X_d\), \(d \in \mathbb{N}\), with values in separable Hilbert spaces. We focus on sequences of tensor product-type and, in particular, degree-type random elements, which have covariance operators of a corresponding tensor form. The average case approximation complexity \(n^{X_d}(\varepsilon)\) is defined as the minimal number of continuous linear functionals that is needed to approximate \(X_d\) with a relative 2-average error not exceeding a given threshold \(\varepsilon \in(0, 1)\). In the paper we investigate \(n^{X_d}(\varepsilon)\) for arbitrary fixed \(\varepsilon \in (0,1)\) and \(d \to \infty\). Namely, we find criteria for the (un)boundedness of \(n^{X_d}(\varepsilon)\) on \(d\) and for tending \(n^{X_d}(\varepsilon) \to \infty\), \(d \to \infty\), for any fixed \(\varepsilon \in(0, 1)\). In the latter case we obtain necessary and sufficient conditions for the following logarithmic asymptotics \[ \ln n^{X_d}(\varepsilon) = a_d + q(\varepsilon) b_d + o(b_d), \;\;d \to \infty \] at continuity points of a non-decreasing function \(q \colon (0,1) \to \mathbb{R}\). Here \((a_d)_{d \in \mathbb{N}}\) is a sequence and \((b_d)_{d \in \mathbb{N}}\) is a positive sequence such that \(b_d \to \infty\), \(d \to \infty\). Under rather weak assumptions, we show that for tensor product-type random elements only special quantiles of self-decomposable or, in particular, stable (for tensor degrees) probability distributions appear as functions \(q\) in the asymptotics. We apply our results to the tensor products of the Euler integrated processes with a given variation of smoothness parameters and to the tensor degrees of random elements with regularly varying eigenvalues of the covariance operator.

60G99 Stochastic processes
60G60 Random fields
60G15 Gaussian processes
60B12 Limit theorems for vector-valued random variables (infinite-dimensional case)
41A60 Asymptotic approximations, asymptotic expansions (steepest descent, etc.)
Full Text: DOI arXiv
[1] Adler, R. J.; Taylor, J., Random fields and geometry, (2007), Springer New York · Zbl 1149.60003
[2] Applebaum, D., Lévy processes and stochastic calculus, (2009), Camb. Univ. Press Cambridge · Zbl 1200.60001
[3] Bingham, N. H.; Goldie, C. M.; Teugels, J. L., Regular variation, (1987), Camb. Univ. Press Cambridge · Zbl 0617.26001
[4] Chang, C.-H.; Ha, C.-W., The Green functions of some boundary value problems via the Bernoulli and Euler polynomials, Arch. Math. (Basel), 76, 5, 360-365, (2001) · Zbl 0986.34010
[5] Christoph, G.; Wolf, W., (Convergence Theorems with a Stable Limit Law, Math. Research, vol. 70, (1992), Akad. Verlag Berlin) · Zbl 0773.60012
[6] Darling, D. A., The influence of the maximum term in the addition of independent random variables, Trans. Amer. Math. Soc., 73, 1, 95-107, (1952) · Zbl 0047.37502
[7] Feller, W., Introduction to Probability Theory and its Applications, vol. 2, (1971), Wiley New York · Zbl 0219.60003
[8] Gao, F.; Hanning, J.; Torcaso, F., Integrated Brownian motions and exact \(L_2\)-small balls, Ann. Probab., 31, 3, 1320-1337, (2003) · Zbl 1047.60030
[9] Gnedenko, B. V.; Kolmogorov, A. N., Limit distributions for sums of independent random variables, (1954), Addison-Wesley Cambridge · Zbl 0056.36001
[10] Gradshteyn, I. S.; Ryzhik, I. M., Tables of integrals, series and products, (2007), Elsevier Burlington · Zbl 1208.65001
[11] Hall, P., A comedy of errors: the canonical form for a stable characteristic function, Bull. Lond. Math. Soc., 13, 1, 23-27, (1981) · Zbl 0505.60022
[12] Hensley, D., The convolution powers of the dickman function, J. Lond. Math. Soc., 33, 3, 395-406, (1986) · Zbl 0565.10041
[13] Hudson, W. N.; Tucker, H. G., On admissible translates of infinitely divisible distributions, Z. Wahrscheinlichkeitstheor. Verwandte Geb., 31, 65-72, (1975) · Zbl 0292.60028
[14] Ibragimov, I. A.; Linnik, Yu. V., Independent and stationary sequences of random variables, (1971), Wolters-Noordhoff Groningen · Zbl 0219.60027
[15] 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) · Zbl 1136.60024
[16] Lifshits, M. A., Lectures on Gaussian processes, (2012), Springer New York · Zbl 1248.60002
[17] Lifshits, M. A.; Papageorgiou, A.; Woźniakowski, H., Average case tractability of non-homogeneous tensor product problems, J. Complexity, 28, 5-6, 539-561, (2012) · Zbl 1262.65212
[18] Lifshits, M. A.; Papageorgiou, A.; Woźniakowski, H., Tractability of multi-parametric Euler and Wiener integrated processes, Probab. Math. Statist., 32, 1, 131-165, (2012) · Zbl 1254.65016
[19] Lifshits, M. A.; Tulyakova, E. V., Curse of dimensionality in approximation of random fields, Probab. Math. Statist., 26, 1, 97-112, (2006) · Zbl 1113.41038
[20] Lifshits, M. A.; Zani, M., Approximation complexity of additive random fields, J. Complexity, 24, 3, 362-379, (2008) · Zbl 1152.65014
[21] M.A. Lifshits, M. Zani, Approximation of additive random fields based on standard information: average case and probabilistic settings, arXiv:1402.5489. · Zbl 1339.60058
[22] Linnik, Yu. V.; Ostrovskii, I. V., (Decomposition of Random Variables and Vectors, Transl. Math. Monog., vol. 48, (1977), AMS Providence, Rhode Island) · Zbl 0358.60020
[23] Loéve, M., (Probability Theory I, vol. 1, Grad. Text Math., vol. 45, (1977), Springer-Verlag New-York) · Zbl 0359.60001
[24] Makarov, B. M.; Goluzina, M. G.; Lodkin, A. A.; Podkorytov, A. N., (Selected Problems in Real Analysis, Transl. Math. Monog., vol. 107, (1992), AMS Providence, Rhode Island) · Zbl 0858.26002
[25] Nagaev, S. V.; Vachtel, V. I., On sums of independent random variables without power moments, Sib. Math. J., 49, 6, 1091-1100, (2008)
[26] Nazarov, A. I.; Nikitin, Ya. Yu., Exact \(L_2\)-small ball behavior of integrated Gaussian processes and spectral asymptotics of boundary value problems, Probab. Theory Related Fields, 129, 4, 469-494, (2004) · Zbl 1051.60041
[27] Novak, E.; Sloan, I. H.; Traub, J. F.; Woźniakowski, H., Essays on the complexity of continuous problems, (2009), EMS Zürich · Zbl 1165.68018
[28] Novak, E.; Woźniakowski, H., (Tractability of Multivariate Problems. Volume I: Linear Information, EMS Tracts Math., vol. 6, (2008), EMS Zürich) · Zbl 1156.65001
[29] Novak, E.; Woźniakowski, H., (Tractability of Multivariate Problems. Volume II: Standard Information for Functionals, EMS Tracts Math., vol. 12, (2010), EMS Zürich) · Zbl 1241.65025
[30] Novak, E.; Woźniakowski, H., (Tractability of Multivariate Problems. Volume III: Standard Information for Operators, EMS Tracts Math., vol. 18, (2012), EMS Zürich) · Zbl 1359.65003
[31] Petrov, V. V., (Limit Theorems of Probability Theory: Sequences of Independent Random Variables, Oxford Stud. Prob., vol. 4, (1995), Clarendon Press Oxford) · Zbl 0826.60001
[32] Ritter, K., (Average-case Analysis of Numerical Problems, Lecture Notes in Math., vol. 1733, (2000), Springer Berlin) · Zbl 0949.65146
[33] Samorodnitsky, G.; Taqqu, M. S., Stable non-Gaussian random processes: stochastics models with infinite variance, (1994), Chapman & Hall London · Zbl 0925.60027
[34] Sato, K.-I., Lévy processes and infinitely divisible distributions, (1999), Camb. Univ. Press Cambridge · Zbl 0973.60001
[35] Sato, K.-I.; Yamazato, M., On distribution function of class \(L\), Z. Wahrscheinlichkeitstheor. Verwandte Geb., 43, 273-308, (1978) · Zbl 0395.60019
[36] Tenenbaum, G., Introduction to analytic and probabilistic number theory, (1995), Camb. Univ. Press Cambridge · Zbl 0788.11001
[37] Traub, J. F.; Wasilkowski, G. W.; Woźniakowski, H., Information, uncertainty, complexity, (1983), Addison-Wesley Reading, MA · Zbl 0522.68041
[38] Traub, J. F.; Wasilkowski, G. W.; Woźniakowski, H., Information-based complexity, (1988), Academic Press New York · Zbl 0674.68039
[39] Traub, J. F.; Werschulz, A. G., Complexity and information, (1998), Camb. Univ. Press Cambridge · Zbl 0917.68094
[40] Traub, J. F.; Woźniakowski, H., A general theory of optimal algorithms, (1980), Academic Press NewYork · Zbl 0441.68046
[41] van der Vaart, A. W., Asymptotic statistics, (1998), Camb. Univ. Press Cambridge · Zbl 0910.62001
[42] Wasilkowski, G. W.; Woźniakowski, H., Average case optimal algorithms in Hilbert spaces, J. Approx. Theory, 47, 17-25, (1986) · Zbl 0588.41008
[43] Whitt, W., Stochastic-process limits: an introduction to stochastic-process limits and their application to queues, (2002), Springer New York · Zbl 0993.60001
[44] Wolfe, S. J., On the unimodality of \(L\) functions, Ann. Math. Statist., 42, 3, 912-918, (1971) · Zbl 0219.60026
[45] Wolfe, S. J., On the continuity properties of \(L\) functions, Ann. Math. Statist., 42, 6, 2064-2073, (1971) · Zbl 0227.60014
[46] Yamazato, M., Unimodality of infinitely divisible distribution functions of class \(L\), Ann. Probab., 6, 4, 523-531, (1978) · Zbl 0394.60017
[47] Zolotarev, V. M., The analytic structure of infinitely divisible laws of class \(L\), Litov. Mat. Sb., 3, 123-140, (1963)
[48] Zolotarev, V. M., (One-dimensional Stable Distributions, Transl. Math. Monog., vol. 65, (1986), AMS Providence, Rhode Island) · Zbl 0589.60015
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.