A RANDOM INTEGRATION ALGORITHM FOR HIGH-DIMENSIONAL FUNCTION SPACES

doi:10.1090/mcom/4171

A RANDOM INTEGRATION ALGORITHM FOR HIGH-DIMENSIONAL FUNCTION SPACES

2025-12-01

0

PRE

AI

DOI：10.1090/mcom/4171

Original

Original request for help

Save

Abstract

En 中文

We introduce a novel random integration algorithm that exhibits a high convergence order for functions characterized by sparse frequencies or rapidly decaying Fourier coefficients. Specifically, for integration in periodic isotropic Sobolev spaces and isotropic Sobolev spaces with compact support, our approach achieves a nearly optimal root mean square error bound. In contrast to previous nearly optimal algorithms, our method exhibits polynomial tractability. Our integration algorithm also enjoys nearly optimal bound for weighted Sobolev space. By incorporating the trick of change of variable, our algorithm is proven to achieve the semi-exponential convergence order for the integration of analytic functions, which marks a significant improvement over the previously obtained super-polynomial convergence order. Furthermore, for integration involving Wiener-type functions, the sample complexity of our algorithm remains independent of the decay rate of the Fourier coefficients.

Keywords:

Numerical integration

Monte Carlo

curse of dimensionality

sample complexity

information-based complexity

A RANDOM INTEGRATION ALGORITHM FOR HIGH-DIMENSIONAL FUNCTION SPACES

Abstract

Journal

Organization