Exact cubature for a class of functions of maximum effective dimension

DOI10.1016/J.JCO.2006.04.002MaRDI QIDQ855894zbMATH OpenOpenAlexFDO

Authors Shu Tezuka, A. Papageorgiou

Publication date 7 December 2006

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

Full work available at URL https://doi.org/10.1016/j.jco.2006.04.002

zbMATH Keywords

algorithmanalysis of varianceANOVAantisymmetric functionsconvergenceeffective dimensionfinancehigh-dimensional integralsquasi-Monte Carlo methodworst case error

Mathematics Subject Classification ID

Monte Carlo methods (65C05) Numerical integration (65D30) Numerical methods (including Monte Carlo methods) (91G60)

Review text

A functional class with maximum effective dimension is considered. The notion of effective dimensions is developed for the purpose of explaining why the quasi-Monte Carlo (QMC) method beats the Monte Carlo method by a wide margin for some high-dimensional integration problems in finance. In section 2 the ANOVA (analysis of variance) decomposition of a function of \(d\) variables is reminded. The terms of this decomposition are defined in a recursive way. The variance of a function of \(d\) variables is given. Two ways of the definition of the effective dimension in a truncation sense and in a superposition sense are reminded by the authors. The notion of effective dimension aims at measuring how important each subset of variables on the function is. In section 3 the functional class \({\mathcal F}_{d}\) is introduced. The elements of the ANOVA decomposition of the functions of this class are shown. Theorem 1 confirms that the effective dimension of any non-constant function \(f \in {\mathcal F}_{d}\), either in the truncation or in the superposition sense, is equal to \(d.\) It is shown that although the effective dimension of all functions in the class \({\mathcal F}_{d}\) is \(d,\) they can be integrated exactly by a cubature with two points. Theorem 2 gives that there exists an exact cubature with two points for the integration of any functions of the class \({\mathcal F}_{d}.\) The two points are in the form \((x_{1}, x_{2}, \ldots , x_{d}) \in [0,1]^{d}\) and \((1 - x_{1}, x_{2}, \ldots , x_{d}) \in [0,1]^{d}\) with deterministic point \((x_{1}, x_{2}, \ldots , x_{d}) \in [0,1]^{d}.\) In this way it is shown that both the convergence of QMC does not depend on the effective dimension and its worst case error can be zero for the functions of maximum effective dimension. The paper ends with a discussion. The problem for a restriction of the class \({\mathcal F}_{d}\) caused on the zero algorithm which is optimal is considered.

Recommendations

• On the necessity of low-effective dimension
• Simple cubature formulas with high polynomial exactness
• Cubature formulas for function spaces with moderate smoothness
• scientific article; zbMATH DE number 1894664
• When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?

Cites work

• Finite-order weights imply tractability of linear multivariate problems
• Finite-order weights imply tractability of multivariate integration
• Global sensitivity indices for nonlinear mathematical models and their Monte Carlo estimates
• scientific article; zbMATH DE number 3688714 (Why is no real title available?)
• scientific article; zbMATH DE number 1222809 (Why is no real title available?)
• scientific article; zbMATH DE number 1246220 (Why is no real title available?)
• scientific article; zbMATH DE number 1790429 (Why is no real title available?)
• scientific article; zbMATH DE number 1894664 (Why is no real title available?)
• scientific article; zbMATH DE number 1425054 (Why is no real title available?)
• scientific article; zbMATH DE number 2237872 (Why is no real title available?)
• Liberating the weights
• Monte Carlo Variance of Scrambled Net Quadrature
• On the necessity of low-effective dimension
• Sufficient conditions for fast quasi-Monte Carlo convergence
• The error bounds and tractability of quasi-Monte Carlo algorithms in infinite dimension
• Tractability of multivariate integration for weighted Korobov classes
• When are quasi-Monte Carlo algorithms efficient for high dimensional integrals?
• Why Are High-Dimensional Finance Problems Often of Low Effective Dimension?

Cited in

(10)

• Romberg extrapolation for Euler summation-based cubature on regular regions
• The effective dimension and quasi-Monte Carlo integration
• Stable high-order randomized cubature formulae in arbitrary dimension
• Efficient and Practical Implementations of Cubature on Wiener Space
• scientific article; zbMATH DE number 634017 (Why is no real title available?)
• Effective dimension of some weighted pre-Sobolev spaces with dominating mixed partial derivatives
• scientific article; zbMATH DE number 1894664 (Why is no real title available?)
• Cubature, approximation, and isotropy in the hypercube
• Estimating Mean Dimensionality of Analysis of Variance Decompositions
• Sparse grid quadrature in high dimensions with applications in finance and insurance

This page was built for publication: Exact cubature for a class of functions of maximum effective dimension

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