2
$\begingroup$

I'm currently researching implementation methods of the Continuous Wavelet Transform(CWT). On paper, the CWT produces infinitely many outputs on a finite signal since the scaling and shifting parameters are continuous.

When discretizing the CWT for a computer application, it is common to limit the scaling based on the bandwidth of the signal and the number of desired voices per octave.

However, I'm confused as to how the time-shifting should be limited. Since we're operating on a discrete input signal, we could technically just time-shift each wavelet by 1 sample to obtain the highest resolution. Yet, this seems wasteful for low-frequency convolutions.

It seems like the time-shift should be a function of scale, such that the time-shift is smaller for high-frequencies and larger for low-frequencies.

How is the CWT time shift typically determined when implementing the algorithm on a computer?

$\endgroup$
1
$\begingroup$

It's indeed wasteful for some signals, but unfortunately not much to do there except downsample afterwards. A fully rectangular representation enables reconstruction and analysis operations that aren't otherwise possible - further, doing 1 shift per sample can be much faster and take less (compute-) memory than e.g. skipping 1, via FFT convolution.

I provide a naive implementation with visuals here, also comparing against Python library implementations. Further, just today I've pushed out a ssqueezepy release, which has the best open-source CWT implementation I know of (I've yet to see if it beats MATLAB's) - can inspect its code.

If you insist on discretizing per-scale, I can only suggest a trial & error approach, as results will vary based on data, wavelet, and wavelet parameters used. You can then plot as a single 2D image by duplicating adjacent time-axis values for higher scales (but that's much effort and guesswork for little or no gain in speed).

$\endgroup$
8
  • $\begingroup$ Regarding implementation, is it more common to use FFT convolution rather than convolution in the time domain? Is FFT convolution "always" going to be faster? I'm researching GPU implementations of the CWT and assume that time series convolution is highly parallel, however, not sure if it could compete with an FFT implementation. $\endgroup$ – Izzo Nov 5 '20 at 20:53
  • $\begingroup$ @Izzo It's not even close between FFT and convolution, only unless sequence lengths are less than about 32. ssqueezepy's, by the way, does something quite different that surprisingly yields better results - discretized convolution, which I've yet to fully understand. FFT convolution is different; it takes DFT and pads both sequences to avoid time-domain aliasing (but yields exactly same result as plain linear convolution, even more accurately in terms of float error as less add/multiply ops). $\endgroup$ – OverLordGoldDragon Nov 5 '20 at 20:57
  • $\begingroup$ And when you say FFT convolution, you're essentially saying: take FFT of wavelet and FFT input signal, multiply them together, perform inverse FFT and we get our output for our first scaled wavlet? $\endgroup$ – Izzo Nov 5 '20 at 21:00
  • $\begingroup$ I don't know the internals of FFT so can't comment on parallelization, but I'd recommend this source with performance comparisons against convolution. -- And, almost correct; it's essential to pad correctly before taking FFT - simple example here. A more detailed explanation toward bottom here. $\endgroup$ – OverLordGoldDragon Nov 5 '20 at 21:02
  • $\begingroup$ @Izzo Actually, for fast, GPU-parallelized convolutions, no better place to look than deep learning libraries - e.g. Pytorch. No neural nets needed, just take the relevant operation. (and I recommend staying away from TensorFlow) $\endgroup$ – OverLordGoldDragon Nov 5 '20 at 21:45

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.