2
$\begingroup$

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:

cq

into this:

cqfft

(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?

ocqfft

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:

mcqfft

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:

mfft mcq

-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:

ocq

(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.)

offt

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: table

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

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.