26
$\begingroup$

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:

Grids showing how the coefficients of the FFT and WT correspond to the time-frequency plane

(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.        ])]
$\endgroup$

migrated from stackoverflow.com Nov 14 '11 at 22:44

This question came from our site for professional and enthusiast programmers.

  • 2
    $\begingroup$ In order to have a better understanding of how these wavelets decomposition work, one useful tool would be to be able to do it on real-life signals : audio signal for example (I have a question in this direction here dsp.stackexchange.com/questions/12694/stft-and-dwt-wavelets) $\endgroup$ – Basj Nov 19 '13 at 9:08
  • $\begingroup$ @endolith Is your question still requested? If so, I can add other hints $\endgroup$ – Laurent Duval May 18 '16 at 17:51
  • $\begingroup$ @LaurentDuval Yes, it's still open, and I still don't understand. I may be confused because CWT uses things like Morlet and DWT only uses things like Haar or Daubechies. I'm not sure if the fast FWT is only Haar or can also use other types of wavelets, either. $\endgroup$ – endolith May 18 '16 at 18:00
  • 2
    $\begingroup$ @ndolith Just a comment for this one: the continuous CWT admit 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. These patterns depend on the wavelet. In the majority of cases, the patterns make a discretized CWT that is redundant. Some want it non redundant, with a dyadic scale. Only very few wavelets allow that. If you then impose the wavelet support to be finite, then Haar is one, almost impossible to obtain w/ "natural wavelets", that why Daubechies' ones were built $\endgroup$ – Laurent Duval May 18 '16 at 18:08
13
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ "it is actually the minimum sampling in shift/scale, and is not a redundant representation." Ah! I think you're right, and this would explain why it's always compared to the FFT, which is also a minimal representation. $\endgroup$ – endolith Nov 24 '09 at 17:11
  • 3
    $\begingroup$ The FWT is a critical sampling of the CWT. I'm still trying to understand it better, but I've learned that the STFT and CWT are both Frames. Frame theory is getting beyond me, but one interesting notion is the uncertainty formula, that for the STFT, dw * dt > C (dw is the frequency resolution, and dt is the time resolution). In other words, as you try to better resolve frequency, you lose time resolution. The CWT does not have this limitation. I will keep reading and try and clarify my answer above once I clarify it in my head. $\endgroup$ – Patrick Dec 10 '09 at 16:24
  • 1
    $\begingroup$ From what I understand, CWT has the same limitation, but uses a better trade-off. $\endgroup$ – endolith Dec 12 '09 at 19:58
  • 1
    $\begingroup$ "STFT are both redundant analyses of a signal". I don't think that's true. If you have a 100-point signal, divide it up into chunks of 10 points, then do a 10-point FFT on each, you still have the same information stored in the same amount of samples. $\endgroup$ – endolith Feb 15 '11 at 19:01
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, I understand the localization of the coefficients. That's the same as the FFT. When you say "must adhere", what do you mean? Is it only a requirement if you're trying to get a minimal/non-redundant representation of the signal? What if you're just trying to analyze/visualize it? I'll add a more concrete example to the question. $\endgroup$ – endolith Feb 8 '10 at 15:18
  • 1
    $\begingroup$ Adhering to the admissibility criterion ensures that a resolution of the identity exists, i.e. that all signals can be recovered from their wavelet transforms. If you do not adhere to it then you cannot recover a signal from its transform, at which point you must question what exactly it is that you're analysing (does it even reflect any information that was in the signal?!). If you do not require a minimal/non-redundant representation then you could use the more lax admissibility criterion from the CWT (which lets you define more "ideal" wavelets). $\endgroup$ – Jon Harrop Feb 11 '10 at 0:54
  • 1
    $\begingroup$ I think you would find my PhD thesis really useful. I'll put it on-line for you... $\endgroup$ – Jon Harrop Feb 11 '10 at 0:54
  • $\begingroup$ Did you put it online? :) $\endgroup$ – endolith Feb 25 '10 at 16:23
  • 2
    $\begingroup$ I sure did: flyingfrogblog.blogspot.com/2010/02/… $\endgroup$ – Jon Harrop Feb 26 '10 at 3:44
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I don't understand this answer. Does it answer my questions? Left side and right side of what? What does this have to do with the time-frequency representation? $\endgroup$ – endolith Nov 24 '09 at 15:11
  • $\begingroup$ The "left side versus right side" description is an excerpted preview of the DWT page, showing that that page includes a simple example to explain the relative merits of the sinusoidal basis and the Haar wavelets basis. You were asking about the nature of the coefficients in a wavelet transform. It sounded like you were looking for intuition. I thought you might find that example (in its original context) useful. $\endgroup$ – Ewan Todd Nov 24 '09 at 15:44
  • $\begingroup$ Yes, I've read the Wikipedia articles multiple times before posting this question. I don't know if/what your answer has to do with my question about the time-frequency representation. If it does, could you connect the dots? An FFT of n samples will produce n coefficients, which make up a single column of the STFT spectrogram. Is there a corresponding relationship between the coefficients produced by the WT and the scalogram? If so, what is it? Which of the boxes in the bottom right chart are filled in by a single run through the FWT? $\endgroup$ – endolith Nov 24 '09 at 16:08
  • 1
    $\begingroup$ Almost everything on the Wikipedia pages related to wavelets is currently wrong. $\endgroup$ – Jon Harrop Feb 15 '10 at 21:34
3
$\begingroup$

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 continuous Haar wavelet

can be sampled into an orthogonal, discrete wavelet: discrete critical Haar wavelet

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.