【数分解説|眺めて理解】高速フーリエ変換 FFT: 離散フーリエ変換を回転因子の特性を活かしてコンピュータでの計算を高速にし計算量をNlogNにする手法.【高速フーリエ変換4/4】
HTML-код
- Опубликовано: 4 окт 2024
- 高速フーリエ変換は、離散的周期的な時間領域と周波数領域を双方に変換できる離散フーリエ変換を高速に計算する手法です. 実際にコンピュータ上の計算で計算すると、通常Nの2乗のオーダになりますが、高速フーリエ変換によってN log Nのオーダーまで落とすことができます. 行列演算を行を入れ替えたり分解することで、計算回数を落としていきます. 高速フーリエ変換を行うときにデータ数は2の何畳かである必要があります.
ビットリバースやバタフライ演算などの活用によって高速に計算することができます. なぜ2乗なのか、なぜ偶数行と奇数行を入れ替えると良いのか、なぜ同じ行列が現れるのか、-1を掛けた行列が現れるのかを詳細に解説します,
高速フーリエ変換をわかりやすく解説するためのpart 4の動画になります.
複素フーリエ級数展開やフーリエ変換、離散フーリエ変換を抑えた上でご視聴ください.
今回は高速フーリエ変換を11分で紹介します.
ThothChildrenは数分でアルゴリズムのポイントをわかりやすく簡単に理解できること、メリットデメリットの把握を目指した解説を投稿する動画チャンネルです.
技術学術集積所 : ThothChildrenVideo
アニメーションを目で見て理解するアルゴリズム
www.thothchildr...
ThothChildrenのわかりやすい解説記事 : 高速フーリエ変換FFT
www.thothchildr... #ThothChildren
参考:
【数分解説】離散フーリエ変換: 離散的周期的な時間領域と周波数領域の間を双方に変換. 周波数とその強さを求める. コンピュータでの計算を可能にする手法【高速フーリエ変換3/4】
• 【数分解説】離散フーリエ変換: 離散的周期...
【数分解説】フーリエ変換: 時間領域と周波数領域の間を双方に変換. 周波数とその強さを求める. 複素フーリエ級数展開の導出から【高速フーリエ変換2/4】
• 【数分解説】フーリエ変換: 時間領域と周波...
【数分解説】フーリエ級数展開: ほぼ全ての関数を重み付けしたsin関数とcos関数等の三角関数の和で表現し周波数の分析を行う. 特定の区間を繰り返す周期関数が対象.【高速フーリエ変換1/4】
• 【数分解説】フーリエ級数展開: ほぼ全ての関...
【概要速修】Stable Diffusion(テキストから画像生成)はどうやって実現するのかざっくり仕組みを知る(DiffusionModel,Deep Learninig)【機械学習解説動画】
• 【概要速修】Stable Diffusion...
【疑問】答えたくない質問(やましい、プライベートな言えないこと)に正直に答えてもらうには?【技術テーマ】
• 【疑問】答えたくない質問(やましい、プライベ...
【数分解説】LU分解: 行列を上三角行列と下三角行列に分解して高速に連立一次方程式や行列式を求める【LU Decomposition】
• 【数分解説】LU分解: 行列を上三角行列と下...
【数分解説】ハフマン符号: パターンの出現確率に応じて符号長さを調整する汎用的な圧縮を実現する【Huffman Code】
• 【数分解説】ハフマン符号: パターンの出現確...
【数分解説】GrabCut(GraphCut): 指定された領域やヒントで画像から物体を切出したい【画像処理/グラブカット】
• 【数分解説】GrabCut(GraphCut...
【数分解説】尤度(尤度関数): あるデータが与えられる時そのデータが出やすいパラメータを求める評価値が欲しい【Likelihood Function】
• 【数分解説】尤度(尤度関数): あるデータが...
【数分解説】パーティクルフィルタ(粒子フィルタ): 観測できない内部の状態の予測分布を粒子で表現して、観測値と制御量、ひとつ前の予測から次の予測をしたい【Particle Filter】
• 【数分解説】パーティクルフィルタ(粒子フィル...
【数分解説】決定木学習(前編:基本とID3): 特徴量から予測でき、重要な特徴量を把握、判断を説明できる軽量な学習がしたい【DecisionTree Model】
• 【数分解説】決定木学習(前編:基本とID3)...
【数分解説】混合ガウス分布: 複数のガウス分布の足し合わせで確率分布を表現したい【Gaussian Mixture Model : GMM】
• 【数分解説】混合ガウス分布: 複数のガウス分...
【数分解説】K-means法(k平均法) : クラスタ数を指定してデータを分割、クラスタリングしたい
• 【数分解説】K-means法(k平均法) :...
【数分解説】ベイズとかp(A|B)、画像や文字列を絡めた確率、条件付き確率のイメージを持てるようにする解説動画【初学者向け】
• 【数分解説】ベイズとかp(A|B)、画像や文...
【数分解説】ラグランジュの未定乗数法 : 拘束条件を守りつつ関数の値を最大化するパラメータを求めたい【Lagrange multiplier】
• 【数分解説】ラグランジュの未定乗数法 : ...
【数分解説】レーベンバーグ・マーカート法 : 非線形な式を扱う場合でも関数の極小値を高速に求めたい:関数フィッティングなどに応用【Levenberg-Marquardt algorithm】
• 【数分解説】レーベンバーグ・マーカート法 ...
【数分解説】ガウス・ニュートン法 : 非線形な式を扱う場合でも関数の極小値を高速に求めたい:関数フィッティングなどに応用【Gauss Newton Method】
• 【数分解説】ガウス・ニュートン法 : 非線...
【数分解説】ニュートン法による最適化 : 非線形な式を扱う場合でも関数の極小値を求めたい:関数フィッティングなどに応用【Newton Methods】
• 【数分解説】ニュートン法による最適化 : ...
【数分解説】拡張カルマンフィルタ : 非線形でもノイズを考慮してリアルタイムに直接観測できない状態を推定したい【Extended Kalman FIlter】
• 【数分解説】拡張カルマンフィルタ : 非線...
【数分解説】カルマンフィルタ : ノイズを考慮してリアルタイムに直接観測できない状態を推定したい【Kalman FIlter】
• 【数分解説】カルマンフィルタ : ノイズを...
【数分解説】ベイズ更新 : データを受けて確率を逐次的に更新して推定したい
• 【数分解説】ベイズ更新 : データを受けて確...
ThothChildren
www.thothchildr...
抜粋:
今日は高速フーリエ変換についてです.それでは早速始めましょう.
高速フーリエ変換は離散フーリエ変換を高速化する手法です.
行列の分割や入れ替え、回転因子の周期性や対称性の活用によって同様の計算を省略することができ、通常の方法ではNの2乗のオーダーの計算がN log Nのオーダーまで落とすことができます.
フーリエ級数展開ではsinとcosで関数を表現していました.
時間は連続で周期的な関数でしたが、周波数は離散値でした.
これをオイラーの公式で整理したのが、複素フーリエ級数展開です.
区間を無限にすることでフーリエ変換を得られました. 時間も周波数も連続した周期的でない関数です.
しかし、コンピュータでは離散的な値が必要なので、周期的で離散的な離散フーリエ変換を導出しました.通常この離散フーリエ変換では遅すぎるため、計算を工夫した高速フーリエ変換を使います.
それでは、まず離散フーリエ変換で使う回転因子の復習と前提として大事なポイントを紹介します.
回転因子の重要な特性の一つが、先ほどから言及している周期性です. データが8個ならn上に8上を足した時と同じ値になります.
もうひとつ大事な要素として対称性があります.
高速フーリエ変換はNが2の冪乗であること、つまり、8や32などの場合のみ使うことができます. 下記ではNが8の時で考えてみます.
それではこの処理を少し整理したバタフライ演算、計算量、ビットリバースの形で見てみます.
ということはこのbit列を逆順にしたら数字が大きくなりそうです.
実際に順番を反転させるとこの様になり、数字にするとこの様になっています.
綺麗に上から数字順にならんでいます.
つまり、元の添字を2進数にして、bitを逆順に並べて、それが表す数字順に並び替えると元の大文字Fがどの行で出力されるかがわかります.
ビットリバース、バタフライ演算、なぜ行を入れ替えるのかに詳しく図解で解説します.
この世のFFTの解説の中で1番分かりやすい
天才的にわかりやすい... どうやって動画つくってるのかすごい気になります
ぞぞちるどれん最近はまってます
す、すごい
Pythonのディープラーニングでフーリエ変換やると頭おかしなるで