python - 离散傅立叶变换在 python 中不起作用/效率很低

Question

我正在尝试在 python 中编写一个离散傅里叶变换函数，它将信号的能谱密度作为一个数组(然后我将以图形方式输出)。我正在使用矩阵乘法来做到这一点。我的代码似乎适用于一小部分数据，但需要很长时间才能处理；对于大量数据，例如一个 wav 文件，它永远无法完成任务。目前的功能是:

from scipy.io import wavfile
import numpy as np
import matplotlib.pyplot as plt

def esd(数据, fs):

a=[]


for i in range(int(np.size(data)/100)):

    dt = 1/(fs)

    fvec = np.arange(100*i , 100+(100*i) , 1)  
    nvec = np.arange(0 , np.size(data) , 1)

    Wconst = np.exp(-1j*2*np.pi/np.size(data))

    ematrix = Wconst**(np.outer(fvec,nvec))

    b = (dt**2)*(abs(np.inner(ematrix , data))**2)

    a = np.concatenate((a,b))




return a

其中data是数据集，fs是采样频率。这个功能如此缓慢或低效是有原因的吗？它旨在处理 100 个频率 block 中的信号，否则矩阵会非常大。

Answer 1

该算法通过计算 Vandermonde 频率矩阵实现“朴素”离散傅立叶变换 (DFT)。问题就在这里:

b = (dt ** 2) * abs(np.inner(ematrix, data)) ** 2

这个简单的实现使用直接矩阵向量乘法，运行时间为 O(N**2)，其中 N == data.size。因此，当您获得更大的数据时，它会变得更糟，并且可能无法在合理的时间内为您的 WAV 文件完成。

这就是使用快速傅里叶变换算法的全部要点，它利用了问题中的许多结构。最值得注意的是，FFT 将问题递归分解为大小为 N/2 的更小问题。该递归结构使 FFT 的运行时间为 O(N log N)。