2
$\begingroup$

Referring to the Halton Sequence, Swiler et al 2006 state that

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.

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.

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.

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?

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?

Here is an example in R:

library(randtoolbox)
samps <- 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

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 (pdf)

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.

$\endgroup$
  • 1
    $\begingroup$ It seems like some of your questions (especially with regard to a leaped Halton sequence) might be answered in Kocis and Whiten, Computational investigations of low-discrepancy sequences, ACM Transactions on Mathematical Software 23 (1997) pp. 266-294. $\endgroup$ – Andrew T. Barker May 23 '12 at 19:41
  • $\begingroup$ There is a lot of work out there extending the Sobol sequence to high dimensions, which may of relevance. $\endgroup$ – oliversm Aug 13 at 9:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.