Generalized tractability for multivariate problems. II: Linear tensor product problems, linear information, and unrestricted tractability (Q839659)

Tractability means the difficulty of approximating operators defined over spaces of functions with \(d\) variables. This is the second of two papers about the generalized tractability for the multivariate problem \(S_{d},\) where for \(d=1,2, \dots\) \(S_{d}\) is defined as \(d\)-fold linear tensor product of a compact linear operator \(S_{1}.\) Also the weak tractability is studied. The results obtained in this paper for the unrestricted domains \(\Omega^{\text{unr}}\) are compared with the results of the first paper, obtained for restricted domains [for part I see J. Complexity 23, No.~2, 262--295 (2007; Zbl 1118.65001)]. Here \(n(\epsilon, S_{d})\) denotes the minimal number of information evaluations needed to approximate \(S_{d}\) to within \(\epsilon \in [0,1].\) The notions of a tractability function, a weak tractability, a tractability domain and an unrestricted tractability domain \(\Omega^{\text{unr}}\) are recalled. An algorithm \(A_{n,d}(f)\) that uses finitely many information evaluations is proposed by an approximation of the operator \(S_{d}.\) The worst case error and the initial error of the algorithm \(A_{n,d}(f)\) are defined. The information complexity \(n(\epsilon, S_{d}, \Lambda_{d})\) of the operator \(S_{d}\) is defined. The notions of a \((T,\Omega)\)-tractability, a strong \((T,\Omega)\)-tractability and a weak tractability of the multivariate problem \( S = \{S_{d}\}\) in the class \(\Lambda = \{\Lambda_{d}\}\) of information evaluations are defined. In Section 3 the case of finitely many eigenvalues is considered. Theorem 3.2 provides a necessary and sufficient condition that the linear tensor product problem \(S\) to be \((T,\Omega^{\text{unr}})\)-tractable. The result of this theorem is illustrated by three kinds of tractability functions. In Corollary 3.3 the general case of finitely many positive eigenvalues is considered and a necessary and sufficient condition for \((T,\Omega^{\text{unr}})\)-tractability of the problem \(S\) is presented. Corollary 3.8 provides a sufficient condition that an arbitrary problem \(S\) with finitely many eigenvalues to be \((T,\Omega^{\text{unr}})\)-tractable. In Section 4 the linear tensor problem with infinitely many positive eigenvalues is studied. In Theorem 4.1 a necessary and sufficient condition that the linear tensor product problem \(S\) with exponentially decaying eigenvalues to be \((T,\Omega^{\text{unr}})\)-tractable is shown. Also upper and lower estimations of the exponent \(t^{\text{tra}}\) are obtained. In corollary 4.3 the necessary and sufficient condition, exposed in Theorem 4.1, for \((T,\Omega^{\text{unr}})\)-tractability is simplified. In Section 5 the tractability for the linear tensor product problem \(S\) with polynomially decaying eigenvalues for \(d=1\) is studied. In Theorem 5.1 a sufficient condition for \((T,\Omega^{\text{unr}})\)-tractability of \(S\) is shown and upper and lower estimations of the exponent \(t^{\text{tra}}\) are obtained. Corollary 5.2 considers the case of a special form of the tractability function and the concret necessary and sufficient condition for \((T,\Omega^{\text{unr}})\)-tractability of \(S\) is obtained. Estimations of the exponent of the tractability \(t^{\text{tra}}\) are shown. In Theorem 5.3 another form of the tractability function is considered and again a necessary and sufficient condition for \((T,\Omega^{\text{unr}})\)-tractability of \(S\) is obtained. The exponents of the tractability of this case are obtained. In Section 6 it is shown that the exponential or polynomial decay of the eigenvalues implies weak tractability. Theoem 6.1 proviedes a sufficient condition for weakly tractability of \(S.\) In Section 7 tractability results for unrestricted domain \(\Omega^{\text{unr}}\) are compared with the tractability results of the first part of the paper.