Timezone: »

Subgroup-based Rank-1 Lattice Quasi-Monte Carlo
Yueming LYU · Yuan Yuan · Ivor Tsang

Tue Dec 08 09:00 PM -- 11:00 PM (PST) @ Poster Session 2 #662
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 property for point set construction. However, the construction of the generating vector of the rank-1 lattice is usually time-consuming through 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 near-optimal rank-1 lattice compared with 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 the benchmark integration test problems and the kernel approximation problems.

Author Information

Yueming LYU (University of Technology Sydney)
Yuan Yuan (MIT)
Ivor Tsang (University of Technology, Sydney)

More from the Same Authors