離散フーリエ変換
式3の注目箇所を F v ( x , v ) {\displaystyle F_{v}(x,v)} で書き変えた - F v ( x , v ) {\displaystyle F_{v}(x,v)} は f ( x , y ) {\displaystyle f(x,y)} のx行目の行のv番目の周波数。 f ( x , y ) {\displaystyle f(x,y)} の1次元DFTの行を集めたものがFvである。
式4の1次元DFTの行列表現と同様に、Fvを使って式5を表現した
式4を式6に代入した結果。ここでWは対称行列であるのでW=Wとした。
F v {\displaystyle F_{v}} の行は f ( x , y ) {\displaystyle f(x,y)} のx行目の行を1次元DFTしたものである。ゆえに F v {\displaystyle F_{v}} は f ( x , y ) {\displaystyle f(x,y)} の各行の1次元DFTした結果の行ベクトルを集めたものになる。F=WFvにおける、Fvを後から掛ける作用素は F v {\displaystyle F_{v}} の列の1次元DFTしたものと同じと考えて良い。
つまり、2次元DFT(2次元フーリエ変換も同様だが)は f ( x , y ) {\displaystyle f(x,y)} を、各行ごとに1次元DFTし、その結果をさらに各列ごとに1次元DFTする事と等価である。ここで、1次元DFTの計算はFFTのアルゴリズムで高速に計算できる。そのため実用上は2次元DFTも、2次元FFTとして計算される。
離散フーリエ変換 F n = 1 N ∑ k = 0 N − 1 f k e − i 2 n π N k {\displaystyle F_{n}={\dfrac {1}{N}}\sum _{k=0}^{N-1}f_{k}e^{-i{\dfrac {2n\pi }{N}}k}}
離散フーリエ逆変換 f k = ∑ n = 0 N − 1 F n e i 2 n π N k {\displaystyle f_{k}=\sum _{n=0}^{N-1}F_{n}e^{i{\dfrac {2n\pi }{N}}k}} とするところもある(図解雑学 フーリエ変換)。
これは、フーリエ変換を F ( ω ) = ∫ − ∞ ∞ f ( x ) e − i ω x d x {\displaystyle F(\omega )=\int _{-\infty }^{\infty }f(x)e^{-i\omega x}dx} 、フーリエ逆変換を f ( x ) = 1 2 π ∫ − ∞ ∞ F ( ω ) e i ω x d ω {\displaystyle f(x)={\dfrac {1}{2\pi }}\int _{-\infty }^{\infty }F(\omega )e^{i\omega x}d\omega } としたときの式である。