1
$\begingroup$

I recently stumbled over Poisson Disk Sampling (here and the meditative version). I wonder if it is an alternative to crude or quasi Monte Carlo for very high dimensional integrals. It is not mentioned in Glasserman's Monte Carlo Methods so I suspect there is some draw-back.

Questions

  1. What is known about convergence rates when using Poisson Disk sampling for high dimensional cubature (d>100)?
  2. How efficient is the creation of Poisson Disk Samples for high dimensional domains?
  3. Is it an alternative to Quasi Monte Carlo methods such as Sobol or Halton sequences? If not, why not?
$\endgroup$
  • $\begingroup$ MC sits on top of a set of numbers. If they are random, we have montecarlo. If you use a grid, then it maps to being a quadrature. The problem with grids is that when you project them onto the lower dimensions of the problem, they do not sample the space evenly. When you do this in 2d it is simple to solve, since you can rotate the grid. As you increase the number of dimensions it gets harder. Sobol/halton/other low discrepency sequences go a long way towards solving this. $\endgroup$ – will Jul 16 '16 at 9:31
  • $\begingroup$ I have to admit I fail to see the connection of your comment with Poisson Disk Sampling. Care to elaborate? $\endgroup$ – g g Jul 17 '16 at 8:47
  • $\begingroup$ I'm saying that it's not an alternative to montecarlo. It is just another way of sampling an N dimensional space, which should sample the space more evenly. $\endgroup$ – will Jul 17 '16 at 18:47
  • $\begingroup$ This might be moved to crossvalidated. $\endgroup$ – Quartz Jul 19 '16 at 13:11
2
$\begingroup$

The classical and naïve procedure for generating Poisson Hypersphere samples is by acceptance rejection, which has complexity over $O(N^2)$ and is thus unfeasible for most practical usage with on-the-fly generation. This cost could be improved by space partitioning techniques at low dimensions, but at high ones afaik they become useless again with uniform distributions. Poisson disc sampling is thus not used widely beyond dimension 10, and I fear in general it is not a meaningful method in high dimensions because of geometric issues, which are conveniently bypassed by standard low discrepancy sequences (e.g. the fact that most of the hypercube volume is near the boundary). Another drawback w.r.t. some quasi-MC sequences is that smoothness of the integrand is not exploited and thus convergence can be significantly slower.

Similar in spirit is optimal quantization which is performed on arbitrary nonuniform distributions (by Pages, Callegaro &c). It has useful properties but suffers from even worse practical drawbacks (often points must be precomputed).

Imho the way to go is quasi-MC, there are sophisticated modern methods which beat anything else by a wide margin, in particular when used with proper integrand adaptations.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Interesting! How does QMC bypass the fact that most of the hypercube volume is near the boundary? And why does Poisson Sphere(or Ball?) sampling fail in this respect? Do you have a reference for this? $\endgroup$ – g g Jul 22 '16 at 15:10
  • $\begingroup$ I meant that the boundary issue is a problem with implementing properly Poisson Ball sampling, additional to the avoidance of balls among themselves; somehow the two distances - radial and orthogonal - don't mix well together. QMC simply focuses on orthogonal well-distribution which by itself can grant some degree of "diagonal" well-distribution, some (but not the simplest) methods further avoid diagonal clumping by more coherent means. Consider e.g. random points each in a different grid's cell: 2 neighbors might still risk vicinity, as a set there's uniform distribution and good avoidance. $\endgroup$ – Quartz May 24 '18 at 12:38

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.