Which time-frequency coefficients does the Wavelet transform compute?

Question

The Fast Fourier Transform takes $\mathcal O(N \log N)$ operations, while the Fast Wavelet Transform takes $\mathcal O(N)$. But what, specifically, does the FWT compute?

Although they are often compared, it seems like the FFT and FWT are apples and oranges. As I understand it, it would be more appropriate to compare the STFT (FFTs of small chunks over time) with 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:

(Another example)

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 (6), and a single $\mathcal O(N \log N)$ FFT operation calculates a single row of $N$ coefficients from $N$ samples. The total is 8 FFTs of 6 points each, or 48 samples in the time domain.

What I don't understand:

• How many coefficients does a single $\mathcal O(N)$ FWT operation compute, and where are they located on the time-frequency chart above?

• Which rectangles 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 [2]: dwt([1, 0, 0, 0, 0, 0, 0, 0], 'haar')
Out[2]:
(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?

Update:

Actually, I was probably doing this wrong, and should be using wavedec(), which does a multi-level DWT decomposition:

In [4]: wavedec([1, 0, 0, 0, 0, 0, 0, 0], 'haar')
Out[4]: 
[array([ 0.35355339]),
 array([ 0.35355339]),
 array([ 0.5,  0. ]),
 array([ 0.70710678,  0.        ,  0.        ,  0.        ])]

Answer 1

You are correct that the FWT is better thought of as a "cousin" of the STFT, rather than the FT. In fact, the FWT is just a discrete sampling of the CWT (continuous wavelet transform), as the FFT/DFT is a discrete sampling of the Fourier transform. This may seem like a subtle point, but it is relevant when choosing how you discretize the transform.

The CWT and STFT are both redundant analyses of a signal. In other words, you have more "coefficients" (in the discrete case) than you need to fully represent a signal. However, a Fourier transform (or say a wavelet transform using only one scale) integrate a signal from -infinity to +infinity. This is not very useful on real world signals, so we truncate (i.e. window) the transforms to shorter lengths. Windowing of a signal changes the transform -- you multiply by the window in time/space, so in transform space you have the convolution of the transform of the window with the transform of the signal.

In the case of the STFT, the windows are (usually) the same length (non-zero extent) at all time, and are frequency agnostic (you window a 10 Hz signal the same width as a 10 kHz signal). So you get the rectangular grid spectrogram like you have drawn.

The CWT has this windowing built in by the fact that the wavelets get shorter (in time or space) as the scale decreases (like higher frequency). Thus for higher frequencies, the effective window is shorter in duration, and you end up with a scaleogram that looks like what you have drawn for the FWT.

How you discretize the CWT is somewhat up to you, though I think there are minimum samplings in both shift and scale to fully represent a signal. Typically (at least how I've used them), for lowest scale (highest frequency), you will sample at all shift locations (time/space). As you get higher in scale (lower in frequency), you can sample less often. The rationale is that low frequencies don't change that rapidly (think of a cymbal crash vs. a bass guitar -- the cymbal crash has very short transients, whereas the bass guitar would take longer to change). In fact, at the shortest scale (assuming you sample at all shift locations), you have the full representation of a signal (you can reconstruct it using only the coefficients at this scale). I'm not so sure about the rationale of sampling the scale. I've seen this suggested as logarithmic, with (I think) closer spacing between shorter scales. I think this is because the wavelets at longer scales have a broader Fourier transform (therefore they "pick up" more frequencies).

I admit I do not fully understand the FWT. My hunch is that it is actually the minimum sampling in shift/scale, and is not a redundant representation. But then I think you lose the ability to analyze (and mess with) a signal in short time without introducing unwanted artifacts. I will read more about it and, if I learn anything useful, report back. Hopefully others will like to comment.

Answer 2

Consider the Haar wavelet case. The Fast Wavelet Transform recursively subdivides your signal and computes the sum and difference of the two halves each time. The difference is the magnitude of the transform for the current wavelet and the sum is returned for the caller to compute the magnitude of the transform for a dilated wavelet with half the frequency. Thus, the FWT covers the time-frequency plane using the pattern described in the diagram you gave.

Note that the diagram you gave is a bit misleading. What they are really trying to tell you is that you get one sample at the lowest frequency, two samples at double that frequency, four samples at quadruple that frequency and so on. The time-frequency properties of each wavelet are not such that they cover their tile. In practice, each wavelet will cover an infinite area because they have compact support and, therefore, must be completely delocalized in terms of frequency. So you should just think about the centers of those tiles.

Furthermore, the FWT requires a discrete wavelet that must adhere to a far more restrictive admissibility criterion than continuous wavelets for the CWT. Consequently, the time-frequency properties of discrete wavelets are generally awful (e.g. the Daubechies wavelets are either full of sharp features or have changing frequency) and the utility of the time-frequency plane is greatly diminished in the context of the FWT. However, continuous wavelets are used to compute time-frequency representations of signals.

Answer 3

Your reference has it:

A sequence of coefficients based on an orthogonal basis of small finite waves, or wavelets.

For more, you may like the DWT page. There it introduces Haar wavelets, Daubechies wavelets and others. It points out how

• Wavelets have location – the (1,1,–1,–1) wavelet corresponds to “left side” versus “right side”, while the last two wavelets have support on the left side or the right side, and one is a translation of the other.
• Sinusoidal waves do not have location – they spread across the whole space – but do have phase – the second and third waves are translations of each other, corresponding to being 90° out of phase, like cosine and sine, of which these are discrete versions.

If, instead of discrete wavelets, you want to now about continuous wavelets or complex wavelets, you might start with wavelet series.

Beyond wikipedia, a textbook and a course might do you well.

Answer 4

Basically, FFT (Fast Fourier Transform) and FWT (Fast Wavelet Transform) are two implementations for discretized transforms, stemming from continuous transforms, turned discrete, that are much faster than standard matrix implementation in $O(N^2)$ (for 1D data). One is more appropriate for harmonic signals, one for transients (more or less).

Note in passing than the FWT does not need to be orthogonal, and that other fast versions exist, like the lifting scheme. Note also than these estimations are asymptotic, and that they cannot be compared easily for short data. In other words, $O(N)$ is not "must faster" than $O(N\log(N))$ in the non-asymptotic regime, because the constant in the $O(\cdot)$ can change the deal. And stuff is not so simple in higher dimensions.

Start from the generic windowed STFT (continuous form). If you plug in an infinite window of unit height, you recover the Fourier transform as a special case. Which you can discretize (and get the DFT) and make it fast (and get the FFT).

Start from a CWT (continuous form). The continuous CWT admits an incredible quantity of potential wavelet shapes. They can be discretized exactly only with sampling patterns (in time or scale) that respect some "Heisenberg" inequality: one sample per unit surface. These patterns depend on the wavelet. In the majority of cases, the patterns make a discretized CWT that is redundant, and yield a wavelet frame.

Some wanted it non redundant, with a dyadic scale (DWT). Only very few wavelets (still an infinite number, but you cannot find them by chance) allow that. Among the first ones were the Haar, the Franklin and Meyer wavelets. If you then impose the wavelet support to be finite, then Haar was quite the only one for a long time. It is almost impossible to obtain an orthogonal wavelet from "natural continuous wavelets", that's why Daubechies' ones were built, and later Symmlets and Coiflets. Those weird-shaped wavelets do no have nice and simple formulas like the Morlet wavelet.

However, they can be implemented with filters and downsampling, instead of integrals. And with some clever tricks, they ended up in $O(N)$ algorithms. You have the FWT. I thus slightly disagree with:

In fact, the FWT is just a discrete sampling of the CWT

DWT (or FWT) is exact, like the DFT/FFT. Most other discretized CWT (with any wavelet) are just approximately so (without much harm if you have sufficient redundancy).

So:

• one single FWT operation computes all coefficients at different levels. The DWT gives you $k$ point per rectangle, you can imagine it at the center, but this is a convention. Basically, this is a sampling of your unknown continuous CWT plane : $k$ samples per "unit" surface. Each point "represents" the whole rectangle, a bit like a DFT point represents the whole DFT bin around him. No fully correct, but that's the idea. The $k$ is given by the signal length. In your graphic, suppose you have $8$ points between $0$ and $4T$. A first level of DWT gives you $2\times 4$ points (one low-pass, one high-pass, downsampled by $2$). That is what you got with your first Python try. The $4$ from high-frequency filtering give you one sample for each of your flat rectangles in $[\omega/2,\omega]$, the highest frequencies. The other $4$ points are decomposed into $2\times2$ again by one low-pass, one high-pass. Similarly as above, $2$ give you one sample for each of the two squares. With the remaining, low-pass/high-pass, you get one sample in $[\omega/8,\omega/4]$. The last sample is the final low-pass coefficient, put in the left-most tall rectangle. That is what you have with your final Python code: $[1,1,2,4]$ coefficients
• rectangles would be filled with a CWT. With the DWT, they are not filled, only have $k$ samples each, like a DFT bin is not "filled".
• FWT has asymptotically less $+$ and $\times$ than an FFT. Is that always more computationnally efficient? Not sure, depends on the constant in the $O(N)$. For sine analysis? FWT is never good (due to the finite length filters, notably). But for a compact representation of images, like in JPEG2000, they can be quite good. There, you can use slightly faster scheme like the lifting scheme.

The following pictures reveal how a continuous version of the Haar wavelet

can be sampled into an orthogonal, discrete wavelet:

Note that some discrete wavelets, especially the long ones (like splines), are sometimes computed using an FFT :)