A new characterization of (s, t)-weak tractability

作者：Werschulz A G^*; Wozniakowski H

来源：Journal of Complexity, 2017, 38: 68-79.

DOI：10.1016/j.jco.2016.10.006

• Weak tractability
• Curse of dimensionality
• Approximation

Siedlecki and Weimar (2015) defined the notion of (s, t)-weak tractability for linear multivariate problems, which holds if the information complexity of the multivariate problem is not exponential in d(t) and epsilon(-s), where d is the number of variables and epsilon is the error threshold with positive s and t. For Hilbert spaces, they were able to characterize (s, t)-weak tractability in terms of how quickly the corresponding ordered singular values decay. Using this result, they studied the embedding of H-r(T-d) into L-2(T-d), where T-d is the d-dimensional torus, determining precisely when this problem is (s, t)-tractable for a given d and r. Their proof is based on deep results of Kuhn et al. (2014), which are complicated by the difficulty of ordering the singular values. In this paper, we provide a new characterization of (s, t)-weak tractability of multivariate problems over Hilbert spaces, which does not require us to order the singular values. This allows us to obtain a new, and somewhat simpler, proof of the Siedlecki and Weimar (2015) result that does not need to use the results of Kuhn et al. (2014).

• 出版日期2017-2