Stochastic Generation of (t, s) Sample Sequences

Abstract

We introduce a novel method to generate sample sequences that are progressively stratified both in high dimensions and in lower-dimensional projections. Our method comes from a new observation that Owen-scrambled quasi-Monte Carlo (QMC) sequences can be generated as stratified samples, merging the QMC construction and random scrambling into a stochastic algorithm. This yields simpler implementations of Owen-scrambled Sobol', Halton, and Faure sequences that exceed the previous state-of-the-art sample-generation speed; we provide an implementation of Owen-scrambled Sobol' (0,2)-sequences in fewer than 30 lines of C++ code that generates 200 million samples per second on a single CPU thread. Inspired by pmj02bn sequences, this stochastic formulation allows multidimensional sequences to be augmented with best-candidate sampling to improve point spacing in arbitrary projections. We discuss the applications of these high-dimensional sequences to rendering, describe a new method to decorrelate sequences while maintaining their progressive properties, and show that an arbitrary sample coordinate can be queried efficiently. Finally we show how the simplicity and local differentiability of our method allows for further optimization of these sequences. As an example, we improve progressive distances of scrambled Sobol' (0,2)-sequences using a (sub)gradient descent optimizer, which generates sequences with near-optimal distances.