信息处理 - 常数 Q 变换的分析和算法复杂度 - 吾爱随笔录

我正在阅读有关恒定 q 变换算法的论文，他们设法将以下方程转换为恒定 q 变换：

进入这个：

cqfft

（其中 X[k] 是 x[n] 的傅立叶变换，而 K*[k, kcq] 是 w[n, kcq] 的傅立叶变换的复共轭） - 声称它是一种有效的算法。

虽然我还是算法复杂性的新手，但我尝试推导出大 O 复杂性。我假设窗口的变换（即 K*[]，内核）是预先计算的。让 N 是变换的大小，而 K 是组件（内核/过滤器/结果）的数量。这是正确的吗？

ocqfft

这就是 FFT (N * log2(N)) 加上 N 次乘法的 K 个循环（卷积）+ 在每个循环中完成的额外内容（完成 K 次）。此外，由于内核是预先计算的，因此在计算过程中需要一定数量的内存存储 + 大量内存访问。通过他们的实现，他们以完整大小（即 N）存储内核，因此计算所需的存储内存将是 K 个 N 大小的内核。

我将 M() 定义为计算期间使用的内存量：

麦克菲特

也就是说，我们需要加载整个信号 (N)，以及 K 个 N 大小的复数 (2) 内核。这与标准 fft 和不需要工作存储的常数 q 变换的直接评估等算法完全不同，因此定义为：

mfft

- 因为他们只需要加载信号。如果我们将 FFT 的复杂性和对常数 q 变换的直接评估定义为：

ocq

（这假设直接评估 CQ 变换，它至少会产生 N K 次操作，以及 N K 次计算每个分量的离散窗口的操作。）

我们可以创建一个小的比较表作为示例。如果变换的大小为 2048，并且所需的组件数为 1048（N = 2048，K = 1048），我们得到以下结果：

看起来 cqfft 算法（他们的）会产生相当高的内存成本（在实际设备中可能会主导计算速度），而计算速度仅提高了约 2 倍。这是正确派生的吗？

据我了解，这是我编写的他们实现的参考伪代码。如果我误解了他们的算法，它可能会显示在这里：

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; 
};

感谢您的任何见解。作为一个额外的问题，有谁知道快速实现 Gabor 变换的复杂性是什么？