アカウント名:
パスワード:
DFT（短時間フーリエ変換）した結果がkスパースな（＝ほとんど０ばっかりで、０以外のデータが最大でもｋ個しかない）ような、信号に対して行える高速アルゴリズムの話しのようです。
計算オーダー・DFT O(n^2)・FFT O(n log n)・NOSFT ①O(k log n) ※理想 ②O(k log n log(n/k)) ※一般的な入力
ただしk≦n, フーリエ変換結果がkスパースな場合。 理想的には、ｋスパースなデータであれば①なんでしょうけど、 わりあいkスパースなデータであれば②程度。外れていれ
リンク先 [srad.jp]にある、グラフをみてみましたが、特に４番目 [mit.edu]ですが、
n=2^22=4194304, k=100 FFTW ：550msec sFFT1.0 ： 55msec
周波数差として、0.0016%幅の中に全てのピークが入るような時にやっとFFTより10倍速い。おっそろしく正弦波な感じのイメージ。
理論的には速いのかもしれませんが、実装上は、今のところ評価不能な感じです（とても遅い。入力波形に制限がある）
>k個の非ゼロ値が連続している必要はない
それはそうなのですが、DFTの場合、そんなに周波数分解能が良くないので、4194304タップ中、・100タップのみが非ゼロ値・あとの4194204タップが０なんてフーリエ値（＝パワースペクトル）というのは非現実的な気がするのです。考え方が間違っているのかな（でも他のグラフも同じような傾向のようです）
>そもそもDFTって言葉の意味もわかってないでしょ？離散フーリエ変換discrete Fourier transform、DFTたたみこみ演算で計算することが多い。
高速フーリエ変換(FFT)も説明が必要ですか？
>なんか賢いつもりで翻訳の真似事してるけど、>ggy (39364)
無いものは自分でやる主義ですから。
ごめん、改行失敗した、再送
>>高速フーリエ変換(FFT)も説明が必要ですか？なんというか、苦笑いしか出てこないけど、バカにされたと思ったならごめんね。あきらかに誤読しているのに自信満々に書いてて、あげくに「なんじゃこりゃ 」とか「保留」とか上から目線で批評してるので、指摘してあげないと他の読者にまずいと思ったので。
>>DFTの場合、そんなに周波数分解能が良くないので ところでこれはどういう意味？ なぜ勝手に分解能が良くないと決めるの？
> >>DFTの場合、そんなに周波数分解能が良くないので>ところでこれはどういう意味？窓関数の辺りのこと(データの最初と終わりが不連続になってピークが広がりを持つ)ことを言ってるのではないの？あるいは離散ポイント間を矩形近似してることの誤差とか？
>窓関数の辺りのこと(データの最初と終わりが不連続になって>ピークが広がりを持つ)ことを言ってるのではないの？>あるいは離散ポイント間を矩形近似してることの誤差とか？
もっと根本的なもので、FFTではたとえ単一周波数でも、スペクトルの裾野が広がってしまう（＝スパースでない）ように思います。
周波数分解能はどのように決めるのか？ [onosokki.co.jp]>FFT法>スペクトルの瞬時時間変動を見たい場合には時間分解能を上げる>（そのためには時間窓長を小さくする）必要があり、>（1）式から周波数分解能が悪くなる。これより、通常の FFT分析では>スペクトルの時間分解能と周波数分解能とは逆数の関係となる。
FFTでは最短でも１周期分の波形長が必要で、周波数x時間分解能がある一定以下になりません。通常（とは言っても、私の考える通常ですが）、FFTはスパースを云々できるほど、スペクトルピークが０が続くことはありません。
スペクトル解析法 [wakwak.com]>最大エントロピー法(MEM：Maximum Entropy Method)と言う スペクトル解析法があります。それは...>有限な測定データからそれだけでは測定不可能な大きなラグを持つ 自己相関関数を情報エントロピーが最大となるように推定することにより スペクトル推定を行う。>したがって 無限に続く信号（現象）の一部分だけからスペクトル解析をす るのに適している。>FFTと比較すると スペクトルの分解能が高い・ 信号の周期に対してデータ長が短くてもスペクトル推定が出来る・ 雑音に対して比較的強い etc.>MEMの使用上の注意点としては 自己回帰モデルの次数決定が難しい最終予測誤差 （FPE：Final Prediction Error）を用いているが どのデータでもこの方法がうまく行くとは限らない・ スペクトルの推定結果は和とはならない(高さは保証されない)・ FFTに比べ計算時間が長い etc.
MEMでもAR, RLS, QRD-LSLだろうと何でも良いのですが、３タップ程度の自己回帰モデルを決め、タップからウィーナー‐ヒンチンの定理でパワースペクトルを求めると、周波数分解能が（FFTに比べ)飛躍的に向上します(k→小のkスパースが言えるほどの）。
１周期の波形をFFTした結果のパワースペクトルの裾野の広がりは、０．２周期程度の波形を自己回帰モデルからパワースペクトル求めたものと同じ印象です。そういった意味で、FFTは分解能が悪いとしました。私が扱う音声解析や、生体信号など扱うレベルでは、FFTの分解能は悪いです。kスパースを言えるほど、スペクトルピークが０が続きません
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
UNIXはシンプルである。必要なのはそのシンプルさを理解する素質だけである -- Dennis Ritchie
NOSFT - 訳してみた (スコア:3, 興味深い)
DFT（短時間フーリエ変換）した結果がkスパースな
（＝ほとんど０ばっかりで、０以外のデータが最大でもｋ個しかない）
ような、信号に対して行える高速アルゴリズムの話しのようです。
計算オーダー
・DFT O(n^2)
・FFT O(n log n)
・NOSFT ①O(k log n) ※理想
②O(k log n log(n/k)) ※一般的な入力
ただしk≦n, フーリエ変換結果がkスパースな場合。
理想的には、ｋスパースなデータであれば①なんでしょうけど、
わりあいkスパースなデータであれば②程度。外れていれ
なんじゃこりゃ (スコア:2)
リンク先 [srad.jp]にある、グラフをみてみましたが、
特に４番目 [mit.edu]ですが、
n=2^22=4194304, k=100
FFTW ：550msec
sFFT1.0 ： 55msec
周波数差として、0.0016%幅の中に全てのピークが入るような時に
やっとFFTより10倍速い。おっそろしく正弦波な感じのイメージ。
理論的には速いのかもしれませんが、
実装上は、今のところ評価不能な感じです（とても遅い。入力波形に制限がある）
Re: (スコア:1)
Re: (スコア:1)
>k個の非ゼロ値が連続している必要はない
それはそうなのですが、DFTの場合、そんなに周波数分解能が良くないので、
4194304タップ中、
・100タップのみが非ゼロ値
・あとの4194204タップが０
なんてフーリエ値（＝パワースペクトル）というのは非現実的な気がするのです。
考え方が間違っているのかな（でも他のグラフも同じような傾向のようです）
Re: (スコア:1)
Re: (スコア:1)
>そもそもDFTって言葉の意味もわかってないでしょ？
離散フーリエ変換discrete Fourier transform、DFT
たたみこみ演算で計算することが多い。
高速フーリエ変換(FFT)も説明が必要ですか？
>なんか賢いつもりで翻訳の真似事してるけど、
>ggy (39364)
無いものは自分でやる主義ですから。
Re: (スコア:1)
Re: (スコア:1)
ごめん、改行失敗した、再送
>>高速フーリエ変換(FFT)も説明が必要ですか？
なんというか、苦笑いしか出てこないけど、
バカにされたと思ったならごめんね。
あきらかに誤読しているのに自信満々に書いてて、
あげくに「なんじゃこりゃ 」とか「保留」とか
上から目線で批評してるので、指摘してあげないと
他の読者にまずいと思ったので。
>>DFTの場合、そんなに周波数分解能が良くないので
ところでこれはどういう意味？
なぜ勝手に分解能が良くないと決めるの？
Re: (スコア:0)
> >>DFTの場合、そんなに周波数分解能が良くないので
>ところでこれはどういう意味？
窓関数の辺りのこと(データの最初と終わりが不連続になってピークが広がりを持つ)ことを言ってるのではないの？
あるいは離散ポイント間を矩形近似してることの誤差とか？
Re:なんじゃこりゃ (スコア:1)
>窓関数の辺りのこと(データの最初と終わりが不連続になって
>ピークが広がりを持つ)ことを言ってるのではないの？
>あるいは離散ポイント間を矩形近似してることの誤差とか？
もっと根本的なもので、FFTではたとえ単一周波数でも、スペクトルの裾野が
広がってしまう（＝スパースでない）ように思います。
周波数分解能はどのように決めるのか？ [onosokki.co.jp]
>FFT法
>スペクトルの瞬時時間変動を見たい場合には時間分解能を上げる
>（そのためには時間窓長を小さくする）必要があり、
>（1）式から周波数分解能が悪くなる。これより、通常の FFT分析では
>スペクトルの時間分解能と周波数分解能とは逆数の関係となる。
FFTでは最短でも１周期分の波形長が必要で、周波数x時間分解能がある一定以下になりません。
通常（とは言っても、私の考える通常ですが）、FFTはスパースを云々できるほど、
スペクトルピークが０が続くことはありません。
スペクトル解析法 [wakwak.com]
>最大エントロピー法(MEM：Maximum Entropy Method)と言う スペクトル解析法があります。それは...
>有限な測定データからそれだけでは測定不可能な大きなラグを持つ 自己相関関数を情報エントロピーが最大となるように推定することにより スペクトル推定を行う。
>したがって 無限に続く信号（現象）の一部分だけからスペクトル解析をす るのに適している。
>FFTと比較すると スペクトルの分解能が高い・ 信号の周期に対してデータ長が短くてもスペクトル推定が出来る・ 雑音に対して比較的強い etc.
>MEMの使用上の注意点としては 自己回帰モデルの次数決定が難しい最終予測誤差 （FPE：Final Prediction Error）を用いているが どのデータでもこの方法がうまく行くとは限らない・ スペクトルの推定結果は和とはならない(高さは保証されない)・ FFTに比べ計算時間が長い etc.
MEMでもAR, RLS, QRD-LSLだろうと何でも良いのですが、３タップ程度の自己回帰モデルを決め、
タップからウィーナー‐ヒンチンの定理でパワースペクトルを求めると、周波数分解能が
（FFTに比べ)飛躍的に向上します(k→小のkスパースが言えるほどの）。
１周期の波形をFFTした結果のパワースペクトルの裾野の広がりは、
０．２周期程度の波形を自己回帰モデルからパワースペクトル求めたものと同じ印象です。
そういった意味で、FFTは分解能が悪いとしました。
私が扱う音声解析や、生体信号など扱うレベルでは、FFTの分解能は悪いです。
kスパースを言えるほど、スペクトルピークが０が続きません