PS #1: If you're curious about the reason the bit-twiddling Hadamard matrix construction method works, I explore it a bit more in the article on the Sierpiński triangle: https://lcamtuf.substack.com/p/sierpinski-triangle-in-my-bitwise/. There is a comment under the article that ties it back to Hadamard.
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.
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.
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.:
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.
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.
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.
PS #1: If you're curious about the reason the bit-twiddling Hadamard matrix construction method works, I explore it a bit more in the article on the Sierpiński triangle: https://lcamtuf.substack.com/p/sierpinski-triangle-in-my-bitwise/. There is a comment under the article that ties it back to Hadamard.
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.
In the classical FFT, the result includes real *and* imaginary parts, so...
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.
No.
Could you elaborate why? It is a reasonable request due to the safety of Rust.
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.
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.
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.
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.