There is a simple fast transform that was popular in the 1960s.
It was popular because it didn’t require a lot of compute.
Then everyone forgot about it.
It probably is time to start using the Walsh Hadamard transform (WHT) again, especially since a wider range of applications have been found for it since the 1960s.
The simplist application of the WHT is image compression:
https://editor.p5js.org/siobhan.491/sketches/BQcmEs9GM
It was used on some of the early space missions.
Reference:
https://www.kdnuggets.com/2021/07/wht-simpler-fast-fourier-transform-fft.html