The Fourier transform and its generalisations are so underappreciated. I've been trying to understand where the speed savings come from and suspect it has to do with coprime harmonics.
I hope someone smarter and more knowledgeable will correct my understanding, but as far as I can tell, the logN savings in harmonic analysis comes from the exponential decay of harmonics in any real ringing system (a passive resonant chamber), because you can avoid "counting"[^1] the energy of subsequent harmonics as precisely as the fundamental frequency.
An excitation frequency of 400Hz will produce resonant harmonics at 800Hz, 1200Hz, etc. at exponentially lower energies than the fundamental. So essentially, you can skip measuring the totatives of the frequency bin you care about.
For example, to find the cause of excitation at 9Hz, you only need to count the energy at 1Hz, 3Hz, 6Hz and 9Hz. You can ignore the totatives of 9 except for 1, which are {1,2,4,5,7,8}.
So if you detect 10J at 2Hz and 10J at 4Hz, you can be sure that there was an excitation at 4Hz as well as 2Hz. Euler's totient function is multiplicative so you win if you do this simultaneously for coprime frequencies.
This is not my area, so math or signal guys please tell me where I'm wrong.
[^1]: "counting" happens by cross-correlating the input with a reference signal, which in Fourier analysis is a cosine wave at the frequency bin.
I hope someone smarter and more knowledgeable will correct my understanding, but as far as I can tell, the logN savings in harmonic analysis comes from the exponential decay of harmonics in any real ringing system (a passive resonant chamber), because you can avoid "counting"[^1] the energy of subsequent harmonics as precisely as the fundamental frequency.
An excitation frequency of 400Hz will produce resonant harmonics at 800Hz, 1200Hz, etc. at exponentially lower energies than the fundamental. So essentially, you can skip measuring the totatives of the frequency bin you care about.
For example, to find the cause of excitation at 9Hz, you only need to count the energy at 1Hz, 3Hz, 6Hz and 9Hz. You can ignore the totatives of 9 except for 1, which are {1,2,4,5,7,8}.
So if you detect 10J at 2Hz and 10J at 4Hz, you can be sure that there was an excitation at 4Hz as well as 2Hz. Euler's totient function is multiplicative so you win if you do this simultaneously for coprime frequencies.
This is not my area, so math or signal guys please tell me where I'm wrong.
[^1]: "counting" happens by cross-correlating the input with a reference signal, which in Fourier analysis is a cosine wave at the frequency bin.