A new characterization of -weak tractability

详细信息    查看全文

• 作者：A.G. Werschulz^a ; ^b ; ^{agw@cs.columbia.edu} ; H. Woźniakowski^b ; ^c ; ^{henryk@cs.columbia.edu}
• 关键词：Weak tractability ; Curse of dimensionality ; Approximation
• 刊名：Journal of Complexity
• 出版年：2017
• 出版时间：February 2017
• 年：2017
• 卷：38
• 期：Complete
• 页码：68-79
• 全文大小：425 K
• 卷排序：38

文摘

Siedlecki and Weimar (2015) defined the notion of (s,t)(s,t)-weak tractability for linear multivariate problems, which holds if the information complexity of the multivariate problem is not exponential in dt and ε−sε−s, where dd is the number of variables and εε is the error threshold with positive ss and tt. For Hilbert spaces, they were able to characterize (s,t)(s,t)-weak tractability in terms of how quickly the corresponding ordered singular values decay. Using this result, they studied the embedding of Hr(Td)Hr(Td) into L2(Td)L2(Td), where TdTd is the dd-dimensional torus, determining precisely when this problem is (s,t)(s,t)-tractable for a given dd and rr. Their proof is based on deep results of Kühn 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)(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 Kühn et al. (2014).