Fast Generation of Space-filling Latin Hypercube Sample Designs

摘要

Latin Hypercube Sampling (LHS) and Jittered Sampling (JS) both achieve better convergence than standard Monte Carlo Sampling (MCS) by using stratification to obtain a more uniform selection of samples, although LHS and JS use different stratification strategies. The "Koksma-Hlawka-like inequality" bounds the error in a computed mean in terms of the sample design's discrepancy, which is a common metric of uniformity. However, even the "fast" formulas available for certain useful L_2 norm discrepancies require O (N~2M) operations, where M is the number of dimensions and N is the number of points in the design. It is intuitive that "space-filling" designs will have a high degree of uniformity. In this paper we propose a new metric of the space-filling property, called "Binning Optimality," which can be evaluated in O (N log(N) operations. A design is "Binning Optimal" in base b, if when you recursively divide the hypercube into b~M congruent disjoint sub-cubes, each sub-cube of a particular generation has the same number of points until the sub-cubes are small enough that they all contain either 0 or 1 points. The O (N log(N)) cost of determining if a design is binning optimal comes from quick-sorting the points into Morton order, i.e. sorting the points according to their position on a space-filling Z-curve. We also present a O (N log(N)) fast algorithm to generate Binning Optimal Symmetric Latin Hypercube Sample (BOSLHS) designs. These BOSLHS designs combine the best features of, and are superior in several metrics to, standard LHS and JS designs. Our algorithm takes significantly less than 1 second to generate M = 8 dimensional space-filling LHS designs with TV = 216 = 65536 points compared to previous work which requires "minutes" to generate designs with Ar = 100 points.