The curse of dimensionality for numerical integration of smooth functions. II

DOI10.1016/J.JCO.2013.10.007zbMATH Open1286.65040arXiv1304.3372OpenAlexW2964286331MaRDI QIDQ2442811FDOQ2442811

Aicke Hinrichs, H. Woźniakowski, Erich Novak, Mario Ullrich

Publication date: 1 April 2014

Published in: Journal of Complexity (Search for Journal in Brave)

Abstract: We prove the curse of dimensionality in the worst case setting for numerical integration for a number of classes of smooth $d$-variate functions. Roughly speaking, we consider different bounds for the derivatives of $fin{C}^k(D_d)$ and ask whether the curse of dimensionality holds for the respective classes of functions. We always assume that $D_{d}subsetmathbb{R}^d$ has volume one and consider various values of $k$ including the case $k=infty$ which corresponds to infinitely many differentiable functions. We obtain necessary and sufficient conditions, and in some cases a full characterization for the curse of dimensionality. For infinitely many 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 $n$ points which decays exponentially fast if $n$ is small relative to $d$. For $k=infty$, we also also study conditions for quasi-polynomial, weak and uniform weak tractability.

Full work available at URL: https://arxiv.org/abs/1304.3372

Recommendations

• The curse of dimensionality for numerical integration of smooth functions
• When are integration and discrepancy tractable?
• Optimal order of convergence and (in)tractability of multivariate approximation of smooth functions
• The curse of dimensionality for the class of monotone functions and for the class of convex functions
• Integration and approximation in arbitrary dimensions

zbMATH Keywords

curse of dimensionalitynumerical integrationintegrationtractabilityworst casesmooth \(d\)-variate function

Mathematics Subject Classification ID

Numerical quadrature and cubature formulas (65D32) Multidimensional problems (41A63) Approximate quadratures (41A55)

Cites Work

• Compactly supported solutions of functional-differential equations and their applications
• Title not available (Why is that?)
• Tractability of multivariate problems. Volume I: Linear information
• Tractability of multivariate problems. Volume II: Standard information for functionals.
• A geometric inequality and the complexity of computing volume
• Uniform weak tractability
• On the optimality of linear methods for operator approximation in convex classes of functions
• The curse of dimensionality for numerical integration of smooth functions
• Title not available (Why is that?)
• Shape analysis via oriented distance functions
• Weak and quasi-polynomial tractability of approximation of infinitely differentiable functions
• Title not available (Why is that?)
• Multivariate integration in \(C^{\infty}([0,1]^{d})\) is not strongly tractable.
• The curse of dimensionality for the class of monotone functions and for the class of convex functions
• Title not available (Why is that?)

Cited In (20)

• Title not available (Why is that?)
• Algorithms and complexity for functions on general domains
• Some Results on the Complexity of Numerical Integration
• EC-tractability of approximation problems in function spaces defined over products of simplices
• The curse of dimensionality for numerical integration on general domains
• For numerical differentiation, dimensionality can be a blessing!
• Notes on \((s,t)\)-weak tractability: a refined classification of problems with (sub)exponential information complexity
• Points on manifolds with asymptotically optimal covering radius
• Optimal recovery and volume estimates
• ABC on IBC
• On a Kantorovich-Rubinstein inequality
• Entropy and sampling numbers of classes of ridge functions
• On weak tractability of the Clenshaw-Curtis Smolyak algorithm
• On weak tractability of the Smolyak algorithm for approximation problems
• Super-polynomial convergence and tractability of multivariate integration for infinitely times differentiable functions
• Polynomial tractability for integration in an unweighted function space with absolutely convergent Fourier series
• The radii of sections of origin-symmetric convex bodies and their applications
• Digital inversive vectors can achieve polynomial tractability for the weighted star discrepancy and for multivariate integration
• On the Wasserstein distance between classical sequences and the Lebesgue measure
• The role of Frolov's cubature formula for functions with bounded mixed derivative

This page was built for publication: The curse of dimensionality for numerical integration of smooth functions. II

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2442811)