Subgroup-based Rank-1 Lattice Quasi-Monte Carlo
This addresses a computational bottleneck for researchers and practitioners using Quasi-Monte Carlo methods in fields like integral approximation and Bayesian inference, offering a faster alternative to exhaustive search methods.
The paper tackles the time-consuming construction of generating vectors for rank-1 lattices in Quasi-Monte Carlo by proposing a closed-form method based on group theory, which reduces distinct pairwise distances and empirically generates near-optimal lattices with superior performance on integration and kernel approximation benchmarks.
Quasi-Monte Carlo (QMC) is an essential tool for integral approximation, Bayesian inference, and sampling for simulation in science, etc. In the QMC area, the rank-1 lattice is important due to its simple operation, and nice properties for point set construction. However, the construction of the generating vector of the rank-1 lattice is usually time-consuming because of an exhaustive computer search. To address this issue, we propose a simple closed-form rank-1 lattice construction method based on group theory. Our method reduces the number of distinct pairwise distance values to generate a more regular lattice. We theoretically prove a lower and an upper bound of the minimum pairwise distance of any non-degenerate rank-1 lattice. Empirically, our methods can generate a near-optimal rank-1 lattice compared with the Korobov exhaustive search regarding the $l_1$-norm and $l_2$-norm minimum distance. Moreover, experimental results show that our method achieves superior approximation performance on benchmark integration test problems and kernel approximation problems.