|
|
|
|
|
|
by targafarian
2845 days ago
|
|
|
I'm curious why Sobol outperforms the R-sequence for numerical integration of an 8-dimensional Gaussian and whether that result holds in lower dimensions (and whether that's tied to the infintely-long-tailed nature of the Gaussian; maybe there's a bias in Sobol that is beneficial in this particular case...?). |
|
|
First is that the maths is far more complex than that of other sequences. Here is a the easiest description I have seen so far [1].
Secondly this complexity as well as the non-trivial requirement to carefully select the basis parameters means that the computing side is very very complex. To get an indication of its complexity, the code for Sobol generation in Mathematica and WolframAlpha is not done by Wolfram itself but rather "comes courtesy of the Intel MKL libraries,... Specifics of the implementation, such as choice of initial values, are not documented. Evaluation of this implementation in terms of discrepancy, projections, and performance in application remains for future work." [also 1]
Thirdly, as defined by d* discrepancy, ( which is by far the most common formal method of quatifying discrepancy) the Sobol sequence does not have an asymptotic discrepancy as low as many of other sequences.
Despite this last point, it has been found that in practice Sobol generally yields as good or better performance when used for numerical integrations.
I personally have a suspicion that this is because of the special property, called "Property A" [2] that all Sobol point sequences possess. However, I will let people much smarter than me comment on whether this belief is justified or not...
In one of my other posts [3], Sobol sequences outperform all of the other low discrepancy sequence (including my new R2 sequence) hands down.
Finally, please note that for brevity and clarity, my blog only shows one example for most topics. I will leave it to other authors, or future posts to more rigourously show how consistent the comparisons are....
[1] http://www.mathematica-journal.com/2011/12/a-toolbox-for-qua... [2] http://www.andreasaltelli.eu/file/repository/HD_SobolGenerat... [3] http://extremelearning.com.au/how-to-generate-a-sequence-of-...