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.

See

Refs

Beck96
Beck, J. (1996) Discrepancy theory. In V. T. Sós (Ed.), Handbook of combinatorics (Vol. 2). MIT Press, Cambridge, MA
DiKS13
Dick, J., Kuo, F. Y., & Sloan, I. H.(2013) High-dimensional integration: The quasi-Monte Carlo way. Acta Numerica, 22, 133–288. DOI.
Mato10
Matousek, J. (2010) Geometric discrepancy: An illustrated guide. Algorithms and Combinatorics, 18.
PaLe06
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.
Parl92
Parlett, B. N.(1992) Some basic information on information-based complexity theory. Bulletin of the American Mathematical Society, 26(1), 3–27.
ScSt12
Schwab, C., & Stuart, A. M.(2012) Sparse deterministic approximation of Bayesian inverse problems. Inverse Problems, 28(4), 045003. DOI.
Sobo66
Sobol’, I. M.(1966) Distribution of points in a cube and integration nets. Uspekhi Matematicheskikh Nauk, 21(5), 271–272.
Srin00
Srinivasan, A. (2000) Low-discrepancy sets for high-dimensional rectangles: a survey. Bulletin of the EATCS, 70, 67–76.
Stua10
Stuart, A. M.(2010) Inverse problems: A Bayesian perspective. Acta Numerica, 19, 451–559. DOI.
Trau88
Traub, J. F.(1988) Information-Based Complexity.
WaSl08
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.
YSAM14
Yang, J., Sindhwani, V., Avron, H., & Mahoney, M. (2014) Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels. arXiv:1412.8293 [Cs, Math, Stat].