Abstract:

We present a Multivariate Decomposition Method (MDM) for approximating integrals of functions with countably many variables. We assume that the integrands have mixed first order partial derivatives bounded in a γ = {γ_u }u⊂N+ -weighted Lp norm. We also assume that the integrands can be evaluated only at points with finitely many (d) coordinates different than zero and that the cost of such a sampling is equal to $(d) for a given cost function $. We show that MDM can approximate the integrals with the worst case error bounded by ε at cost proportional to −1+|O(ln(1/ε)/ ln(ln(1/ε)))| ε even if the cost function is exponential in d, i.e., $(d) = e^{O(d)}.  This is an almost optimal method since all algorithms for univariate functions (d = 1) from this space have the cost bounded from below by Ω(1/ε).