Optimal algorithms for numerical integration: recent results and open problems
From MaRDI portal
Let \( D_d\subset\mathbb R^d \) be open set with Lebesgue measure 1. For example one may take the unit cube \(D_d:=[0,1]^d\). The subject of this paper is studying algorithms and tractibility for the the approximation of the integral \(S_d(f)=\int_{D_d}f(x)dx\) for integrable functions \(f:D_d\to \mathbb R\). Given fixed \( \varepsilon>0\) the underlying question concerns the minimal number of function values that are required to achieve an error of \(\varepsilon \). The author presents a detailed and comprehensive survey on optimal algorithms for numerical integration in the following senses. Lower bounds, universality, general domains and IID information. There is an excellent set of open problems presented with some well written concluding remarks. As a world authority on this subject, the author has produced an up to date excellent and well written paper with a wealth of good references.\N\NFor the entire collection see [Zbl 1552.65006].
Cites work
- 4. On the power of random information
- A Monte Carlo method for integration of multivariate smooth functions
- A new upper bound for sampling numbers
- A note on sampling recovery of multivariate functions in the uniform norm
- A sharp upper bound for sampling numbers in \(L_2\)
- A universal algorithm for multivariate integration
- A variant of Schur's product theorem and its applications
- Algorithms and complexity for functions on general domains
- An estimate of the mean remainder term in quadrature formulae
- Approximation numbers of Sobolev embeddings-sharp constants and tractability
- Approximation of mixed order Sobolev functions on the \(d\)-torus: asymptotics, preasymptotics, and \(d\)-dependence
- Automatic integration using asymptotically optimal adaptive simpson quadrature
- Bases in function spaces, sampling, discrepancy, numerical integration
- Complexity of oscillatory integrals on the real line
- Complexity of oscillatory integration for univariate Sobolev spaces
- Component-by-component construction of randomized rank-1 lattice rules achieving almost the optimal randomized error rate
- Construction of interlaced scrambled polynomial lattice rules of arbitrary high order
- Construction-free median quasi-Monte Carlo rules for function spaces with unspecified smoothness and general weights
- Constructive subsampling of finite frames with applications in optimal function recovery
- Das asymptotische Verteilungsgesetz der Eigenwerte linearer partieller Differentialgleichungen (mit einer Anwendung auf die Theorie der Hohlraumstrahlung).
- Deterministic and stochastic error bounds in numerical analysis
- Digit-by-digit and component-by-component constructions of lattice rules for periodic functions with unknown smoothness
- Discrepancy theory and quasi-Monte Carlo integration
- Explicit error bounds for Markov chain Monte Carlo
- Explicit error bounds for randomized Smolyak algorithms and an application to infinite-dimensional integration
- Exponential tractability of \(L_2\)-approximation with function values
- Faster estimates of the mean of bounded random variables
- Function spaces and wavelets on domains
- Function spaces in Lipschitz domains and optimal rates of convergence for sampling
- Function spaces with dominating mixed smoothness
- Function values are enough for \(L_2\)-approximation
- Function values are enough for \(L_2\)-approximation. II
- High dimensional integration of smooth functions over cubes
- High dimensional polynomial interpolation on sparse grids
- scientific article; zbMATH DE number 5797591 (Why is no real title available?)
- scientific article; zbMATH DE number 3688714 (Why is no real title available?)
- scientific article; zbMATH DE number 193625 (Why is no real title available?)
- scientific article; zbMATH DE number 1126861 (Why is no real title available?)
- scientific article; zbMATH DE number 898099 (Why is no real title available?)
- Hyperbolic cross approximation. Lecture notes given at the courses on constructive approximation and harmonic analysis, Barcelona, Spain, May 30 -- June 3, 2016
- Intractability results for integration and discrepancy
- Intractability results for positive quadrature formulas and extremal problems for trigonometric polynomials
- Introduction to quasi-Monte Carlo integration and applications
- Lattice Rules
- Lattice rules with random \(n\) achieve nearly the optimal \(\mathcal{O}(n^{-\alpha-1/2})\) error independently of the dimension
- Linear vs. nonlinear algorithms for linear problems
- Lower bounds for integration and recovery in L₂
- Lower bounds for the error of quadrature formulas for Hilbert spaces
- Modern Monte Carlo methods for efficient uncertainty quantification and propagation: a survey
- Monte Carlo algorithms.
- New lower bounds for the integration of periodic functions
- Numerical integration of Hölder continuous, absolutely convergent Fourier, Fourier cosine, and Walsh series
- Numerical integration of peak functions
- On asymptotically optimal cubatures for multidimensional Sobolev spaces
- On optimal adaptive quadratures for automatic integration
- On optimal recovery in L₂
- On the approximate calculation of multiple integrals
- On the power of adaption
- On the power of standard information for tractability for \(L_2\)-approximation in the average case setting
- On the worst-case error of least squares algorithms for L₂-approximation with high probability
- On weak tractability of the Clenshaw-Curtis Smolyak algorithm
- On weak tractability of the Smolyak algorithm for approximation problems
- Optimal approximation of multivariate periodic Sobolev functions in the sup-norm
- Optimal confidence for Monte Carlo integration of smooth functions
- Optimal Monte Carlo integration on closed manifolds
- Optimal Monte Carlo methods for \(L^2\)-approximation
- Optimal order quadrature error bounds for infinite-dimensional higher-order digital sequences
- Optimal pointwise sampling for \(L^2\) approximation
- Optimal quadrature formulas for the Sobolev space H^1
- Optimum quantization and its applications
- Polynomial tractability for integration in an unweighted function space with absolutely convergent Fourier series
- Product rules are optimal for numerical integration in classical smoothness spaces
- Quadrature and widths
- Quadrature rules and distribution of points on manifolds
- Random approximation of Sobolev embeddings
- Random sections of ellipsoids and the power of random information
- Random-prime-fixed-vector randomised lattice-based algorithm for high-dimensional integration
- Randomized approximation of Sobolev embeddings
- Randomized approximation of Sobolev embeddings. II
- Randomized approximation of Sobolev embeddings. III
- Recent advances in higher order quasi-Monte Carlo methods
- Recovery of Sobolev functions restricted to iid sampling
- Reproducing kernels of Sobolev spaces on \(\mathbb{R}^d\) and applications to embedding constants and tractability
- Sampling numbers and function spaces
- Simple characterizations of exponential tractability for linear multivariate problems
- Simple cubature formulas with high polynomial exactness
- Sobolev bounds on functions with scattered zeros, with applications to radial basis function surface fitting
- Sobolev Spaces
- Solvable integration problems and optimal sample size selection
- Some results on the complexity of numerical integration
- Stability of lattice rules and polynomial lattice rules constructed by the component-by-component algorithm
- Stable high-order randomized cubature formulae in arbitrary dimension
- Super-polynomial accuracy of one dimensional randomized nets using the median of means
- Support Vector Machines
- Tensor power sequences and the approximation of tensor product operators
- The cost of deterministic, adaptive, automatic algorithms: cones, not balls
- The curse of dimensionality for numerical integration of smooth functions
- The curse of dimensionality for numerical integration of smooth functions. II
- The curse of dimensionality for numerical integration on general domains
- The curse of dimensionality for the \(L_p\)-discrepancy with finite \(p\)
- The inverse of the star-discrepancy depends linearly on the dimension
- The Modern Mathematics of Deep Learning
- The power of adaptive algorithms for functions with singularities
- Tractability of approximation in the weighted Korobov space in the worst-case setting -- a complete picture
- Tractability of multivariate problems. Volume I: Linear information
- Tractability of multivariate problems. Volume II: Standard information for functionals.
- Tractability of multivariate problems. Volume III: Standard information for operators
- Understanding machine learning. From theory to algorithms
- Uniform recovery of high-dimensional C^r-functions
- Weak and quasi-polynomial tractability of approximation of infinitely differentiable functions
- Widths of embeddings in function spaces
- Worst-case recovery guarantees for least squares approximation using random samples
Cited in
(3)
This page was built for publication: Optimal algorithms for numerical integration: recent results and open problems
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7012124)
