Component-by-component construction of randomized rank-1 lattice rules achieving almost the optimal randomized error rate
Component-by-component construction of randomized rank-1 lattice rules achieving almost the optimal randomized error rate
复制标题
DOI：
10.1090/mcom/3769
复制
发表时间：
2021-09
期刊：
影响因子：
--
通讯作者：
J. Dick;T. Goda;Kosuke Suzuki
中科院分区：
文献类型：
--
作者：
J. Dick;T. Goda;Kosuke Suzuki
我们研究了一种随机求积算法来近似在高维单位立方体上定义的周期函数的积分。 Kritzer、Kuo、Nuyens 和 Ullrich（2019）最近的工作表明，具有随机选择的点数和良好生成向量的 1 阶晶格规则几乎可以实现加权 Korobov 空间中随机误差的最佳阶，而且，如果权重参数 $\gamma_j$ 满足可求和条件，则误差与维度无关。 $\sum_{j=1}^{\infty}\gamma_j^{1/\alpha}<\infty$，其中$\alpha$是平滑参数。该论证基于以下存在性结果：至少一半的可能生成向量在相同函数空间中产生几乎最坏情况误差的最佳顺序。在本文中，我们提供了这种随机Rank-1格子规则的逐个组件构造算法，无需检查构造的生成向量是否满足所需的最坏情况误差界限。与上述工作类似，我们证明，如果相同条件 $\sum_{j=1}^{\infty}\gamma_j^{1/\alpha}<\infty$ 成立，我们的算法几乎实现了随机误差的最佳顺序，并且误差范围与维度无关。我们还分别为加权半周期余弦空间的帐篷变换晶格规则和加权沃尔什空间中的多项式晶格规则提供了类似的结果。
We study a randomized quadrature algorithm to approximate the integral of periodic functions defined over the high-dimensional unit cube. Recent work by Kritzer, Kuo, Nuyens and Ullrich (2019) shows that rank-1 lattice rules with a randomly chosen number of points and good generating vector achieve almost the optimal order of the randomized error in weighted Korobov spaces, and moreover, that the error is bounded independently of the dimension if the weight parameters, $\gamma_j$, satisfy the summability condition $\sum_{j=1}^{\infty}\gamma_j^{1/\alpha}<\infty$, where $\alpha$ is a smoothness parameter. The argument is based on the existence result that at least half of the possible generating vectors yield almost the optimal order of the worst-case error in the same function spaces. In this paper we provide a component-by-component construction algorithm of such randomized rank-1 lattice rules, without any need to check whether the constructed generating vectors satisfy a desired worst-case error bound. Similarly to the above-mentioned work, we prove that our algorithm achieves almost the optimal order of the randomized error and that the error bound is independent of the dimension if the same condition $\sum_{j=1}^{\infty}\gamma_j^{1/\alpha}<\infty$ holds. We also provide analogous results for tent-transformed lattice rules for weighted half-period cosine spaces and for polynomial lattice rules in weighted Walsh spaces, respectively.