FFT

フーリエ変換

フーリエ変換は、物理学や数学でよく登場し、そのため日常生活でも多くの場面で使われています。

簡単に言うと、フーリエ変換は時間や空間の領域で表された入力信号を受け取り、それを周波数の領域へと変換します。 もう少し具体的には、異なる周波数が混ざり合った（つまり重ね合わさった）入力信号に対して、変換はそれぞれの周波数を分離し、その相対的な強さを示します。

このことから、フーリエ変換は信号処理（フィルタリングや圧縮など）や多くのデータサイエンスの応用における中心的な道具となっています。 そのため、最初に想像するよりもずっと広く使われており、フーリエ変換の出力が一般には複素数であることを考えると、虚数が欠かせないものになる代表的な例でもあります。

フーリエ変換には積分を使った定式化もありますが、ここで扱うのはデジタルの世界なので、興味があるのは離散版です。 変換の導出はこの演習の範囲を超えていますが、順方向の離散変換（周波数領域への変換）は次の形をとります： Xₖ = Σ xₙ * ℯ^(-2iπk * n/N) ここで、和はnについてとり、Nはサンプル数、kは周波数、iは虚数単位、xₙは個々のサンプルです。

高速フーリエ変換

フーリエ変換は非常に有用ですが、素朴に実装すると少し遅いです（O(n²)）。 高速フーリエ変換（FFT）は、これを劇的に高速化するアルゴリズムです。 これは通常、分割統治の戦略によって行われ、定式化の中のある種の対称性を利用することで、漸近的にO(Nlog(N))の計算量になります。 この高速化により、変換の実用性と応用範囲が大きく向上します。