Why Poisson Disk Sampling Is Unsuitable for High-Dimensional Integration
Summary
The document evaluates whether Poisson disk sampling can serve as an alternative to crude Monte Carlo or quasi-Monte Carlo for high-dimensional integration. It identifies practical obstacles in generating samples: naïve rejection sampling has quadratic cost in the number of points, while spatial partitioning methods lose usefulness at high dimensions. The answer also argues that geometric properties of high-dimensional spaces make the approach poorly suited to such problems.
Compared with low-discrepancy sequences such as Sobol or Halton, Poisson disk sampling is said not to exploit smoothness in the integrand, which can lead to slower convergence. Optimal quantization is mentioned as a related approach, but it too has practical limitations because samples may need to be precomputed. The response favors quasi-Monte Carlo with suitable integrand adaptations. It gives qualitative guidance rather than convergence-rate measurements or benchmarks, so the recommendation is not supported by numerical comparisons in the document.
Key ideas
- Naïve rejection sampling for Poisson disk points has quadratic cost in the number of points.
- Spatial partitioning can help at low dimensions but is described as ineffective in very high dimensions.
- Poisson disk sampling does not exploit integrand smoothness in the way some quasi-Monte Carlo methods can.
- The response recommends adapted quasi-Monte Carlo methods, while providing no numerical convergence comparisons.
Tags
Full text
# Is Poisson Disk Sampling an alternative to crude Monte Carlo and QMC? # Is Poisson Disk Sampling an alternative to crude Monte Carlo and QMC? 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 - What is known about convergence rates when using Poisson Disk sampling for high dimensional cubature (d>100)? - How efficient is the creation of Poisson Disk Samples for high dimensional domains? - Is it an alternative to Quasi Monte Carlo methods such as Sobol or Halton sequences? If not, why not? ## Answer by Quartz (score 2) https://quant.stackexchange.com/a/28152 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.
Shown in full with attribution under the source's licence. Licence: CC BY-SA 4.0 (Stack Exchange)
This summary was written by Stratmill's research agent from the original; it is not a copy of the source.