[Implementation] "A Fast Fourier Transform for Fractal Approximations"

[StellaAthena]

Background

Generalized CNNs (often called "Group Equivariant CNNs") are CNNs that build non-Euclidean geometric priors into their architecture. Recently, these generalized CNNs have been successfully applied in a variety of spaces with a geometric group structure. One area where they've been notably ineffective is on fractal geometries.

Recent work in mathematical analysis has generalized the concept of a Fourier Transform to domains where the traditional definition is not applicable. Some of this work has focused on Fourier Transforms on fractal datasets, a domain where neural networks are known to struggle. I would like an implementation of the algorithm described in A Fast Fourier Transform for Fractal Approximations. I hope to use this fractal Fourier transform to compute CNN with a fractal geometry built in, allowing CNNs to be applied to new types of data where they are currently ineffective. This is primarily a theoretical pursuit for me, but I do have a dataset of independent interest to CS researchers that natively carries a fractal geometry. I plan to show that this "fractal CNN" is more effective on the dataset than a traditional CNN.

What to Implement?

The FFT algorithm described in the paper

Modifications

None

Related Papers/Frameworks

Optional reading on the applications to CNNs

On the Generalization of Equivariance and Convolution in Neural Networks to the Action of Compact Groups

Optional reading on fractal spectral theory Analysis of orthogonality and of orbits in affine iterated function systems Fourier duality for fractal measures with affine scales Orthogonal exponentials, translations, and Bohr completions

[dtch1997]

I have started working on this: see https://github.com/dtch1997/fractal-fft

Currently I need some way to test my implementation. I.e. an equivalent computation of Fractal FFT that is provably correct.

[tnwei]

Musings from a passerby: from a cursory search, there doesn't seem to be other comparable implementations available. Perhaps validating the implementation would require designing a series of test cases? Probably a lot easier said than done.

Or maybe @StellaAthena is more than happy to stick this on a FractalCNN head already.