Analyse audio/music frequencies without STFT, at 1/f temporal resolution, using probe phasors at logarithmically-spaced frequencies, O(N log N)?

Question

First, some background: The STFT is the best general-purpose tool I know of for analysing a (musical or other) signal into its component frequencies. For many purposes the STFT works fine, but there are two related problems that make it non-ideal for musical purposes -- 1) the frequency bins are evenly-spaced, not logarithmically like the human hearing system works, and 2) by the mathematical nature of the DFT/FFT, you need to capture a long period of audio to get decent frequency resolution at low frequencies.

For example, to be able to distinguish semitones accurately in the bass range of a piano, you'd need approximately 1hz resolution, meaning you'd need to capture 1 second of audio. For music, this is a completely unacceptable time resolution.

There are various ways to enhance the output of the FFT, including a) zero-padding to create a larger window, or b) overlapping analysed segments, or c) magic with the phase to detect frequency change. These are useful, but still have problems -- more computation overhead, and while (a) can increase the apparent frequency resolution at a given temporal resolution, it doesn't help with a situation where two frequencies happen to fall into the same bin.

So... I've been researching other possibilities, out of sheer interest. CWT and DWT looked very promising at first, but the CWT is very slow to compute, and the DWT only has octave frequency resolution. (That right?) I've also considered taking multiple FFTs at different time/frequencies resolutions to cover the space better, or solutions like zoom-FFT. These all help solve different specific problems, but none of them really make the fundamental problem go away: we don't have a fast (N log N) way of analysing the frequencies in a signal at good temporal and frequency resolution.

A lot of people point to the Heisenberg uncertainty principle at this point, implying that there's a mathematical impossibility of actually achieving this at all. I'm pretty sure this is simply wrong: sure, the uncertainty principle is valid, but we're not even close to running into it yet. The problem here is that the DFT/FFT can only analyse frequencies at integer multiples of the fundamental. However, the other frequencies are certainly there to be analysed, at good temporal resolution -- if we're willing to use a (computationally slow) sine sweep or continuous wavelet transform. The uncertainty principle doesn't cause problems until long after the FFT ceases to be useful.

So, my solution. I'd like you to tell me if and where it's wrongheaded: Let's correlate the input signal with probe phasors at select frequencies. At first, this sounds like an N^2 algorithm (N operations for a correlation at each frequency, times the number of frequencies). However, the key point is that for equivalent log-frequency resolution to an FFT of the same frequency resolution (at low frequencies), you only need to analyse log N frequencies -- because the resolution at high frequencies is logarithmically less important in musical signals.

So, we have an algorithm that works like this:

1. Decide on your frequency resolution. Let's say octaves for now, though I'd want sub-semi-tones in most applications.
2. Pre-load some buffers with probe phasors as frequencies spaced at that interval -- let's say 16, 32, 64, 128, 256, 512, 1024hz, [...]. Because higher frequencies can be detected in a shorter amount of time, you need fewer samples (= better temporal resolution, as well as fewer operations) at higher frequencies. For the sake of it, let's use a few periods at each frequency.
3. Pre-window these buffers, if it makes sense.
4. Correlate each of these with a long-enough segment of the input signal at time t (i.e. the sum of the component-wise multiplication of the segment and the probe). Probably normalize this value.
5. The result of this correlation is the magnitude of the signal at that frequency, at time t. So, the table of results-vs-frequencies should be your frequency spectrum at the desired logarithmic resolution (octaves, in this case).

From what I can work out, this would give you superb temporal resolution proportional (a few cycles of each frequency) at whatever frequency resolution you like, using approximately N operations times log N frequencies, so long as your frequencies were logarithmically spaced -- which is exactly what you want for music, and exactly the problem with the STFT -- thus, solving the problems with the STFT (for musical signals), with equivalent computational complexity.

What am I missing? Would this work at all? Are there caveats or pitfalls? Is my complexity calculation mathematically sound?

It feels a bit like inventing a perpetual-motion machine -- it looks like it should work, but my gut feeling is that I'm glossing over some important detail.

Answer 1

True, the complexity would be $O(N \log N)$.

But this $\log N$ captures a different reality from the $\log N$ in the FFT algorithm. In your case it comes from the fact that you're only interested in a smaller set of logarithmic spaced frequencies. In the FFT case, it comes from the "divide and conquer", recursive structure of the Cooley–Tukey algorithm.

Let's say you're interested in quarter-tone resolution, from 40 Hz to 1.28kHz. That's 5 octaves, or 120 quarter-tones. For a 1024-long buffer, your algorithm is doing exactly 1024 x 120 complex MAC (plus some book-keeping). A naive radix-2 FFT would do 1024 x 10 complex MAC (plus some book-keeping). Your algorithm is 12 times slower.

Also, your transform doesn't sound invertible, which makes it useful only for analysis applications (not resynthesis, effects...).

Answer 2

What you describe might be similar to applying a Constant-Q transform using Morlet or Gabor wavelets. These transforms may have a higher computational cost than using windowed FFTs, but may, when scaled suitably, represent something closer to human perceptual resolutions for both frequency and time.

Answer 3

Please define what you mean by probe phasor? i haven't encountered that term in audio.

I think that your theory is good, because i wrote a similar program in 2004 which gives sample accurate results, without bins and windows. the uncertainty principle does prevent bit accurate detection of sine wave peaks and troughs, if you had two sines mixed inside an audio file and you wanted to analyse them in a spectrogram from a submarine radar which is pretty precise, you wouldnt be able to see very precise frequency and time signatures, you couldn't have a sine wave of 440 that makes a single detected signature line at 440, but you could average the values of the spectrogram that would form a bell curve around the 440 mark and say with high precision that the signal was at 440.

The probe phasor would necessarily be based on delays of audio and comparing values across the time domain, and that means that the highest frequency time signatures that you can have are delayed as a factor of the frequency, so low frequencies have lower time domain resolution... and as you increase the precision of the phasor probe, i found that the resulting graph values are written with more time delay or less time precision, i don't know which.

I saw that, as you can compute a 1gb high precision analysis of a 1 second sound, you have so much data in the end that you can visually and mathematically average and process the result to have much more precision that the initial uncertainty precision implies, that if you do further processing, you can have frequency accurate data, and very accurate time data too, but it does seem to be by statistically averaging the results. same as all statistics, with alot of data you have high certainty of the underlying values.

you can also run the audio forwards and backwards, and determine from both graphs where in time the detected signals are actually occuring, they are in the middle of the forwards and backwards analysed spectrogram.