In numerical analysis, low-discrepancy sequences play a crucial role. They are special sequences of points in a d-dimensional unit hypercube ([0,1]^d) designed to distribute themselves as uniformly as possible within that space.
Here's a breakdown of the key aspects:
Discrepancy: This refers to how well a set of points fills the space. A low discrepancy for a sequence's first N points (N being a subsequence length) signifies that the proportion of points falling within any arbitrary subset B closely resembles the volume of B relative to the whole hypercube. This is in contrast to a purely random sequence, where some regions might be under or over-represented by chance.
Properties: Low-discrepancy sequences, also known as quasi-random sequences, possess properties similar to random sequences but with a more uniform distribution. They are not truly random, but their design offers advantages in specific applications.
Generators: Low-discrepancy sequence generators are algorithms that produce these special sequences. Well-known examples include Sobol sequences, Halton sequences, and Faure sequences. Each generator employs a distinct method to construct the sequence, often relying on prime numbers and radical inverses for point generation within each dimension.
Applications: Low-discrepancy sequences find use in various areas, particularly in:
Numerical Integration: By distributing points more evenly, these sequences can improve the accuracy of numerical integration methods like quasi-Monte Carlo (QMC).
High-Dimensional Sampling: In high-dimensional spaces, low-discrepancy sequences can ensure a better exploration of the space compared to random sampling approaches.
In the code example, from top to bottom, a low order output bit of a Linear Congruence generator, a Xor Shift generator and an Additive Recurrence generator, together with a 2d plot of the Walsh Hadamard transform to the right.
Random projections obtained from completely random sign flippling followed by the Walsh Hadamard transform do not retain positional information of say clumped data within the input such as a translated circle. If used with a neural network that gives the neural network far more work to do. A solution is to utilize a sub-random projection using a low discrepancy sequence of sign flips.
It seems like the Xor Shift generator wins, subject to further experimentation with the various parameters.