アカウント名:
パスワード:
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の場合、そんなに周波数分解能が良くないので>ところでこれはどういう意味？窓関数の辺りのこと(データの最初と終わりが不連続になってピークが広がりを持つ)ことを言ってるのではないの？あるいは離散ポイント間を矩形近似してることの誤差とか？
いやだから、私が >>そもそもDFTって言葉の意味もわかってないでしょ？って書いたのは、翻訳のしょっぱなに >>DFT（短時間フーリエ変換）なんて書いてるので、一般のDFTの話を勝手に短時間FTに限定しているから。DFTといえば時系列データが対象で実用上窓関数が必須、と思い込んでいるようだが、あなたの従事する分野でそうだったとしても、一般を論じている今回の論文とは全く関係ないことですよね。FFTには例えば3次元のカルテシアン座標上でポアソン方程式をスペクトル法で解く、なんていう窓関数とは無縁の用途もたくさんあるわけで。だか
批判の理由を書いたので ggy も評価。正解も不正解も私には判断できないが乗りかかった船に最後までつきあう姿勢が立派。
言い訳が長すぎて、読む気が起きないので評価しない。長い言い訳が必要と言うことは、最初のコメントに遡って無価値と判断。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
最初のバージョンは常に打ち捨てられる。
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)
いやだから、私が
>>そもそもDFTって言葉の意味もわかってないでしょ？
って書いたのは、翻訳のしょっぱなに
>>DFT（短時間フーリエ変換）
なんて書いてるので、一般のDFTの話を勝手に短時間FTに限定しているから。
DFTといえば時系列データが対象で実用上窓関数が必須、と思い込んでいるようだが、あなたの従事する分野でそうだったとしても、一般を論じている今回の論文とは全く関係ないことですよね。
FFTには例えば3次元のカルテシアン座標上でポアソン方程式をスペクトル法で解く、なんていう窓関数とは無縁の用途もたくさんあるわけで。
だか
Re: (スコア:0)
批判の理由を書いたので ggy も評価。
正解も不正解も私には判断できないが乗りかかった船に最後までつきあう姿勢が立派。
Re:なんじゃこりゃ (スコア:1)
言い訳が長すぎて、読む気が起きないので評価しない。
長い言い訳が必要と言うことは、最初のコメントに遡って無価値と判断。
the.ACount