2
$\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?
Improve this question
$\endgroup$
4
  • $\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
    Commented Jul 16, 2016 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
    Commented Jul 17, 2016 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
    Commented Jul 17, 2016 at 18:47
  • $\begingroup$ This might be moved to crossvalidated. $\endgroup$
    – Quartz
    Commented Jul 19, 2016 at 13:11

1 Answer 1

Reset to default
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$
2
  • $\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
    Commented Jul 22, 2016 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
    Commented May 24, 2018 at 12:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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