The Living Thing / Notebooks :

Quasi Monte Carlo

Simplistically put, using a random, Monte Carlo style algorithm, but deterministically, by sampling at well-chosen points.

Key words: discrepancy.

Some of the series of points used are nice for parallelised algorithms, by the way, in the same way that randomised algorithms are.

Low discrepancy sequences such as Sobol nets, Gray codes, others? If you aren’t doing this incrementally you can pre-generate a point set rather than a sequence.



Beck, J. (1996) Discrepancy theory. In V. T. Sós (Ed.), Handbook of combinatorics (Vol. 2). MIT Press, Cambridge, MA
Dick, J., Kuo, F. Y., & Sloan, I. H.(2013) High-dimensional integration: The quasi-Monte Carlo way. Acta Numerica, 22, 133–288. DOI.
Matousek, J. (2010) Geometric discrepancy: An illustrated guide. Algorithms and Combinatorics, 18.
Panneton, F., & L’Ecuyer, P. (2006) Infinite-Dimensional Highly-Uniform Point Sets Defined via Linear Recurrences in mathbb{F}_{2^w }. In H. Niederreiter & D. Talay (Eds.), Monte Carlo and Quasi-Monte Carlo Methods 2004 (pp. 419–429). Springer Berlin Heidelberg DOI.
Parlett, B. N.(1992) Some basic information on information-based complexity theory. Bulletin of the American Mathematical Society, 26(1), 3–27.
Schwab, C., & Stuart, A. M.(2012) Sparse deterministic approximation of Bayesian inverse problems. Inverse Problems, 28(4), 045003. DOI.
Sobol’, I. M.(1966) Distribution of points in a cube and integration nets. Uspekhi Matematicheskikh Nauk, 21(5), 271–272.
Srinivasan, A. (2000) Low-discrepancy sets for high-dimensional rectangles: a survey. Bulletin of the EATCS, 70, 67–76.
Stuart, A. M.(2010) Inverse problems: A Bayesian perspective. Acta Numerica, 19, 451–559. DOI.
Traub, J. F.(1988) Information-Based Complexity.
Wang, X., & Sloan, I. H.(2008) Low discrepancy sequences in high dimensions: How well are their projections distributed?. Journal of Computational and Applied Mathematics, 213(2), 366–386. DOI.
Yang, J., Sindhwani, V., Avron, H., & Mahoney, M. (2014) Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels. arXiv:1412.8293 [Cs, Math, Stat].