The case for Fast Transforms as Averaging Machines

Are Fast Transforms like the FFT and Walsh Hadamard transform averaging machines?


Certainly there is an all sum term such as A+B+C+D+E+F+G in the diagram which can be considered an average especially after vector length renormalization where all the output terms would typically be multiplied by 1/sqr(width), 1/sqr(8) in this case, to leave vector magnitude unchanged by the transform.

For a different input, say {+1,+1,-1,-1,-1,-1,+1,+1] the output term A+B-C-D-E-F+G+H becomes 1+1+1+1+1+1+1+1.  For that input pattern that particular output term becomes an averaging operation.


Degrees of freedom

For standard averaging of n values many different combinations of values can result in the same average. There are many degrees of freedom.

As you start demanding more and more output terms of a fast transform be particular values the degrees of freedom in the input shrink. Until, when you demand all the outputs be particular values, then only one exact input vector will give that result.

To get around that you can:

  • Use a wider transform than the wanted output vector.
  • Accept say a 1% output error tolerance which will restore some degree of freedom.
If you accept either of those 2 conditions then local errors in the input to the transform may be organized such that they cancel out globally.

For example there might be too few local parameters per function in a system of parametric functions for local errors to be cancelled out.

However the errors could be cancelled out globally by mutual cooperation of the local functions if they were all interconnected in some way.
And a fast transform can provide that connectivity.

As a practical matter you may want to remove the spectral bias of the transform (ie. a strong respose to certain sine and cosine waves) in this particular application. As you only need the connectivity behavior. You could consider a fixed random pattern of sign flips applied to the output of the transform to remove the bias. Or a sub-random pattern of sign flips.


Comments

Post a Comment

Popular posts from this blog

2 Siding ReLU via Forward Projections

Image
2 Siding ReLU via Forward Projections The ReLU acivation function in neural networks has special properties that allow it to be considered in a different way to other activation functions. The Switching Viewpoint You can view ReLU as being non-conducting when x<=0 and fully conducting when x>0.  It is a switch which is automatically turned on when x>0 and automatically turned off when x<=0. Which is an ideal rectifier in electrical engineering terms.  Hence the term  Rectified Linear Unit. A switch isn't there when it is on from the point of view of the flowing electricity (or analogous thing.)  Electricity flows through pushed together switch contacts the same as through the wires to the switch.  All the ReLUs in a neural network that are conducting, wire together various sub-components of the network. The wiring being complete the ReLUs become essentially invisible, until one or more ReLUs change state. Since neural networks are computed in a ...
Read more

Switch Net

Image
 Switch Net Switch Net. Switch Net is a neural network based on using the fast Walsh Hadamard tranform (WHT) as a fixed set of layer weights with a parametric switching based activation function. The cost of the WHT is nlog2(n) add subtracts as opposed to n squared fused multiply adds for a conventional dense neural layer's weight calculations. A fixed random pattern of sign flips is applied to the input data so that the first WHT fairly distributes information with a Gaussian distribution across its outputs. Then a switching decision is applied to each output of the WHT and the output is multiplied by one weight or another.  The section between the red lines is basically a layer and can be repeated a number of times. A final WHT is done to combine the last lot of switched weight outputs. Some example code is here: https://editor.p5js.org/congchuatocmaydangyeu7/sketches/7ekZTwQMF One slight issue is if the switching weights for a particular output have opposite signs then the ...
Read more

Artificial Neural Networks

Image
Artificial neural networks An artificial neuron. The basic behavior of an artificial neural network is determined by the dot product (weighted sum) operator in each neuron. This also has a geometric interpretation. The dot product of A and B is the magnitude (vector length) of vector A by the magnitude of vector B by the cosine of the angle between them.  Dot product video. To understand information storage in a weighted sum it helps to know the central limit theorem. Statistical properties of the dot product. The central limit theorem. If you store 1 <vector,scalar> association in a weighed sum the weight vector will point in the same direction as the input vector. Store 2 <vector,scalar> associations and both input vectors will point some angle away from the weight vector. As a result the scalar output will be more sensitive to small changes in the input vectors. A reduction in an initial mild error correction capacity. I...
Read more