The following article has been re-posted, as-is, from the now defunct SubjectiveMachine blog. First published Oct 8, 2011.
I have some (very preliminary) results from a (very rough) implementation of the signal analysis algorithm I alluded to in my previous post. For the moment, for want of a better name I shall refer to it as PWT – for “Period Wave Transform” or “Period Width Transform”. The images below compare the output of my implementation with that of STFT (as output by Audacity) for the same signal.
Notice first that the outputs are not identical, although they are similar. PWT does not emulate STFT and there are some characteristic differences in each approach that are reflected in their outputs (for example with respect to the characterisation of [apparent] harmonics). I hope to explore some of these differences in detail in a some later posts.
What is perhaps most intriguing though is the difference in computational complexity between the two algorithms:
A naive implementation of the Fourier Transform takes O(n2) computations, where n is the length of the signal (i.e. the number of samples or datapoints it contains). The Fast Fourier Transform (FFT) reduces this to O(n log(n)). STFT is basically a bunch of Fourier Transforms performed upon several blocks of data, but owing to the fact that these blocks of data come from a single source and are heavily overlapped, it is possible to make further optimizations. Therefore, whereas performing a separate FFT upon each block in the data would take around (n w log(w)) steps in total (where w is the block size), existing STFT algorithms require only (n w) steps. If the block size is linked to the signal size (i.e. w=xn for some constant x) then the resultant complexity is O(n2); such might be the case where increases in n correspond to increases in sampling rate or fidelity, with x corresponding to some maximum wavelength (minimum frequency) that we are interested in capturing. In the alternative case that the block size w is fixed, the complexity reduces to O(n), although of course the actual number of computations in practice will be very much dependent upon w.
In contrast, the complexity of PWT is simply O(n), with the actual number of computations being comparable to that of STFT with very low w, and instead somewhat dependent on the amplitude resolution. Like STFT with low w it is also suitable for calculating online (i.e. as the data is encountered). As it does not require any segmentation however, it can respond to the full gamut of frequencies present in the signal (note: I have not substantiated this on audio data yet, but watch this space).