Is a wavelet-based correlation measure worth any additional computational overhead?

Question

I have used both correlation and coherence as measures of correlation between signals. I was thinking that a time-frequency approach would give me the best of these worlds.

My question is whether this extra data adds enough to the overall picture of the signal to justify the increased computational cost associated with doing the wavelet transforms as part of the calculation?

Reference: an ArXiv paper: "A cross-correlation technique in wavelet domain for detection of stochastic gravitational waves" by S.Klimenko, G.Mitselmakher, A.Sazonov

Answer 1

First off, you should use whichever tool is appropriate for the job. Correlation vs coherence vs wavelet-based correlation are all different things, so this question is kind of like asking "Which is better? Screwdrivers or hammers?" It depends on what you're trying to do, and whether you care about similarity in time, frequency spectra, or both.

Second, I have only a minimal understanding of wavelets, but your assumption that wavelets require more computation might be wrong. The Fast Fourier Transform takes $O(n\log n)$ operations, while the Fast Wavelet Transform takes $O(n)$. So the wavelet method might actually require less computation, depending on whether you can use the information you get out of it.

Empirically, producing n outputs from n real inputs, the multi-level wavelet transform in PyWavelets becomes faster than NumPy's FFT when n is greater than about 4096.

However

1. It's Python, and the two implementations could be very differently efficient. I don't even know if wavedec() would be considered a Fast Wavelet Transform. They use the abbreviation DWT in their documentation. Are Haar DWT and FWT the same thing?
2. The time varies depending on the wavelet used. Meyer wavelet takes 6 times as long as Daubechies to produce the same amount of data.
3. I still don't understand how the FWT tiles the time-frequency plane, or if producing n outputs is sufficient to get the same kind of similarity measurement as an n-point circular cross-correlation using FFTs. (Technically it's a time-scale plane, not time-frequency, but I think they're the same for the complex Morlet wavelet?) FWT is a "critical sampling" of the plane, and produces the same amount of data as FFT, so it seems fair to compare them.

The main point is that computation time is at least roughly similar for both, so I don't think you should worry about it when deciding which to use.

Answer 2

This is very late, but maybe it's worth it anyway...

The time-scale plane is not the same as the time-frequency plane, although it might be useful as well. Signals at different places in the time scale plane are related by $x(t) \rightarrow x(\Delta s(t-\Delta t))$, where $\Delta s$ moves you up (or down) in scale and $\Delta t$ shifts you in time. The same transformation in the time-frequency plane is $x(t) \rightarrow x(t-\Delta t) e^{i \Delta \omega t}$, where $\Delta \omega$ is a shift in frequency. If your signal $x(t)$ is a sine wave, the two transformations are the same.

The DWT, or discrete wavelet transform, computes only discrete scales, just as the FFT computes only discrete frequencies. And the comment that @Spacey made above that the DWT is not translation-invariant is correct. This occurs because at every stage of the DWT, the signal is decimated by two. This makes the DWT faster than the FFT, $O(N)$, but also destroys the translation-invariance.

So using the DWT to examine the time-scale plane isn't going to get you very far. This is especially true because the scales "visited" by the DWT are separated by factors of two, and are much less dense than the coverage you can get in the time-frequency plane with the FFT. You need to use a wavelet transform that is translation-invariant, sometimes called the undecimated wavelet transform, among many other names. Even then, you still have the sparsity of the computed scale samples to contend with.

Furthermore, it's often desirable to think of locations in the time-scale plane as having an energy density. This approach is facilitated by using an analytic wavelet, such as the complex Morlet wavelet mentioned earlier. One method that balances translation-invariance and analyticity against computation time is the complex dual-tree wavelet transform. Doing the same thing in the time-frequency plane is perhaps simpler: do an approximate Hilbert transform on your signal first by doing an FFT, zeroing out all the negative frequencies, followed by an IFFT.

If the intuition that correlation looks for similarity in time and coherence looks for similarity in frequency is correct, then you might be better off sticking to the time-frequency plane. It's certainly simpler to compute, and it's easy to refine the sampling along the frequency axis. None of the approaches mentioned above address sampling the scale axis more densely. To do that, you pretty much have to go to the continuous wavelet transform, although there might be something else out there that I'm not aware of. If you have Matlab, follow the link above and have at it.