(I asked this on Stack Overflow a while ago and didn't get a satisfying answer, so I'm trying again here.)
Although they are often compared, it seems like the FFT and FWT are apples and oranges. As I understand it, a more appropriate comparison would be the STFT (FFTs of small chunks over time) and the complex Morlet WT, since they're both time-frequency representations based on complex sinusoids (please correct me if I'm wrong). This is often shown with a diagram like this:
The left shows how the STFT is a bunch of FFTs stacked on top of each other as time passes (this representation is the origin of the spectrogram), while the right shows the dyadic WT, which has better time resolution at high frequencies and better frequency resolution at low frequencies (this representation is called a scalogram).
In this example, N for the STFT is the number of vertical columns (ω axis), and a single O(N log N) FFT operation calculates a single row of N coefficients from N samples.
What I don't understand: How many coefficients does a single O(N) FWT operation compute, and where are they located on the time-frequency chart above? Which tiles get filled in by a single computation?
If we calculate an equal-area block of time-frequency coefficients using both, do we get the same amount of data out? Is the FWT still more efficient than the FFT?
Concrete example using PyWavelets:
In : dwt([1, 0, 0, 0, 0, 0, 0, 0], 'haar') Out: (array([ 0.70710678, 0. , 0. , 0. ]), array([ 0.70710678, 0. , 0. , 0. ]))
It creates two sets of 4 coefficients, so it's the same as the number of samples in the original signal. But what's the relationship between these 8 coefficients and the tiles in the diagram?