Generalized Tractability for Multivariate Problems: Part II: Linear Tensor Product Problems, Linear Information, and Unrestricted Tractability

Title:

Generalized Tractability for Multivariate Problems: Part II: Linear Tensor Product Problems, Linear Information, and Unrestricted Tractability

Author(s):

Gnewuch, Michael
Wozniakowski, Henryk

Date:

2007

Type:

Technical reports

Department:

Computer Science

Permanent URL:

http://hdl.handle.net/10022/AC:P:29533

Series:

Columbia University Computer Science Technical Reports

Part Number:

CUCS04207

Abstract:

\usepackage{amssymb} \begin{document} We continue the study of generalized tractability initiated in our previous paper ``Generalized tractability for multivariate problems, Part I: Linear tensor product problems and linear information'', J. Complexity, 23, 262295 (2007). We study linear tensor product problems for which we can compute linear information which is given by arbitrary continuous linear functionals. We want to approximate an operator $S_d$ given as the $d$fold tensor product of a compact linear operator $S_1$ for $d=1,2,\dots\,$, with $\S_1\=1$ and $S_1$ has at least two positive singular values. Let $n(\varepsilon,S_d)$ be the minimal number of information evaluations needed to approximate $S_d$ to within $\varepsilon\in[0,1]$. We study \emph{generalized tractability} by verifying when $n(\varepsilon,S_d)$ can be bounded by a multiple of a power of $T(\varepsilon^{1},d)$ for all $(\varepsilon^{1},d)\in\Omega \subseteq[1,\infty)\times \mathbb{N}$. Here, $T$ is a \emph{tractability} function which is nondecreasing in both variables and grows slower than exponentially to infinity. We study the \emph{exponent of tractability} which is the smallest power of $T(\varepsilon^{1},d)$ whose multiple bounds $n(\varepsilon,S_d)$. We also study \emph{weak tractability}, i.e., when $\lim_{\varepsilon^{1}+d\to\infty,(\varepsilon^{1},d)\in\Omega} \ln\,n(\varepsilon,S_d)/(\varepsilon^{1}+d)=0$. In our previous paper, we studied generalized tractability for proper subsets $\Omega$ of $[1,\infty)\times\mathbb{N}$, whereas in this paper we take the unrestricted domain $\Omega^{\rm unr}=[1,\infty)\times\mathbb{N}$. We consider the three cases for which we have only finitely many positive singular values of $S_1$, or they decay exponentially or polynomially fast. Weak tractability holds for these three cases, and for all linear tensor product problems for which the singular values of $S_1$ decay slightly faster that logarithmically. We provide necessary and sufficient conditions on the function~$T$ such that generalized tractability holds. These conditions are obtained in terms of the singular values of $S_1$ and mostly limiting properties of $T$. The tractability conditions tell us how fast $T$ must go to infinity. It is known that $T$ must go to infinity faster than polynomially. We show that generalized tractability is obtained for $T(x,y)=x^{1+\ln\,y}$. We also study tractability functions $T$ of product form, $T(x,y) =f_1(x)f_2(x)$. Assume that $a_i=\liminf_{x\to\infty}(\ln\,\ln f_i(x))/(\ln\,\ln\,x)$ is finite for $i=1,2$. Then generalized tractability takes place iff $$a_i>1 \ \ \mbox{and}\ \ (a_11)(a_21)\ge1,$$ and if $(a_11)(a_21)=1$ then we need to assume one more condition given in the paper. If $(a_11)(a_21)>1$ then the exponent of tractability is zero, and if $(a_11)(a_21)=1$ then the exponent of tractability is finite. It is interesting to add that for $T$ being of the product form, the tractability conditions as well as the exponent of tractability depend only on the second singular eigenvalue of $S_1$ and they do \emph{not} depend on the rate of their decay. Finally, we compare the results obtained in this paper for the unrestricted domain $\Omega^{\rm unr}$ with the results from our previous paper obtained for the restricted domain $\Omega^{\rm res}= [1,\infty)\times\{1,2,\dots,d^*\}\,\cup\,[1,\varepsilon_0^{1})\times\mathbb{N}$ with $d^*\ge1$ and $\varepsilon_0\in(0,1)$. In general, the tractability results are quite different. We may have generalized tractability for the restricted domain and no generalized tractability for the unrestricted domain which is the case, for instance, for polynomial tractability $T(x,y)=xy$. We may also have generalized tractability for both domains with different or with the same exponents of tractability. \end{document}

Subject(s):

Computer science
 Item views:

194
 Metadata:

text  xml
 Suggested Citation:

Michael Gnewuch, Henryk Wozniakowski,
2007,
Generalized Tractability for Multivariate Problems: Part II: Linear Tensor Product Problems, Linear Information, and Unrestricted Tractability, Columbia University Academic Commons,
http://hdl.handle.net/10022/AC:P:29533.