Heuristic approaches to obtain low-discrepancy point sets via subset selection
Abstract
Building upon the exact methods presented in our earlier work [J. Complexity, 2022], we introduce a heuristic approach for the star discrepancy subset selection problem. The heuristic gradually improves the current-best subset by replacing one of its elements at a time. While the heuristic does not necessarily return an optimal solution, we obtain very promising results for all tested dimensions. For example, for moderate
sizes $30 \leq n \leq 240$, we obtain point sets in dimension 6 with
$L_{\infty}$ star discrepancy up to 35\% better than that of the first $n$ points of the Sobol' sequence. Our heuristic works in all dimensions, the main limitation being the precision of the discrepancy calculation algorithms.
We provide a comparison with a recent energy functional introduced by Steinerberger [J. Complexity, 2019], showing that our heuristic performs better on all tested instances. Finally, our results and complementary experiments also give further empirical information on inverse star discrepancy conjectures.
Origin | Files produced by the author(s) |
---|