what is continuous wavelet (cwt) ,wavelet packet (wpt) and stockwell (S-T) computational complexity?

• What is computational complexity of continuous wavelet transform cwt ?
• What is computational complexity of wavelet packet transform wpt ?
• What is computational complexity of Stockwell transform transform wpt ?
• for the cwt : imagine I have a signal with length of $N$ and I scale vector is 0:1:s
what will happen if I discretize scale vector to 0:dj:s for better accuracy?
• for the WPT : Imagine signal size is $N$ and I am decomposing it in $L$ levels.

note:

for Continuous case I guess its $O(S\times N^{2})$ and for 0:dj:S, It must be $O(\frac{S}{dj}\times N^{2})$ , Am I right?
for WPT transform it must be $O(2^{L}\times NLogN )$ . Is that right?
For S transfrom I think it is $O(N^{2}Log N)$ . Is it true?
I have calculated the running time of Stockwell and Continuous wavelet transforms. but the time results are strange.
N=3000; $O(Stockwell)=1.039\times 10^{8}$ it takes 2.5 sec
N=3000, scale=300; $O(cwt)=2.7\times 10^{9}$ it takes 0.58 sec
why this is happening here ? [P.S I have run them 100 times and got the time average]

• Did you find solutions in the given answers? – Laurent Duval Apr 4 '16 at 22:13
• Oui! @LaurentDuval – Electricman Apr 13 '16 at 13:45

Let us assume a one-dimensional signal of length N.

The complexity of the continuous wavelet transform can be $O(N)$, see for instance Continuous wavelet transform with arbitrary scales and $O({N})$ complexity. One should take into account that one can use scale/voice relationship, and subsample each scale or voice differently, which plays a role in the overall complexity. Complex aspects in the wavelet choice, its truncation, approximate FIR relationships are also important when you want to reconstruct.

The complexity of the dyadic or 2-band uniform wavelet packet (each level is decomposed in the same way) is typically $O(N\log N)$. This may be adapted when one chooses multiband or $M$-band wavelet ($M \ge 2$), best basis packet based on entropy-like measures, and useful dual-tree complex wavelet packets.

Baseline S-transform is of $O(N^2\log N)$ complexity. There are claims of recent implementations of a fast S-transform in $O(N \log N)$, from researchers in Calgary.

This being said, one should balance efficiency and complexity.

Firstly, simple and fast transforms might have a limited use, or require very expensive outer processing: one can get a globally very fast and efficient adaptive filtering with complex wavelet frames, which might be more difficult with a standard 2-scale orthogonal discrete wavelet transform.

Secondly, a lot hides in the $O$ Bachmann-Landau notation. There is a constant factor, that can be huge for mild length signals. And the bound can be pessimistic.

Thirdly, memory consumption, and potentials to use pipes, parallelization, GPU/DSP or hardware/software association may mitigate theoretical complexity.

Finally, I would be very glad to see a thoroughful comparison of asymptotic complexity of such time-frequency and time-scale transforms in higher dimensions too.

For a dsicretized signal with N samples. In terms of complexity for the DWT it is O(N) and for WPT its O(Nlog(N)) REFER. For each scale one calculates a convolution and not a single correlation value and the scale values need to be integral values. They can be constrained by using the iterative structure of quadrature mirror LP and HP filters, which is basically a explicit way of coding the scaling function. This is basically because one needs a finite number of scalings of the wavelet to represent the signal (wavelet is overcomplete frame). REFER2. For the wavelet packet tree the extra cost is due to the encoding of the residue/detail coefficients.

EDIT: You are right the discretization of the scale function in the CWT parameter decides the number of levels of decomposition. Matlab implements the CWT and describes that the DFT can be used in calculating the CWT by zeropadding the wavelet and performing circular convolutions.

Here Δt is the sampling interval (period) which basically discretizes the signal and the wavelet. So i guess you are right about the complexities for both the CWT and the WPT versions! Sorry about the mix up!

• He asked for the computational complexity of the CWT, not the DWT. – TheGrapeBeyond Nov 7 '13 at 13:57
• Hi, the signal length is $N$ and decomposition level is $L$. so you are saying computational complexity of $WPT$ is $O(NlongN)$, and for $DWT$ is $O(N)$ then where is the effects of $L$ on computational complexity ?!! It must be related to $L$ somehow.!!! Also I have asked about CWT as well!!! Merci beaucoup. @ravi-kiran – Electricman Nov 7 '13 at 14:46
• Hi. The formulation you gave is CWTFT not CWT. and that uses FFT . but that I am asking about cwt. is true which malab uses conv2 to calculate that integral for cwt and conv2 is very efficient. if you are agree that $O(cwt)=S\times N^{2}$ then why it takes times less than another methods that has $O(ST)=N^{2}LogN$?? look at the question for operation numbers, Tnx @beedot – Electricman Nov 9 '13 at 16:00
• I see! Sorry i am catching on slow! Maybe you could profile the code in matlab over the different loops to the see the distribution of processor time over different loops of S and N? If there are any implementation/algorithm specifics, one should be able to see this. – beedot Nov 9 '13 at 16:20
• yea I guess I must implement cwt codes on my own to be sure. but I have problem with it. see my question here too: dsp.stackexchange.com/questions/11576/… @beedot – Electricman Nov 9 '13 at 16:56