離散フーリエ変換が機能しない/非常に非効率的であるpython

Question

私は、信号のエネルギースペクトル密度を配列（これをグラフィカルに出力する）に与える離散フーリエ変換関数をPythonで記述しようとしています。私は行列の乗算を使ってこれをやっています。私のコードは小さなデータセットでは動作するようですが、処理に時間がかかります。例えば大量のデータに対してタスクを完了しないwavファイル。関数は、現在ある：

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

デフESD（データ、FS）：データがデータセットと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 

サンプリング周波数です。この機能が非常に遅くて非効率的な理由はありますか？これは、100ブロックの周波数で信号を処理するように設計されています。それ以外の場合、マトリックスは非常に大きくなります。

Answer 1

このアルゴリズムは、「ナイーブ」、離散フーリエ変換（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)とするものです。