12 Comments

PS #1: Apologies to all the folks who signed up for this after the xz article and didn't realize what's coming!

PS #2: Here's a person experimenting with Walsh-Hadamard for image compression: http://rotormind.com/blog/2019/hadamard-days-night/

Plus, some technical details about the spectrograms shown at the bottom. They were calculated with DCT and WHT from a 44.1 kHz mono audio file. Input sample window was 512 with a transform stepover of 1, producing an output array with dimensions around 512 x 485k. Pixel intensities correspond to normalized absolute values with a gamma of around 0.4 (i.e., pixel = fabs(orig_value / window_size) ^ 0.4)). The image was then resized with Lanczos resampling, and rendered with a linear black - sky blue - white colormap.

Expand full comment

In the classical FFT, the result includes real *and* imaginary parts, so...

Expand full comment

I want to get this straight in my head for future reference (it's been a while since I thought precisely about this type of thing). As someone coming from a chemistry background, I've worked with the frequency domain (though my hands-on with low-level implementations is limited, I did have some spectroscopy research projects where I had to use Fourier transforms more explicitly rather than just clicking a button). In general, we see it often in spectroscopy, or looking at electrons and atoms in molecules, reciprocal space and wave functions in crystallography and quantum chemistry, and more. Going a little deeper, things like electron spin behavior come to mind. Even lower, we know of the role of complex numbers and probability densities in quantum mechanics. But I see your point that in many cases we impose these constructs to make sense of signals analytically. Is that what you're saying, and am I looking at it through a similar lens to you? Does the claim that frequency domain space is just a construct hold up in more "fundamental" fields like chemistry and physics in your view? What does this say about our understanding of the world? I have some thoughts about this in relation to AI and human-computer interaction, and how theories shape our beliefs and how this might end up with us living in a world with coercive AI but that's for another post :) thanks for the gentle and intuitive post!

Expand full comment

"it’s just that discrete Fourier doesn’t have a monopoly on truth." this has many implications lol (ironically, over-reading and over-analyzing a comment about not over-analyzing a method).

Expand full comment

The entire article is essentially a stealth rant about the behavior highlighted at the beginning of this later article:

https://lcamtuf.substack.com/p/the-internets-knowledge-problem

It's less about epistemology and more about not using it as a crutch when more satisfying and less circular explanations are available.

Quantum physics is a separate can of worms because we no longer have particularly satisfying, intuitive models of what the universe is made out of. We essentially have abstract math with predictive power. Is the universe made out of math? Is there a deeper level we have no chance of measuring (string theory)? Anyway, when no better explanation is available, "because Fourier says so" is probably OK - especially when dealing with sine waves.

Expand full comment

This is a great article, but for future ones, could you use Rust instead of C for any code? Rust is now the preferred programming language for code examples.

Expand full comment

Looking at the recent Rust hype, if it’s a joke (and I think it is), than it’s a great one! :D

Expand full comment

No.

Expand full comment

Could you elaborate why? It is a reasonable request due to the safety of Rust.

Expand full comment

The thing about the internet is that it's very easy to bug strangers about your pet causes, but no single person has enough bandwidth to care for or debate every single cause they are bugged about.

The parent poster is not a subscriber, has no discernible online footprint, and put very little effort into justifying their request. Even on the off chance it's not a drive-by troll, I don't think it warrants a whole lot of debate.

To not sound like a complete ass, I'll bite - but only briefly. I'm using C in lieu of imperative pseudocode. The benefit it has over pure pseudocode is that it compiles and doesn't rely on some syntax I pulled out of nowhere. The benefit over higher-level languages is that it shows the mechanics of the calculation in a way that's trivial to transpose to any other dialect. This can't be said about code that uses cute but language-specific array manipulation and iteration idioms, e.g.:

WalshMatrix = Nest[ArrayFlatten@{{#, #}, {#, -#}} &, 1, #] &;

If you'd like to offer examples in your preferred language, feel free to share them in the comments below.

Expand full comment

A better question than the title of this piece would be "What other transforms can we imagine that help us understand things for which the DFT is of little help?" That we could choose other transforms and calculate them easily isn't all that interesting until we see the insights that those other transforms open for us.

Expand full comment

The specific thing that prompted me to write the article is folks on electronics-related subreddits uttering maxims like "square waves aren't real", "the real and correct explanation of impedance is that it's a Fourier transform of...", etc - in other words, anchoring explanations of the world we perceive to a particular frequency-domain interpretation of it.

For the Walsh-Hadamard transform, I think the answer about applications is fairly intuitive: it works well for isolating square wave components, which is something that DFT turns into a mess. I think it's used in a couple of digital signal processing domains (including something with spread-spectrum coding?), for filtering certain "spiky" signals (e.g., ECG), and somewhere in cryptography. It could probably also work well for certain types of image compression, but DCT works better in the general case.

Expand full comment