Liberating the dimension for \(L_2\)-approximation (Q423879): Difference between revisions

The variable \(u\) varies over finite subsets of \(\{1,2,3,\ldots\}\). \(H_u\) is a tensor product of univariate Hilbert spaces with probability density \(\rho\) over a domain \(D\). Consider \(\infty\)-variate functions of the form \(f=\sum_u f_u\in\mathcal{F}_\gamma\), i.e., for which \(\|f\|_{\mathcal{F}_\gamma}=[\sum_u\gamma_u^{-1}\|f_u\|_{H_u}^2]^{1/2}<\infty\). The problem is to approximate \(f\in\mathcal{F}_\gamma\) in the \(L_2\)-norm \[ \|f\|_{\mathcal{L}_2}=\lim_{d\to\infty}\int_{D^d}\left|\sum_{u\subseteq\{1,\ldots,d\}} f_u(\mathbf{x})\right|^2\prod_{j=1}^d \rho(x_j)d\mathbf{x}. \] The approximation is of the form \(\sum_i L_i(f) g_i\) with \(g_i\in\mathcal{L}_2\) and \(L_i\) a linear functional (unrestricted linear information) or \(L_i(f)\) is just a function sample \(f(\mathbf{x}_i)\) (standard information). If an error less than \(\epsilon\) can be obtained with a complexity bounded by \(C\epsilon^{-p}\) then the problem is polynomially tractable. Weakly tractable means that the complexity does not depend exponentially on \(1/\epsilon\). In the paper sufficient conditions for polynomial and weak tractability are derived. These conditions depend on the decay of the weights \(\gamma_u\) and on the complexity needed to solve the univariate case, see also \textit{M. Weimar} [J. Complexity 28, No. 1, 59--75 (2012; Zbl 1234.41027)].