アカウント名:
パスワード:
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の場合、そんなに周波数分解能が良くないので>ところでこれはどういう意味？窓関数の辺りのこと(データの最初と終わりが不連続になってピークが広がりを持つ)ことを言ってるのではないの？あるいは離散ポイント間を矩形近似してることの誤差とか？
私は wakatonoo2 を評価する。正解も不正解も私には判断できないが情報展開する姿勢が立派。改行すら失敗するggyは自分では何もせず上から目線で批評しかしてないので信用しない。
いやだから、私が >>そもそもDFTって言葉の意味もわかってないでしょ？って書いたのは、翻訳のしょっぱなに >>DFT（短時間フーリエ変換）なんて書いてるので、一般のDFTの話を勝手に短時間FTに限定しているから。DFTといえば時系列データが対象で実用上窓関数が必須、と思い込んでいるようだが、あなたの従事する分野でそうだったとしても、一般を論じている今回の論文とは全く関係ないことですよね。FFTには例えば3次元のカルテシアン座標上でポアソン方程式をスペクトル法で解く、なんていう窓関数とは無縁の用途もたくさんあるわけで。だから、この人はDFTって言葉の意味すらわかってないんじゃないか、と思ったわけ。
>>窓関数の辺りのこと(データの最初と終わりが不連続になってピークが広がりを持つ)ことを言ってるのではないの？
この発言もちょっとおかしくて、窓関数が前提なことがそもそも間違いなのは先に指摘したとおりだけど、窓関数はサンプル区間の境界でデータの不連続をなくすために適用するもんなので、言っていることが意味不明。窓関数を適用しないでぶった切る、つまり「矩形窓」を使うんだったら確かに不連続になってしまうけど、データの不連続が問題なんだったらそうならないような窓関数を適用するべきで、窓関数っていうのは普通はそういうものを指す。
で、窓関数があろうがなかろうが関係なく、この論文は変換後の波数空間でk個の非ゼロ値が連続しているなんて前提は一切ないのに、 あなたは、じゃなかったwakatonoo2氏は、著しい誤読の挙句、まるで意味がないかのような批評をしているので、誰か理解している人が指摘してあげないといけないでしょ？
あと、>>離散ポイント間を矩形近似してることの誤差とかこんなこと言い出したらこの論文の手法どころか、DFTそのものが無意味と言っているようなもんですよ。FFTなんて速くてもまったく意味がない、って言ってるのと同じです。もちろんそんなわけはなくて、離散化の誤差が問題になるのだったら問題にならないほど高いサンプリングレートをとる、あるいはレートが不十分ならそんな高周波は解析対象としない(できない)、です。
矩形近似ってのも意味わからんですが。サンプルは点でとるので、FFTのアルゴリズム自体にそのサンプル間をどう補間するかという前提は全くないですよ。強いて言えば正弦波の重ね合わせで補間する、ですかね。少なくとも矩形補間ではないですね。
とまあ、乗りかかった舟なんで、私の知識で指摘できることは指摘してきます。
批判の理由を書いたので ggy も評価。正解も不正解も私には判断できないが乗りかかった船に最後までつきあう姿勢が立派。
言い訳が長すぎて、読む気が起きないので評価しない。長い言い訳が必要と言うことは、最初のコメントに遡って無価値と判断。
>窓関数の辺りのこと(データの最初と終わりが不連続になって>ピークが広がりを持つ)ことを言ってるのではないの？>あるいは離散ポイント間を矩形近似してることの誤差とか？
もっと根本的なもので、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: (スコア:0)
私は wakatonoo2 を評価する。
正解も不正解も私には判断できないが情報展開する姿勢が立派。
改行すら失敗するggyは自分では何もせず上から目線で批評しかしてないので信用しない。
Re:なんじゃこりゃ (スコア:1)
いやだから、私が
>>そもそもDFTって言葉の意味もわかってないでしょ？
って書いたのは、翻訳のしょっぱなに
>>DFT（短時間フーリエ変換）
なんて書いてるので、一般のDFTの話を勝手に短時間FTに限定しているから。
DFTといえば時系列データが対象で実用上窓関数が必須、と思い込んでいるようだが、あなたの従事する分野でそうだったとしても、一般を論じている今回の論文とは全く関係ないことですよね。
FFTには例えば3次元のカルテシアン座標上でポアソン方程式をスペクトル法で解く、なんていう窓関数とは無縁の用途もたくさんあるわけで。
だから、この人はDFTって言葉の意味すらわかってないんじゃないか、と思ったわけ。
>>窓関数の辺りのこと(データの最初と終わりが不連続になってピークが広がりを持つ)ことを言ってるのではないの？
この発言もちょっとおかしくて、窓関数が前提なことがそもそも間違いなのは先に指摘したとおりだけど、窓関数はサンプル区間の境界でデータの不連続をなくすために適用するもんなので、言っていることが意味不明。
窓関数を適用しないでぶった切る、つまり「矩形窓」を使うんだったら確かに不連続になってしまうけど、データの不連続が問題なんだったらそうならないような窓関数を適用するべきで、窓関数っていうのは普通はそういうものを指す。
で、窓関数があろうがなかろうが関係なく、この論文は変換後の波数空間でk個の非ゼロ値が連続しているなんて前提は一切ないのに、 あなたは、じゃなかったwakatonoo2氏は、著しい誤読の挙句、まるで意味がないかのような批評をしているので、誰か理解している人が指摘してあげないといけないでしょ？
あと、
>>離散ポイント間を矩形近似してることの誤差とか
こんなこと言い出したらこの論文の手法どころか、DFTそのものが無意味と言っているようなもんですよ。
FFTなんて速くてもまったく意味がない、って言ってるのと同じです。
もちろんそんなわけはなくて、離散化の誤差が問題になるのだったら問題にならないほど高いサンプリングレートをとる、あるいはレートが不十分ならそんな高周波は解析対象としない(できない)、です。
矩形近似ってのも意味わからんですが。
サンプルは点でとるので、FFTのアルゴリズム自体にそのサンプル間をどう補間するかという前提は全くないですよ。
強いて言えば正弦波の重ね合わせで補間する、ですかね。
少なくとも矩形補間ではないですね。
とまあ、乗りかかった舟なんで、私の知識で指摘できることは指摘してきます。
Re: (スコア:0)
批判の理由を書いたので ggy も評価。
正解も不正解も私には判断できないが乗りかかった船に最後までつきあう姿勢が立派。
Re:なんじゃこりゃ (スコア:1)
言い訳が長すぎて、読む気が起きないので評価しない。
長い言い訳が必要と言うことは、最初のコメントに遡って無価値と判断。
the.ACount
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スパースを言えるほど、スペクトルピークが０が続きません