Infinite-dimensional quadrature and approximation of distributions

DOI10.1007/S10208-008-9029-XzbMATH Open1177.65011arXivmath/0601240OpenAlexW2044203216MaRDI QIDQ839653FDOQ839653

Authors: J. Creutzig, Steffen Dereich, Thomas Müller-Gronbach, Klaus Ritter 

Publication date: 2 September 2009

Published in: Foundations of Computational Mathematics (Search for Journal in Brave)

Abstract: We study numerical integration of Lipschitz functionals on a Banach space by means of deterministic and randomized (Monte Carlo) algorithms. This quadrature problem is shown to be closely related to the problem of quantization of the underlying probability measure. In addition to the general setting we analyze in particular integration w.r.t. Gaussian measures and distributions of diffusion processes. We derive lower bounds for the worst case error of every algorithm in terms of its computational cost, and we present matching upper bounds, up to logarithms, and corresponding almost optimal algorithms. As auxiliary results we determine the asymptotic behaviour of quantization numbers and Kolmogorov widths for diffusion processes.

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

Recommendations

• Variable subspace sampling and multi-level algorithms
• Multi-level Monte Carlo algorithms for infinite-dimensional integration on \(\mathbb R^{\mathbb N}\)
• Quadrature for self-affine distributions on \(\mathbb R^d\)
• On the complexity of computing quadrature formulas for SDEs
• Random bit quadrature and approximation of distributions on Hilbert spaces

zbMATH Keywords

Gaussian measuresquadratureworst case errorMonte Carlo algorithmalmost optimal algorithmsaverage Kolmogorov widthnumerical integration of Lipschitz functional on Banach space

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Gaussian processes (60G15) Stochastic ordinary differential equations (aspects of stochastic analysis) (60H10) Approximation by arbitrary nonlinear expressions; widths and entropy (41A46)

Cites Work

• Gaussian processes: Inequalities, small ball probabilities and applications
• Foundations of quantization for probability distributions
• Title not available (Why is that?)
• Expansion of the global error for numerical schemes solving stochastic differential equations
• Monte Carlo complexity of global solution of integral equations
• Monte Carlo complexity of parametric integration
• Statistical Romberg extrapolation: a new variance reduction method and applications to option pricing
• Title not available (Why is that?)
• Title not available (Why is that?)
• The coding complexity of diffusion processes under supremum norm distortion
• Deterministic and stochastic error bounds in numerical analysis
• Average-case analysis of numerical problems
• The law of the Euler scheme for stochastic differential equations. I: Convergence rate of the distribution function
• On the optimality of linear methods for operator approximation in convex classes of functions
• s-numbers in information-based complexity
• Asymptotic analysis via Mellin transforms for small deviations in \(L^2\)-norm of integrated Brownian sheets
• Functional quantization of a class of Brownian diffusions: a constructive approach
• Title not available (Why is that?)
• Functional quantization for numerics with an application to option pricing
• Average \(n\)-widths of the Wiener space in the \(L_ \infty\)-norm
• Rate optimality of wavelet series approximations of fractional Brownian motion
• Complexity of weighted approximation over \(\mathbb{R}^d\)
• On tractability of path integration
• Title not available (Why is that?)
• Optimal series representation of fractional Brownian sheets
• On the link between small ball probabilities and the quantization problem for Gaussian measures on Banach spaces
• Sharp asymptotics of the functional quantization problem for Gaussian processes.
• A generalization of Ornstein's \(\overline d\) distance with applications to information theory
• Small ball probabilities of fractional Brownian sheets via fractional integration operators
• Small ball probabilities around random centers of Gaussian measures and applications to quantization
• Optimality of an explicit series expansion of the fractional Brownian sheet
• Title not available (Why is that?)
• High-resolution quantization and entropy coding for fractional Brownian motion
• The coding complexity of diffusion processes under \(L^p[0,1]\)-norm distortion
• Randomization for continuous problems
• Title not available (Why is that?)
• Small ball estimates for Gaussian processes under Sobolev type norms
• On the constructions and nonlinearity of binary vector-output correlation-immune functions
• Small ball probabilities for Gaussian processes with stationary increments under Hölder norms

Cited In (53)

