For a paper I recently submitted, I was asked to provide the number of operations for my method. I decompose CNN features using wavelets for pooling. I know the computational complexity of the FWT is O(N). But how do I calculate the exact number (or an estimate) of computations using the FWT for any given image?
Hi Travis,
the number of computations might be difficult to estimate and it will heavily depend on your implementation.
But I trie to give you an idea how one could estimate it in my opinion: Basically, the FWT is the convolution of an iteratively downsampled input with highpass and lowpass filter coefficients. The wavelet you are using determines these filter coefficients. If we assume the number of filter coefficients for the low pass and high pass as K and L, for a straight forward time domain implementation, you could calculate the number of computations like this: for each scale with N input points (N is getting smaller per scale due to downsampling) you will have to perform N*K multiplications and N*(K-1) additions for low pass filtering and N*L multiplications and N*(L-1) additions (if we do not consider differences at the "borders").
However, depending on the filter coefficients and input signal length it will be beneficial not to use a straight forward time domain implementation. Some wavelets also allow efficient implementations owing to the structure of their filter coefficients. An efficient implementation thus won't need the number of computations as stated before.
Greetings, Sebastian
Thank you! Disregard my follow up. I figured it out and had answered my own question.
- Badges
- Science topic
- Similar topics
- Computer Science
- Images