TY - JOUR

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

AU - Khartov, A.A.

PY - 2015

Y1 - 2015

N2 - We study approximation properties of sequences of centered random elements $X_d$, $d\in\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}(\e)$ 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 $\e\in(0,1)$. In the paper we investigate $n^{X_d}(\e)$ for arbitrary fixed $\e\in(0,1)$ and $d\to\infty$. Namely, we find criteria of (un)boundedness for $n^{X_d}(\e)$ on $d$ and of tending $n^{X_d}(\e)\to\infty$, $d\to\infty$, for any fixed $\e\in(0,1)$. In the latter case we obtain necessary and sufficient conditions for the following logarithmic asymptotics \begin{eqnarray*} \ln n^{X_d}(\e)= a_d+q(\e)b_d+o(b_d),\quad d\to\infty, \end{eqnarray*} at continuity points of a non-decreasing function $q\c

AB - We study approximation properties of sequences of centered random elements $X_d$, $d\in\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}(\e)$ 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 $\e\in(0,1)$. In the paper we investigate $n^{X_d}(\e)$ for arbitrary fixed $\e\in(0,1)$ and $d\to\infty$. Namely, we find criteria of (un)boundedness for $n^{X_d}(\e)$ on $d$ and of tending $n^{X_d}(\e)\to\infty$, $d\to\infty$, for any fixed $\e\in(0,1)$. In the latter case we obtain necessary and sufficient conditions for the following logarithmic asymptotics \begin{eqnarray*} \ln n^{X_d}(\e)= a_d+q(\e)b_d+o(b_d),\quad d\to\infty, \end{eqnarray*} at continuity points of a non-decreasing function $q\c

KW - multivariate problems

KW - tensor product-type random elements

KW - approximation

KW - average case approximation complexity

KW - asymptotic analysis

KW - tractability.

U2 - 10.1016/j.jco.2015.06.004

DO - 10.1016/j.jco.2015.06.004

M3 - Article

VL - 31

SP - 835

EP - 866

JO - Journal of Complexity

JF - Journal of Complexity

SN - 0885-064X

IS - 6

ER -