• Optimal randomized changing dimension algorithms for infinite-dimensional integration on function spaces with ANOVA-type decomposition
• On multilevel Picard numerical approximations for high-dimensional nonlinear parabolic partial differential equations and high-dimensional nonlinear backward stochastic differential equations
• Quasi-Monte Carlo and \(\varepsilon\)-truncation dimension in ANOVA spaces
• How complex is a random picture?
• A Proof that Artificial Neural Networks Overcome the Curse of Dimensionality in the Numerical Approximation of Black–Scholes Partial Differential Equations
• On the complexity of computing quadrature formulas for SDEs
• \( \varepsilon \)-superposition and truncation dimensions in average and probabilistic settings for \(\infty \)-variate linear problems
• Liberating the dimension for \(L_2\)-approximation
• Embeddings of weighted Hilbert spaces and applications to multivariate and infinite-dimensional integration
• Strong convergence of an explicit numerical method for SDEs with nonglobally Lipschitz continuous coefficients
• Deterministic multi-level algorithms for infinite-dimensional integration on \(\mathbb R^{\mathbb N}\)
• Existence and construction of shifted lattice rules with an arbitrary number of points and bounded weighted star discrepancy for general decreasing weights
• Liberating the dimension for function approximation: standard information
• Liberating the dimension for function approximation
• Tractability of infinite-dimensional integration in the worst case and randomized settings
• Multilevel Monte Carlo for Lévy-driven SDEs: central limit theorems for adaptive Euler schemes
• A multilevel Monte Carlo algorithm for Lévy-driven stochastic differential equations
• Multilevel Monte Carlo algorithms for Lévy-driven SDEs with Gaussian correction
• Hyperbolic cross approximation in infinite dimensions
• Exact simulation of the 3/2 model
• On tractability of linear tensor product problems for \(\infty \)-variate classes of functions
• Multi-level Monte Carlo algorithms for infinite-dimensional integration on \(\mathbb R^{\mathbb N}\)
• Multilevel Monte Carlo simulation of Coulomb collisions
• The coding complexity of Lévy processes
• Random bit quadrature and approximation of distributions on Hilbert spaces
• On quadrature formulae for functions of an infinitely large number of variables
• Multilevel Monte Carlo simulation for Lévy processes based on the Wiener-Hopf factorisation
• Variable subspace sampling and multi-level algorithms
• Divergence of the multilevel Monte Carlo Euler method for nonlinear stochastic differential equations
• Central limit theorem for the multilevel Monte Carlo Euler method
• Coupling importance sampling and multilevel Monte Carlo using sample average approximation
• Liberating the dimension for function approximation and integration
• Average case tractability of approximating \(\infty\)-variate functions
• Efficient algorithms for multivariate and \(\infty\)-variate integration with exponential weight
• Quadrature for self-affine distributions on \(\mathbb R^d\)
• MDFEM: multivariate decomposition finite element method for elliptic PDEs with uniform random diffusion coefficients using higher-order QMC and FEM
• High resolution quantization and entropy coding of jump processes
• Entropy and sampling numbers of classes of ridge functions
• Strong convergence for explicit space-time discrete numerical approximation methods for stochastic Burgers equations
• Infinite-dimensional integration in weighted Hilbert spaces: anchored decompositions, optimal deterministic algorithms, and higher-order convergence
• Multilevel Picard iterations for solving smooth semilinear parabolic heat equations
• Random bit multilevel algorithms for stochastic differential equations
• Liberating the dimension
• Infinite-dimensional integration on weighted Hilbert spaces
• Tractability of approximation of \(\infty\)-variate functions with bounded mixed partial derivatives
• Infinite-dimensional integration and the multivariate decomposition method
• Overcoming the curse of dimensionality in the numerical approximation of semilinear parabolic partial differential equations
• Numerical approximations of stochastic differential equations with non-globally Lipschitz continuous coefficients
• Some results on the complexity of numerical integration
• Disintegration of Gaussian measures and average-case optimal algorithms
• Learning the random variables in Monte Carlo simulations with stochastic gradient descent: Machine learning for parametric PDEs and financial derivative pricing
• Lower Bounds for the Number of Random Bits in Monte Carlo Algorithms
• Optimal numerical integration and approximation of functions on \(\mathbb{R}^d\) equipped with Gaussian measure

This page was built for publication: Infinite-dimensional quadrature and approximation of distributions

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