アカウント名:
パスワード:
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スパースなデータであれば②程度。外れていれば誤差が増える。
１０倍早いという感じは受けなかったのですが、 イメージ的には全データ1024個だったら、フーリエ変換した後の結果が ０以外のデータ102以下、ほとんど０データが残992個であれば、 ②の演算が採用でき、k=102, n=1024としてFFTに比べ10倍高速ですね。
FFT (高速フーリエ・コサイン・サイン変換) の概略と設計法 [kyoto-u.ac.jp]などにあるように、基底(=2.7が最適）から始め、Cooley-Tukey型FFT、Prime Factor型FFT、実数限定など組み方次第、メモリアクセスや、ＣＰＵキャッシュなどの実環境でFFTの演算スピードなんて大きく変わりすぎるので、なんとも言えませんが。
※リンク先 [kyoto-u.ac.jp]はSETI@homeに使われているFFTなども載っています。
以下、意訳---我々はn次DFTのkスパースな近似を計算する問題について提案する。我々は以下の2つのアルゴリズムを示す。
・入力信号が最大でもk個の非ゼロフーリエ係数を持つ(＝kスパース)入力信号に対する計算量O(k log n)アルゴリズム・一般的な入力に対する計算量O(k log n log(n/k))のアルゴリズム
両方のアルゴリズムとも、どんなkであってもk = O(n)を満たし、、オーダーはO(n log n)より改善される。よってFFTより高速であるといえる。
なお、これらのアルゴリズムはFFTより高速な条件を満たす初めてのものとなる。また、もしFFTが最適であるとしても、kスパースなケースではあらゆるkについてk=n^Ω(1)を満たすので、確かに最適なアルゴリズムとなる。
一般的な信号の"疎フーリエ変換"を計算するための任意のアルゴリズムは、それが適応的サンプリングを行った場合でも、少なくともΩ(K log（n/ k）log log n)個の信号データを使用する必要があることを我々は示すことによって、提案アルゴリズムの結果を補足した。
長くなったのでこちらに。
MemCalc百問百答 [gms-jp.com]などにも載っていますが、適応化フィルタの理想タップ数は、赤池情報量規準AICなどで予想できます。
今回のNOSFTが要求しているフーリエ結果がｋスパースな入力データというものも、AICからある程度予測できそうな気がします。これはAICから予測できる理想タップ数が、含まれている周波数の種別の数になっているからです。
AICの理論はよく判りませんが、入力データを行列とみなして対角化し、行列の固有値を大きいほうから並べ、変曲点までの個数を数え、それを理想タップ数とします。これが周波数の種別の数になります。（正確には定常エルゴート過程にある自己相関関係にある周波数の数）
適応フィルタは、含まれている周波数の数の分だけタップ数にすると安定です。タップ数がむやみに大きいとニセピークなどが現れます。NOSFTもnに比べ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)に設定を変更する必要があります。
犯人はmoriwaka -- Anonymous Coward
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スパースなデータであれば②程度。外れていれば誤差が増える。
１０倍早いという感じは受けなかったのですが、
イメージ的には全データ1024個だったら、フーリエ変換した後の結果が
０以外のデータ102以下、ほとんど０データが残992個であれば、
②の演算が採用でき、k=102, n=1024としてFFTに比べ10倍高速ですね。
FFT (高速フーリエ・コサイン・サイン変換) の概略と設計法 [kyoto-u.ac.jp]などにあるように、
基底(=2.7が最適）から始め、Cooley-Tukey型FFT、Prime Factor型FFT、
実数限定など組み方次第、メモリアクセスや、ＣＰＵキャッシュなどの実環境で
FFTの演算スピードなんて大きく変わりすぎるので、なんとも言えませんが。
※リンク先 [kyoto-u.ac.jp]はSETI@homeに使われているFFTなども載っています。
以下、意訳
---
我々はn次DFTのkスパースな近似を計算する問題について提案する。
我々は以下の2つのアルゴリズムを示す。
・入力信号が最大でもk個の非ゼロフーリエ係数を持つ(＝kスパース)入力信号に対する計算量O(k log n)アルゴリズム
・一般的な入力に対する計算量O(k log n log(n/k))のアルゴリズム
両方のアルゴリズムとも、どんなkであってもk = O(n)を満たし、、
オーダーはO(n log n)より改善される。よってFFTより高速であるといえる。
なお、これらのアルゴリズムはFFTより高速な条件を満たす初めてのものとなる。
また、もしFFTが最適であるとしても、kスパースなケースではあらゆるkについて
k=n^Ω(1)を満たすので、確かに最適なアルゴリズムとなる。
一般的な信号の"疎フーリエ変換"を計算するための任意のアルゴリズムは、
それが適応的サンプリングを行った場合でも、
少なくともΩ(K log（n/ k）log log n)個の信号データを使用する必要があることを
我々は示すことによって、提案アルゴリズムの結果を補足した。
Re:NOSFT - 訳してみた (スコア:2)
長くなったのでこちらに。
MemCalc百問百答 [gms-jp.com]などにも載っていますが、
適応化フィルタの理想タップ数は、赤池情報量規準AICなどで予想できます。
今回のNOSFTが要求しているフーリエ結果がｋスパースな入力データというものも、
AICからある程度予測できそうな気がします。
これはAICから予測できる理想タップ数が、含まれている周波数の種別の数に
なっているからです。
AICの理論はよく判りませんが、入力データを行列とみなして対角化し、
行列の固有値を大きいほうから並べ、変曲点までの個数を数え、
それを理想タップ数とします。これが周波数の種別の数になります。
（正確には定常エルゴート過程にある自己相関関係にある周波数の数）
適応フィルタは、含まれている周波数の数の分だけタップ数にすると安定です。
タップ数がむやみに大きいとニセピークなどが現れます。
NOSFTもnに比べ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スパースを言えるほど、スペクトルピークが０が続きません