I wrote some code to generate Latin hypercube samples for interpolation over high-dimensional parameter spaces. Latin hypercubes are essentially collections of points on a hypercube that are placed on a cubic/rectangular grid, which possess the property that no two points share any individual coordinate, and every row/column/higher-dimensional-axis is sampled once. e.g., for 2 dimensions and 4 total samples, this is a Latin hypercube:
| | | |x| | |x| | | |x| | | | | | |x| |
One algorithm for generating this is to generate D random permutations of the integers 0 through N-1, where D is the number of dimensions and N is the desired number of samples. Concatenating these together into a DxN matrix gives a list of coordinates which will form a Latin hypercube.
I am also interested in generating a special type of Latin hypercube called a symmetric Latin hypercube. This property essentially means that the hypercube is invariant under spatial inversion. One way of expressing this condition, is that (if the samples are zero-indexed) if the hypercube has the sample (i, j, ..., k), for some integer indices i,j,k, then it also has the sample (n-1-i, n-1-j, ..., n-1-k), where n is the number of samples. For 2D and n=4, this is an example of a symmetric Latin hypercube:
| |x| | | | | | |x| |x| | | | | | |x| |
The condensed version of why I want to do this is that I want to evaluate a function which is expensive to compute, and depends on many parameters. I pre-generate a list of values for this function at a set of points and use interpolation over the parameters to extend this list to any desired point within a set range. Latin hypercube samples are used for the pre-computation instead of a grid, with the idea that they will more efficiently sample the behavior of the function and result in lower interpolation errors.
I have tested the code below both using automated tests and by visual inspection of the results for the trivial 2D case. Statistical tests of higher dimensional cases have convinced me it works successfully there as well. The code can produce either random Latin hypercubes or a rather nongeneral set of symmetric ones (I am convinced my second algorithm cannot in principle generate any possible symmetric Latin hypercube, just a specific type). Also, the symmetric algorithm doesn't really work properly for odd numbers of samples, so I have outright blocked such samples from being generated.
My code can be seen along with specification and performance tests here, although not the visual tests at the moment.
I am aware that my project structure is probably overkill for the amount of code here. I am mostly looking for any insights regarding my algorithms, as while they are very fast even for large dimensions and sample sizes, I don't doubt improvements exist. However any comments are welcome.
import numpy as np class LatinSampler: def _check_num_is_even(self, num): if num % 2 != 0: raise ValueError("Number of samples must be even") def get_lh_sample(self, param_mins, param_maxes, num_samples): dim = param_mins.size latin_points = np.array([np.random.permutation(num_samples) for i in range(dim)]).T lengths = (param_maxes - param_mins)[None, :] return lengths*(latin_points + 0.5)/num_samples + param_mins[None, :] def get_sym_sample(self, param_mins, param_maxes, num_samples): self._check_num_is_even(num_samples) dim = param_mins.size even_nums = np.arange(0, num_samples, 2) permutations = np.array([np.random.permutation(even_nums) for i in range(dim)]) inverses = (num_samples - 1) - permutations latin_points = np.concatenate((permutations,inverses), axis=1).T lengths = (param_maxes - param_mins)[None, :] return lengths*(latin_points + 0.5)/num_samples + param_mins[None, :]
Edit: I glossed over this, but this code doesn't return Latin hypercubes per se, but rather Latin hypercubes stretched/squeezed and shifted so that the points can be over arbitrary ranges of values. However the core code will generate a Latin hypercube if the last manipulation (multiply by
lengths and add
param_mins) is omitted.