Monte Carlo sampling high dimensions with the halton sequence? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T08:29:21Z http://mathoverflow.net/feeds/question/97700 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/97700/monte-carlo-sampling-high-dimensions-with-the-halton-sequence Monte Carlo sampling high dimensions with the halton sequence? David LeBauer 2012-05-22T21:07:57Z 2012-05-25T14:31:45Z <p>Referring to the Halton Sequence, <a href="https://cfwebprod.sandia.gov/cfdocs/CCIM/docs/AIAASDMpaper49843.pdf" rel="nofollow">Swiler et al 2006</a> state that </p> <blockquote> <p>In cases where a large number of input variables are sampled, Robinson and Atcitty recommend using a leaped sequence, where the user does not use every term in the Halton sequence but sets a “leap value” to the next prime number larger than the largest prime base. Using the leaped values in the sequence can help maintain uniformity when generating sample sets for high dimensions.</p> </blockquote> <p>I can not track down the Robinson and Atcitty (1999) reference. But I am curious what the limitations are of using the Halton sequence to generate a quasi-random sample from an $n$-dimensional parameter space. </p> <p>I am trying to minimize the number of samples required to estimate a response surface. To do this, I have been taking ~500 to 1000 samples from a set of 15-20 parameters. </p> <p>How can I tell if I am having issues with uniformity with my sample - is there a simple visualization or other analysis? Are there alternative algorithms that do not have this problem? What options do I have other than reducing the dimension of parameter space or increasing the number of samples?</p> <p>Also, (what is and) how do I implement a "leaped sequence". If I have an $n\times m$ matrix of samples from a Halton sequence, can I just delete specific rows? </p> <p>Here is an example in R:</p> <pre><code>library(randtoolbox) samps &lt;- halton(n = 500, dim = 15) head(signif(samps,3)) [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [,11] [1,] 0.500 0.333 0.20 0.143 0.0909 0.0769 0.0588 0.0526 0.0435 0.0345 0.0323 [2,] 0.250 0.667 0.40 0.286 0.1820 0.1540 0.1180 0.1050 0.0870 0.0690 0.0645 [3,] 0.750 0.111 0.60 0.429 0.2730 0.2310 0.1760 0.1580 0.1300 0.1030 0.0968 [4,] 0.125 0.444 0.80 0.571 0.3640 0.3080 0.2350 0.2110 0.1740 0.1380 0.1290 [5,] 0.625 0.778 0.04 0.714 0.4550 0.3850 0.2940 0.2630 0.2170 0.1720 0.1610 [6,] 0.375 0.222 0.24 0.857 0.5450 0.4620 0.3530 0.3160 0.2610 0.2070 0.1940 [,12] [,13] [,14] [,15] [1,] 0.0270 0.0244 0.0233 0.0213 [2,] 0.0541 0.0488 0.0465 0.0426 [3,] 0.0811 0.0732 0.0698 0.0638 [4,] 0.1080 0.0976 0.0930 0.0851 [5,] 0.1350 0.1220 0.1160 0.1060 [6,] 0.1620 0.1460 0.1400 0.1280 </code></pre> <hr> <p>Swiler, L. P., Slepoy R., and Giunta, A. A., “Evaluation of Sampling Methods in Constructing Response Surface Approximations,” paper AIAA-2006-1827 in Proceedings of the 47th AIAA/ASME/ASCE/AHS/ASC Structures, Structural Dynamics, and Materials Conference (2nd AIAA Multidisciplinary Design Optimization Specialist Conference), Newport, Rhode Island, 2006 <a href="https://cfwebprod.sandia.gov/cfdocs/CCIM/docs/AIAASDMpaper49843.pdf" rel="nofollow">(pdf)</a></p> <p>Robinson, D.G. and C. Atcitty, 1999. "Comparison of Quasi- and Pseudo-Monte Carlo Sampling for Reliability and Uncertainty Analysis." Proceedings of the AIAA Probabilistic Methods Conference, St. Louis MO, AIAA99-1589.</p>