Butterflies Are All You Need: A Universal Building Block for Structured Linear Maps

Created: 2022-05-25T17:36:59-05:00

TODO link not implemented: => 1903.05895.pdf TODO actual whitepaper

The challenge is to find a parametrization that is capable of representing the above structured matrix classes, without using too many parameters.

Butterfly structure is basically a 2x2 matrix.

Values are projected through the butterfly matrix to process and recombine the halves.

Butterflies can be treated as a neural network problem and numerical optimization can "train" the butterfly matrices.

Able to immitate multiple discrete transforms using the same execution kernels at close to the same speeds of optimized implementations.

Can replace fully connected neural network sections with similarly performing ones with "40X less parameters."

FFT Function

• Separate even and odd inputs
• Recursively perform the FFT function on the new halves
• Recombine using a butterfly structure