This work investigates the star discrepancies and squared integration errors of two quasi-random points constructions using a generator one-dimensional sequence and the Hilbert space-filling curve. This recursive fractal is proven to maximize locality and passes uniquely through all points of the d-dimensional space. The van der Corput and the golden ratio generator sequences are compared for random- ized integro-approximations of both Lipschitz continuous and piecewise constant functions. We found that the star discrepancy of the construction using the van der Corput sequence reaches the theoretical optimal rate when the number of samples is a power of two while using the golden ratio sequence performs optimally for Fibonacci numbers. Since the Fibonacci sequence increases at a slower rate than the exponential in base 2, the golden ratio sequence is preferable when the budget of samples is not known beforehand. Numerical experiments confirm this observation.
Schretter, C, He, Z, Gerber, M, Chopin, N & Niederreiter, H 2016, Van der Corput and Golden Ratio Sequences Along the Hilbert Space-Filling Curve. in R Cools & D Nuyens (eds), Monte Carlo and Quasi-Monte Carlo Methods: MCQMC, Leuven, Belgium, April 2014. Springer Proceedings in Mathematics & Statistics, vol. 163, Springer Verlag, pp. 531-544, Eleventh International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, Leuven, Belgium, 6/04/14.
Schretter, C., He, Z., Gerber, M., Chopin, N., & Niederreiter, H. (2016). Van der Corput and Golden Ratio Sequences Along the Hilbert Space-Filling Curve. In R. Cools, & D. Nuyens (Eds.), Monte Carlo and Quasi-Monte Carlo Methods: MCQMC, Leuven, Belgium, April 2014 (pp. 531-544). (Springer Proceedings in Mathematics & Statistics; Vol. 163). Springer Verlag.
@inproceedings{354886df8dd54784a5a31ce50c89a6cf,
title = "Van der Corput and Golden Ratio Sequences Along the Hilbert Space-Filling Curve",
abstract = "This work investigates the star discrepancies and squared integration errors of two quasi-random points constructions using a generator one-dimensional sequence and the Hilbert space-filling curve. This recursive fractal is proven to maximize locality and passes uniquely through all points of the d-dimensional space. The van der Corput and the golden ratio generator sequences are compared for random- ized integro-approximations of both Lipschitz continuous and piecewise constant functions. We found that the star discrepancy of the construction using the van der Corput sequence reaches the theoretical optimal rate when the number of samples is a power of two while using the golden ratio sequence performs optimally for Fibonacci numbers. Since the Fibonacci sequence increases at a slower rate than the exponential in base 2, the golden ratio sequence is preferable when the budget of samples is not known beforehand. Numerical experiments confirm this observation.",
keywords = "Hilbert curve, Discrepancy, Golden ratio sequence, Numerical integration",
author = "Colas Schretter and Zhijian He and Mathieu Gerber and Nicolas Chopin and Harald Niederreiter",
year = "2016",
language = "English",
isbn = "978-3-319-33505-6",
series = "Springer Proceedings in Mathematics & Statistics",
publisher = "Springer Verlag",
pages = "531--544",
editor = "Ronald Cools and Dirk Nuyens",
booktitle = "Monte Carlo and Quasi-Monte Carlo Methods",
address = "Germany",
note = "Eleventh International Conference on Monte Carlo and Quasi-Monte Carlo Methods in Scientific Computing, MCQMS ; Conference date: 06-04-2014 Through 11-04-2014",
}