Random Integration Algorithm for High-dimensional Function Spaces

We introduce a novel random integration algorithm that boasts both high con<br />vergence order and polynomial tractability for functions characterized by sparse<br />frequencies or rapidly decaying Fourier coefficients. Specifically, for integration in<br />periodic isotropic Sobolev space and the isotropic Sobolev space with compact sup<br />port, our approach attains a near-optimal root mean square error. In contrast to<br />previous nearly optimal algorithms, our method exhibits polynomial tractability,<br />ensuring that the number of samples does not scale exponentially with increasing<br />dimensions. Our integration algorithm also enjoys near-optimal bound for weighted<br />Korobov space. Furthermore, the algorithm can be applied without the need for<br />prior knowledge of weights, distinguishing it from component-by-component algo<br />rithms. For integration in the Wiener algebra, the sample complexity of our algo<br />rithm is independent of the decay rate of Fourier coefficients. The effectiveness of<br />the integration is confirmed through numerical experiments.