by Mayur Patel
In some sampling applications, such as financial simulations, the dimension of the model might not be known at the time of software implementation. In computer graphics, there are some path tracing implementations that use high-dimension sequences to vary the ray path through the scene. The exact depth of the ray path might not be known beforehand. As a result, there is an appetite for sample generators that do not require the dimension of the samples to be fixed.
The solution for these use cases has been the Sobol sequence, often used with Owen scrambling to improve its distribution of samples. The typical implementation uses tables that enable producing samples with tens of thousands of dimensions, which is sufficient for most use cases. In this post, I'll present an alternative: a Kronecker sequence that can produce samples in arbitrary dimensions without a lookup table.
Kronecker Sequences
A Kronecker sequence is defined by {$n \cdot \alpha$} where n is the index of the value in the sequence, $\alpha$ is an irrational number and the {} operation indicates the fractional part of the product, or $(n \cdot \alpha) \bmod 1$. In dimensions greater than one, linearly independent irrationals are used and each dimension can be calculated independently using the same formula. Kronecker sequences are fast to calculate and the code is simple and compact.
In one dimension, the golden ratio is the irrational value known to produce the lowest discrepancy. In dimensions higher than one, there isn't a great deal of theory to help us pick useful concrete values for the irrationals that will drive high-quality variants of the sequence.
From previous work, I found sets of irrationals empirically that perform well in specific dimensions. Roberts had previously presented a generalization of the golden ratio for generating Kronecker sequences. In that case, the dimension is fixed because the irrationals are calculated as a function of the dimension. There aren't a lot of battle-tested methods for selecting irrationals that will scale to high dimensions when the dimension is not known beforehand.
New Irrationals for Use with Kronecker Sequences
In this post, I am presenting a method for generating a Kronecker sequence for arbitrary dimensions. I propose that we use this sequence to generate the irrational value to be used for each dimension:
$\alpha_s = \frac{1}{(s + 2 + \sqrt{7/251})}$
where s is the zero-based index indicating the dimension, $s \ge 0$
While this form is easy to implement in software, each element of the sequence does have an equivalent quadratic irrational form:
$\alpha_s$ = { $\frac{502 - \sqrt{1757}}{997}$, $\frac{753 - \sqrt{1757}}{2252}$, .... }
which means that each element also has a periodic continued fraction representation:
$\alpha_s$ = { $[0; 2, 5, \overline{1, 82, 1, 10}]$, $[0; 3, 5, \overline{1, 82, 1, 10}]$, .... }
A Kronecker sequence implementation that retrieves the irrational values from a cache or table will be extremely fast, while also being compact in RAM by the standards of modern applications; however, a generalized sample generator could be implemented with a 2-line function without a table or cache for applications that require extremely compact coding.
Here is a high-precision, stateless, table-free implementation which also supports Cranley-Patterson rotation for randomization of the sequence:
Require: integer32 index, zero-based index of the requested value
1: integer32 alpha ← pow(2, 32) / (2 + dim + sqrt(7/251));
2: return pow(2, -32) * float32(
How I discovered this sequence of irrationals is beyond the scope of a brief blog post; however, it suffices to say that I used methods similar to those outlined in my previous paper. By the same arguments made there, we can't say that this is an "optimal" Kronecker sequence in any sense, but that it might be a "useful" sequence for particular kinds of sampling applications.
Properties of the New Kronecker Sequence
As you might expect from a method that should scale to arbitrary dimensions, using these irrationals to drive a Kronecker sequence produces samples with relatively nice lower-dimension projections. For example, here are the first 1024 samples for several 2d projections:
I used Diaphony and Unanchored L2 Discrepancy metrics to evaluate the quality of the new Kronecker sequence. In previous work, I found the Unanchored L2 Discrepancy to be a leading metric for estimating real-world performance under a variety of 2D sampling circumstances. The Kronecker sequence did not outperform the Sobol sequence with Owen scrambling in the lowest dimensions, but for 8 dimensions and better, the performance was comparable.
This suggests that the Kronecker sequence could perform well for high-dimension sampling applications.
Conclusions
Just because we can produce samples in arbitrary dimensions does not mean that all our sampling challenges are solved. Theory tells us that we should use a minimum number of samples that increases geometrically with dimension. For example, to sample a 64-dimensional space, we would need at least $2^{64}$ samples. This is obviously computationally prohibitive. As a result, dimension-reduction methods are important for practical applications.
Nonetheless, I think you'll find the Kronecker sequence presented here to be easy to apply and useful in practice. Try it out in your own sampling applications to see whether it works well for you.
Comments
Post a Comment