Quasi Monte Carlo
September 1, 2015 — February 14, 2017
concurrency hell
Monte Carlo
probabilistic algorithms
pseudorandomness
Simplistically put, using a random, Monte Carlo style algorithm, but deterministically, by sampling at well-chosen points.
Key words: low discrepancy set/sequence.
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
- Quasi Monte Carlo introduction by Sasha Nikolov
- algorithmic complexity
- Practical example: Generating Hammersley point sets for image synthesis.
- Dirk Nuyens’ magic point shop contains “QMC point generators and generating vectors” (MATLAB/octave/C++)
- When Random Numbers Are Too Random: Low Discrepancy Sequences « The blog at the bottom of the sea
1 References
Beck. 1996. “Discrepancy Theory.” In Handbook of Combinatorics.
Chazelle. 2001. The discrepancy method: randomness and complexity.
Dick, Kuo, and Sloan. 2013. “High-Dimensional Integration: The Quasi-Monte Carlo Way.” Acta Numerica.
Kuipers, and Niederreiter. 2012. Uniform Distribution of Sequences.
Matousek. 2010. “Geometric Discrepancy: An Illustrated Guide.” Algorithms and Combinatorics.
Panneton, and L’Ecuyer. 2006. “Infinite-Dimensional Highly-Uniform Point Sets Defined via Linear Recurrences in \(\mathbb{F}_{2^w }\).” In Monte Carlo and Quasi-Monte Carlo Methods 2004.
Parlett. 1992. “Some Basic Information on Information-Based Complexity Theory.” Bulletin of the American Mathematical Society.
Schwab, and Stuart. 2012. “Sparse Deterministic Approximation of Bayesian Inverse Problems.” Inverse Problems.
Sobol’. 1966. “Distribution of Points in a Cube and Integration Nets.” Uspekhi Matematicheskikh Nauk.
Srinivasan. 2000. “Low-Discrepancy Sets for High-Dimensional Rectangles: A Survey.” Bulletin of the EATCS.
Stuart. 2010. “Inverse Problems: A Bayesian Perspective.” Acta Numerica.
Traub. 1988. “Information-Based Complexity.”
Wang, and Sloan. 2008. “Low Discrepancy Sequences in High Dimensions: How Well Are Their Projections Distributed?” Journal of Computational and Applied Mathematics.
Yang, Sindhwani, Avron, et al. 2014. “Quasi-Monte Carlo Feature Maps for Shift-Invariant Kernels.” arXiv:1412.8293 [Cs, Math, Stat].