Analysis and algorithmic complexity of the Constant Q transform

Question

Here I am again (Implementation of the constant Q transform + property questions) :)

I was reading this paper on a constant-q transform algorithm, where they managed to turn the following equation for the constant-q transform:

into this:

(where X[k] is the fourier transform of x[n], and K*[k, kcq] is the complex conjugate of the fourier transform of the w[n, kcq]) - claiming it to be an efficient algorithm.

While I'm still new to algorithmic complexity, I tried to derive the big-O complexity. I'm assuming the transforms of the windows (ie. K*[], the kernels) are pre-calculated. Let N be the size of the transform, and K the number of components (kernels / filters / results). Would this be correct?

So thats the FFT (N * log2(N)) plus K loops of N multiplies (the convolution) + additional stuff done at each loop (done K times). Also, since the kernels are precalculated, that incurs both a certain amount of memory storage needed + a lot of memory access during the calculation. With their implementation, they store the kernels in full size (that is, N), so the required storage memory for the calculation would be K kernels of N size.

I'm defining M() to be the amount of memory used during an calculation:

That is, we need to load the whole signal (N), also K number of N-sized complex (2) kernels. That is quite different from algorithms like the standard fft and direct evaluation of the constant-q transform which requires no working storage, and as of such are defined to be:

-Since they only need to load the signal. If we define the complexity of the FFT and the direct evaluation of the constant-q transform to the following:

(This assumes direct evaluation of the CQ-transform which incurs at least NK operations, together with NK operations calculating the discrete window for each component.)

we can create a small comparison table for an example. If the transform is of size 2048, and the wanted number of components is 1048 (N = 2048, K = 1048), we get the following results:

It would seem the cqfft algorithm (theirs) incurs a rather extreme memory cost (that in practical appliances could dominate computational speed) for a mere ~2x increase in computation speed. Is this correctly derived?

Here's a reference-pseudocode of their implementation i wrote, as i understand it. If i have misunderstood their algorithm, it will probably show here:

std::vector<complex<float>> fft(float[], size_t);

class kTransform
{
    vector<complex<float>> cqfft(vector<float> signal)
    {
        vector<complex<float>> fftdata = fft(signal, size);
        for (int kernel = 0; kernel < kernels.size(); ++kernel)
        {
            complex<float> accumulator;
            for (int k = 0; k < size; ++k)
            {
                accumulator += fftdata[k] * conj(kernels[kernel][k]);
            }
            fftdata[kernel] = accumulator / size;
        }
        return fftdata;
    }

    void compileKernels(vector<float> freqs, size_t dftSize)
    {
        auto numKernels = freqs.size();
        kernels.resize(numKernels);
        size = dftSize;
        for (int kernel = 0; kernel < numKernels; ++kernel)
        {
            kernels[kernel] = fft(Window(freqs[kernel]));
        }
    }
    size_t size;
    vector<vector<complex<float>>> kernels; 
};

Thank you for any insight. As a bonus question, does anyone know what the complexity of a fast implementation of the Gabor transform is?

Answer 1

I didn't verify each exact step of your analysis, but it seems that you're overestimating the memory part by a huge margin. A lot of the kernels are identical except for the exact tiem moemnt at which they're applied. In fact, you only have one kernel per level. So for a typical music application you have only 12 levels per octave, and thus 12 kernels. Over a 10 octave range (20 Hz-20 kHz) that's still only 240 levels. The paper you reference uses quarter-tone resolution (24/octave) and 5 octaves. That's just a design choice.

Next, you state that "With their implementation, they store the kernels in full size". I doubt it. The paper explicitly mentions the effect of trimming the kernels (see Figure 3) and states that the kernels are trimmed to 6 values max (and sometimes just 1 !). This saves both memory and time. The exact amount does depend on the trimming applied.