The curse of dimensionality for numerical integration of smooth functions II

详细信息    查看全文

• 作者：Aicke Hinrichs^a ; ^{a.hinrichs@uni-jena.de" class="auth_mail} ; Erich Novak^a ; ^{erich.novak@uni-jena.de" class="auth_mail} ; Mario Ullrich^a ; ^{ullrich.mario@gmail.com" class="auth_mail} ; Henryk Wo藕niakowski^b ; ^c ; ^{henryk@cs.columbia.edu" class="auth_mail}
• 关键词：Integration ; Tractability ; Curse of dimensionality
• 刊名：Journal of Complexity
• 出版年：April, 2014
• 年：2014
• 卷：30
• 期：2
• 页码：117-143
• 全文大小：475 K

文摘

We prove the curse of dimensionality in the worst case setting for numerical integration for a number of classes of smooth -variate functions. Roughly speaking, we consider different bounds for the directional or partial derivatives of and ask whether the curse of dimensionality holds for the respective classes of functions. We always assume that has volume one and we often assume additionally that is either convex or that its radius is proportional to . In particular, can be the unit cube. We consider various values of including the case which corresponds to infinitely differentiable functions. We obtain necessary and sufficient conditions, and in some cases a full characterization for the curse of dimensionality. For infinitely differentiable functions we prove the curse if the bounds on the successive derivatives are appropriately large. The proof technique is based on a volume estimate of a neighborhood of the convex hull of points which decays exponentially fast in聽 . For , we also study conditions for quasi-polynomial, weak and uniform weak tractability. In particular, weak tractability holds if all directional derivatives are bounded by one. It is still an open problem if weak tractability holds if all partial derivatives are bounded by one.