The complexity of linear tensor product problems in (anti)symmetric Hilbert spaces (Q1759353): Difference between revisions

Let \(H_1\) be an infinite dimensional separable Hilbert space, \(G_1\) be another Hilbert space and \(S_1:H_1\to D_1\) be a compact operator. For an integer \(d>1\), let \(H_d=H_1\otimes\dotsb\otimes H_1\) and \(G_d=G_1\otimes\dotsb\otimes G_1\) be \(d\)-folder tensor products of these spaces and let \(S_d:H_d\to G_d\) be the tensor product of the operator \(S_1\). The tensor product problem consists in an approximation of the operator \(S_d\) by an algorithm which uses a finite number of functionals. Many of the concepts can be found in the monograph [\textit{E. Novak} and \textit{H. Woźniakowski}, Tractability of multivariate problems. Volume I: Linear information. Zürich: European Mathematical Society (EMS) (2008; Zbl 1156.65001)]. In the present paper, the author studies a constrained tensor product problem in which the space \(H_d\) is replaced by the subspace \(P_I(H_d)\), where \(P_I\) is one of the following two operators, namely the symmetrizer \(\mathcal{G}_I\), given by \(\mathcal{G}_I(f)=(1/ \sharp S_I)\sum_{\pi\in S_I}f(\pi(\cdot))\), or the antisymmetrizer \(\mathcal{U}_I\), given by \(\mathcal{U}_I(f)=(1/ \sharp S_I)\sum_{\pi\in S_I}(-1)^{|\pi|}f(\pi(\cdot))\), respectively. Here, \(I\subset\{1,\dotsc,d\}\) is a fixed set of indices, \(S_I\) is the set of permutations of the set \(\{1,\dotsc,d\}\), which does not permute the elements of the set \(\{1,\dotsc,d\}\setminus I\), \(\sharp S_I\) is the cardinality of \(S_I\) and \((-1)^{|\pi|}\) is the sign of a permutation \(\pi\). Using the sequence \(\lambda=(\lambda_i)_{i\in\mathbb{N}}\), \(\lambda_1\geq\lambda_2\geq\dotsb\geq 0\) of the squared singular values of the operator \(S_1\), the author gives a description of optimal linear algorithms for both of these problems. Then the complexity of the obtained optimal algorithms is studied, i.e., the behavior of the function \(n(\varepsilon,d)\), which equals to the smallest integer \(n\), such that the given linear algorithm with \(n\) functionals gives a degree of approximation smaller than \(\varepsilon>0\), for all functions \(f\) belonging to the unit ball of the space \(P_I(H_d)\). Special attention is paid to polynomial tractability, i.e., whether there exist constants \(C,p>0\) and \(q\geq0\), such that \(n(\varepsilon,d)\leq C\cdot \varepsilon^{-p}\cdot d^q\) holds, for all \(d\in\mathbb{N}\), \(\varepsilon\in(0,1]\), as well to strong polynomial tractability, which corresponds to the particular case of \(q=0\). The discussion is carried out using the sequence \(\lambda\). Finally, the theory is applied to the Schrödinger equation.