Uniform Point Picking on a Sphere

An easy way to pick a point uniformly at random on the surface of a sphere is to generate three Gaussian random variables x, y, z.

Then the distribution of the vectors:

is uniform over the surface. For higher dimensional spheres the procedure is a simple extension.

A vector with random +1,-1 elements picks a point on the surface of a random hypercube.

The Central Limit Theorem applies to all the output values of the fast Walsh Hadamard transform of the random (+1,-1) vector.  Since the Central Limit Theorem applies not just to sums, also to differences and any mixture of the two.

The fast Walsh Hadamard transform just being patterns of addition and subtraction.  And the central limit theorem showing that additions and subtraction of random numbers from almost any random distribution results in random numbers from the Gaussian (Normal) distribution.

The fast Walsh Hadamard transform (scaled version) leaves vector length unchanged or only multiplied by a constant (unscaled version). It just rotates a vector point on the surface of a hypersphere to another point on the surface of the hypersphere.

Therefore the fast Walsh Hadamard transform applied to a random vector with random  (+1,-1) elements maps to some random point on the surface of an n dimensional hyper-sphere uniformly and to some degree of quantization. 

Quantization is involved because you only sum and difference a finite number of +1's and -1.

Starting with the all +1's vector (1,1,...1) and applying various sign flips you can approximate any linear mapping from the all +1's vector to some arbitrary point on the surface of the hyper-sphere to the quantization limit level of approximation. All linear mapping from the initial point are possible.

More generally you can hope to create an arbitrary linear mapping approximation of the vector (x0,x1,...xn) by multiplying with various parameters (p0x0, p1x1,..pnxn) followed by a fast Walsh Hadamard transform, where the parameters p0...pn could be chosen in some automated way, such as in SwitchNet.

For example if (x0,x1...xn) is non-sparse and even if p0 to pn are restricted to being +1 or -1 then an arbitrary linear mapping can be constructed to some level of quantization (accuracy.)

If (x0,x1,...xn) is non-sparse and p0 to pn are chosen randomly then the CLT applies to the outputs of the fast Walsh Hadamard transform applied to  (p0x0, p1x1,..pnxn) and so all linear mappings are possible to some accuracy.