Asymptotic analysis of average case approximation complexity of Hilbert space valued random elements

作者：Khartov A A^*

来源：Journal of Complexity, 2015, 31(6): 835-866.

DOI：10.1016/j.jco.2015.06.004

• Multivariate problems
• Tensor product-type random elements
• Approximation
• Average case approximation complexity
• Asymptotic analysis
• Tractability

We study approximation properties of sequences of centered random elements X-d, d is an element of 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(Xd) (epsilon) 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 epsilon is an element of (0, 1). In the paper we investigate n(Xd) (epsilon) for arbitrary fixed epsilon is an element of (0, 1) and d -> infinity. Namely, we find criteria of (un) bounded-ness for n(Xd) (epsilon) on d and of tending n(Xd) (epsilon) -> infinity, d -> infinity, for any fixed epsilon is an element of (0, 1). In the latter case we obtain necessary and sufficient conditions for the following logarithmic asymptotics
ln n(Xd) (epsilon) = a(d) q(epsilon)b(d) o(b(d)), d -> infinity,
at continuity points of a non-decreasing function q: (0, 1) -> R Here (a(d))(d is an element of N) is a sequence and (b(d))(d is an element of N) is a positive sequence such that b(d) -> infinity, d -> infinity. 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 covariance operator.

• 出版日期2015-12