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, others? Do Gray codes, fit in here? If you aren’t doing this incrementally you can pre-generate a point set rather than a sequence.

See

Beck, József. 1996. “Discrepancy Theory.” In Handbook of Combinatorics, edited by Vera T Sós. Vol. 2. MIT Press, Cambridge, MA.

Chazelle, Bernard. 2001. The Discrepancy Method: Randomness and Complexity. 1st paperback ed. Cambridge: Cambridge Univ. Press. http://www.cs.princeton.edu/~chazelle/book.html.

Dick, Josef, Frances Y. Kuo, and Ian H. Sloan. 2013. “High-Dimensional Integration: The Quasi-Monte Carlo Way.” Acta Numerica 22 (May): 133–288. https://doi.org/10.1017/S0962492913000044.

Kuipers, L., and H. Niederreiter. 2012. Uniform Distribution of Sequences. Dover Publications.

Matousek, Jiri. 2010. “Geometric Discrepancy: An Illustrated Guide.” Algorithms and Combinatorics 18. http://library.wur.nl/WebQuery/clc/1249742.

Panneton, François, and Pierre L’Ecuyer. 2006. “Infinite-Dimensional Highly-Uniform Point Sets Defined via Linear Recurrences in $\mathbb{}F{}_{2ŵ }$.” In Monte Carlo and Quasi-Monte Carlo Methods 2004, edited by Harald Niederreiter and Denis Talay, 419–29. Springer Berlin Heidelberg. https://doi.org/10.1007/3-540-31186-6_25.

Parlett, Beresford N. 1992. “Some Basic Information on Information-Based Complexity Theory.” Bulletin of the American Mathematical Society 26 (1): 3–27. http://www.ams.org/bull/1992-26-01/S0273-0979-1992-00239-2/.

Schwab, C., and A. M. Stuart. 2012. “Sparse Deterministic Approximation of Bayesian Inverse Problems.” Inverse Problems 28 (4): 045003. https://doi.org/10.1088/0266-5611/28/4/045003.

Sobol’, Il’ya Meerovich. 1966. “Distribution of Points in a Cube and Integration Nets.” Uspekhi Matematicheskikh Nauk 21 (5): 271–72. http://www.mathnet.ru/eng/rm5932.

Srinivasan, Aravind. 2000. “Low-Discrepancy Sets for High-Dimensional Rectangles: A Survey.” Bulletin of the EATCS 70: 67–76. http://www.cs.umd.edu/~srin/PDF/disc-survey.pdf.

Stuart, A. M. 2010. “Inverse Problems: A Bayesian Perspective.” Acta Numerica 19: 451–559. https://doi.org/10.1017/S0962492910000061.

Wang, Xiaoqun, and Ian H. Sloan. 2008. “Low Discrepancy Sequences in High Dimensions: How Well Are Their Projections Distributed?” Journal of Computational and Applied Mathematics 213 (2): 366–86. https://doi.org/10.1016/j.cam.2007.01.005.

Yang, Jiyan, Vikas Sindhwani, Haim Avron, and Michael Mahoney. 2014. “Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels,” December. http://arxiv.org/abs/1412.8293.