Quasi Monte Carlo

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

Key words: low discrepancy set/sequence.

Low discrepancy l2 balls covering a random field

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

Sobol nets, others? Do Gray codes, fit in here? If we aren’t doing this incrementally we can pre-generate a point set rather than a sequence.

See

References

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.
Dick, Josef, Frances Y. Kuo, and Ian H. Sloan. 2013. Acta Numerica 22 (May): 133–288.
Kuipers, L., and H. Niederreiter. 2012. Uniform Distribution of Sequences. Dover Publications.
Matousek, Jiri. 2010. Algorithms and Combinatorics 18.
Panneton, François, and Pierre L’Ecuyer. 2006. In Monte Carlo and Quasi-Monte Carlo Methods 2004, edited by Harald Niederreiter and Denis Talay, 419–29. Springer Berlin Heidelberg.
Parlett, Beresford N. 1992. Bulletin of the American Mathematical Society 26 (1): 3–27.
Schwab, C., and A. M. Stuart. 2012. Inverse Problems 28 (4): 045003.
Sobol’, Il’ya Meerovich. 1966. Uspekhi Matematicheskikh Nauk 21 (5): 271–72.
Srinivasan, Aravind. 2000. Bulletin of the EATCS 70: 67–76.
Stuart, Andrew M. 2010. Acta Numerica 19: 451–559.
Traub, J. F. 1988.
Wang, Xiaoqun, and Ian H. Sloan. 2008. Journal of Computational and Applied Mathematics 213 (2): 366–86.
Yang, Jiyan, Vikas Sindhwani, Haim Avron, and Michael Mahoney. 2014. arXiv:1412.8293 [Cs, Math, Stat], December.

No comments yet. Why not leave one?

GitHub-flavored Markdown & a sane subset of HTML is supported.