あるAnonymous Coward 曰く、MITの研究者らが、高速フーリエ変換（FFT）より高速なフーリエ変換アルゴリズムを開発しているそうだ（MIT news、論文）。MIT newsによると、このアルゴリズムは特定の状況下においては従来のFFTと比べ10倍も高速に実行できるという。信号を一定の帯域幅ごとに分割して処理する、というのがポイントのようだ。この手法では、信号に含まれる周波数分布が疎であるほど高速化できるらしい。
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:なんじゃこりゃ (スコア:1)
いやだから、私が
>>そもそもDFTって言葉の意味もわかってないでしょ？
って書いたのは、翻訳のしょっぱなに
>>DFT（短時間フーリエ変換）
なんて書いてるので、一般のDFTの話を勝手に短時間FTに限定しているから。
DFTといえば時系列データが対象で実用上窓関数が必須、と思い込んでいるようだが、あなたの従事する分野でそうだったとしても、一般を論じている今回の論文とは全く関係ないことですよね。
FFTには例えば3次元のカルテシアン座標上でポアソン方程式をスペクトル法で解く、なんていう窓関数とは無縁の用途もたくさんあるわけで。
だから、この人はDFTって言葉の意味すらわかってないんじゃないか、と思ったわけ。
>>窓関数の辺りのこと(データの最初と終わりが不連続になってピークが広がりを持つ)ことを言ってるのではないの？
この発言もちょっとおかしくて、窓関数が前提なことがそもそも間違いなのは先に指摘したとおりだけど、窓関数はサンプル区間の境界でデータの不連続をなくすために適用するもんなので、言っていることが意味不明。
窓関数を適用しないでぶった切る、つまり「矩形窓」を使うんだったら確かに不連続になってしまうけど、データの不連続が問題なんだったらそうならないような窓関数を適用するべきで、窓関数っていうのは普通はそういうものを指す。
で、窓関数があろうがなかろうが関係なく、この論文は変換後の波数空間でk個の非ゼロ値が連続しているなんて前提は一切ないのに、 あなたは、じゃなかったwakatonoo2氏は、著しい誤読の挙句、まるで意味がないかのような批評をしているので、誰か理解している人が指摘してあげないといけないでしょ？
あと、
>>離散ポイント間を矩形近似してることの誤差とか
こんなこと言い出したらこの論文の手法どころか、DFTそのものが無意味と言っているようなもんですよ。
FFTなんて速くてもまったく意味がない、って言ってるのと同じです。
もちろんそんなわけはなくて、離散化の誤差が問題になるのだったら問題にならないほど高いサンプリングレートをとる、あるいはレートが不十分ならそんな高周波は解析対象としない(できない)、です。
矩形近似ってのも意味わからんですが。
サンプルは点でとるので、FFTのアルゴリズム自体にそのサンプル間をどう補間するかという前提は全くないですよ。
強いて言えば正弦波の重ね合わせで補間する、ですかね。
少なくとも矩形補間ではないですね。
とまあ、乗りかかった舟なんで、私の知識で指摘できることは指摘してきます。
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スパースを言えるほど、スペクトルピークが０が続きません
並列化性能の方が大事な世界もある (スコア:1)
どこかで何度も誰かが話されているので今更なのですが、
並列性能が遅かったら業界によっては意味が無いです。大規模な計算で FFT がボトルネックになるのは全通信が必要など、並列化に向いていない仕様のためです。そのため超大規模・超並列系ではFFTは使わない方向で進化している。
シングルで10倍速くても、数百並列が限界とすると、15並列くらいできっちりシングル演算の速度を越えることが出来て数千・数万並列くらいまであまり速度劣化がなければそっちの方が結果的に速いです。無論、シングルで速いに越したことはないですが。当然、ここいらの需要は業界によって異なります。それでも単純に10倍速くなると言うのは画期的かとは思いますし、ただのFFTど等程度の並列コストならばそれだけで10倍の規模の計算が出来るわけですので。いやースゲーです。偉い人。すごい人。
# 論文読めって？すんません後で(汗)
# イントロがいきなりDFTっす。そっちの人？ FFTWとかのInterfaceがあるとうれしい気がする。
名前はどうするんだろう (スコア:0)
Faster Fourier transform?
Re:名前はどうするんだろう (スコア:5, おもしろおかしい)
ソースネクストがさりげなく売ります。
#Insanely great!
#をかのゆ
Re: (スコア:0)
最近ソースネクストの名前すら聞かなくなって、Windowsのパッケージソフトはオワコンなんだなあとあらためて思った。スマホと違って意識の高い()ユーザーのせいで広告も行動追跡もろくろく組み込めないし。
Re:名前はどうするんだろう (スコア:1)
ノートン先生とか、ウィルスバスターとか、MS Officeとか、Visual Studioとか、Adobeのソフトとか、初音ミクちゃんとか、えっちなゲームとか、まだまだいろいろあると思うよ。
多くのソフトでパッケージ版の他にダウンロード版も出ていたり、大抵の場合は代替の無料ソフトが見つかったりするようにはなったけど。
1を聞いて0を知れ!
Re:名前はどうするんだろう (スコア:1)
これだけ数挙げても、まだそういう風に言われるとは思わんかった。
> むしろ逃げられないように囲い込んで独占に成功したところしか生き残れていないというイメージ
へー。君はエロゲに囲い込まれてるんだ。よかったね。
それに、MS Officeはダウンロード版もあるんだよ。パッケージが廃れたっていうなら、多くの人がそっちに移行しててもいいはずだよね。
ウィルス対策ソフトだって、今は有料・無料問わずダウンロード版も多くあるし、Officeソフトや開発ソフトと比べたら囲い込みっつーのも少ない。使ってるウィルス対策ソフトが変わって一体誰が気にするっていうんだ?
んで、初音ミクはボーカロイド市場だけでなく、音楽編集ソフトの市場も盛り上げた。
一部のアホが「終わった」と嬉々として騒いでいる中、こういうソフトが生まれて市場が盛り上がったっていうのは、ごく一部の例だとしても十分注目に値することだ。
# 君の意見は実につまらない。
1を聞いて0を知れ!
Re: (スコア:0)
意識の高い()ユーザー
()の中に何を入れようとしたのか気になる
Re: (スコア:0)
Re: (スコア:0)
暗喩、ではないよね。まあでも言いたいことはわかる。
Re:名前はどうするんだろう (スコア:4, 参考になる)
sFFT (Sparse Fast Fourier Transform) [mit.edu]と呼ぶみたいですね。
Re:名前はどうするんだろう (スコア:2)
FTFFT じゃなかったのか…残念。
Re:名前はどうするんだろう (スコア:1)
Re: (スコア:0)
じゃぁ
Further Fast Fourier transform
で。
---
これを使ったProgramを(略
Re:名前はどうするんだろう (スコア:2)
Yet Faster Fourier Transformはどうですか。
新人。プログラマレベルをポケモンで言うと、コラッタぐらい
Re: (スコア:0)
日本語では Dreadnought を超える戦艦が「超ド級/超弩級」 [wikipedia.org]なので、Fast Fourier Transform を超えるのは「超ファ級」ということになるでしょうか。
Re:名前はどうするんだろう (スコア:3)
> 「超ファ級」
ソ。
[udon]
Re: (スコア:0)
爆速とか檄速とかにしといて、更に早くなったら超とか超々とかつければいいんじゃないの
影響度は (スコア:0)
よく知らないので識者に聞きたいのですが
FFTって音声とか周波数とかの超基礎アルゴリズムですよね。
これが10倍速くなったってことは、通信も数倍速くなったりするんですか？
Re:影響度は (スコア:1)
10倍速くなった分、CPUなりDSPの動作時間率が下がれば低消費電力化は期待出来ると思いますが。
Re:影響度は (スコア:1)
通信そのものは速くなりません。
受信後の信号を抜き出す処理が速くなる可能性はありますが、回線上の通信の遅延にくらべたら微々たるものです。
とはいえ、軽量なアルゴリズムが開発されることにより、ソフトウェアが軽量化され、結果的にはCPUリソースその他が有効活用されるようになります。
DSPなどで実装されている場合も、回路やマイクロコードが簡略化できる可能性があり、それは消費電力の低減などに寄与するかもしれません。
現在の通信方式も、FFTで周波数ごとの信号を読みだしていますが、新方式が「特定の状況下で10倍速い」というなら、その特定の状況になりやすい通信方式などが出てくる可能性もありますね。
Re: (スコア:0)
>通信も数倍速くなったりするんですか？
FFTの演算部分が律速になってる場合は速くなるでしょうが、通信だと大抵の場合速度を制限してるのはS/N比だとか帯域だとかな気がしますので、速くならないんじゃないでしょうか。
Re: (スコア:0)
変換のオーバーヘッドが減るだけ
Re: (スコア:0)
一般的な影響はまったくありません
この論文が取り扱っている条件はかなり特殊なものなので、一般的な連続時間信号を離散化して扱う音声処理などとは無関係です
Re: (スコア:0)
>> この論文が取り扱っている条件はかなり特殊なものなので、一般的な連続時間信号を離散化して扱う音声処理などとは無関係です
えっ？ちゃんと論文読みました？
Re: (スコア:0)
FFTは色々な線形演算に応用できるので、それなりに影響は大きいです。
例えば、FFTで「たたみ込み演算」を高速化(高効率化)できるのは有名ですが、
たたみ込み演算は線形デジタルフィルタの演算そのものなので、各種フィルタ演算を
高速化できます。
他にも最近サービスが始まったドコモの Xi は信号の変調、復調にFFTをそのまま使いますので、
計算効率が10倍良くなるとすると、現在ハードウエアでやっているFFT処理が、
ソフトウエアで出来るのではないかと考えたくなります。
でも今回のやつはデータを選ぶようなので応用は限られているような気がします。
たぶん (スコア:0)
高速フーリエ変換だと、サンプル数と基底数が2^nに固定されるけど
この方法だと独立に選べるからそれによって高速に処理できるってこと？
ではないはず (スコア:1)
FFTW のライブラリでも既にサンプル数が 2^a*3^b*5^c*7^d*11^e*13^f (ただし e+f=0 or 1)
が扱えたりする(一応 2^n が最も効率良いはず)のでそういうことではないと思う。
ある程度以上に疎な場合(重みのでかい周波数が多くない場合)に高速に変換できうる
アルゴリズムを作ったというかより一般的に使える形に発展させた、みたいな話に見える。
FFT を使うような場合はデータはある程度は疎であるような気がしなくもないから
結構有用だったりするのかな。ただ、特定の状況で 10 倍くらいだと普通の状況
だとほとんど効かないんじゃ、的なことはありえるかも。あと不可逆になるのかなぁ。
# 論文はちらっと見たけど速攻で諦めた。無理。
非可逆圧縮専用? (スコア:0)
>信号に含まれる周波数分布が疎であるほど
非可逆な希ガス。成分の存在はどうやって判定するんだろう。決めうち?
あらかじめ分布を知っていないといけないの?
IFFTやって元の信号に戻らないなら、応用は限定されるね。
OFDMのこのキャリア(周波数)要らない!ってのなら使えるかな。
Re:非可逆圧縮専用? (スコア:2)
>あらかじめ分布を知っていないといけないの?
線形とみなせる測定対象なら固有振動モードが有限な数しかないだろう。それはＦＦＴしたい測定対象の大多数だと思うけど。
Re: (スコア:0)
そこはスラドのタレコミにつっこむんじゃなくて。
論文取り寄せて読んだら解決かと。
FEMとかBEMとか (スコア:0)
スパースなのでMPEGとかJPEG、もしくはその延長線にはあんまりインパクトない気はしますが
(私が不勉強であるかもしれないが)
有限要素法とか境界要素法に使えるみたいですね(スパース行列の典型ですし)。
本質的に線形偏微分方程式の数値解法なんだから、新たな計算法の開発も
できるかもしれない。
すごいよ すごい (スコア:0)
そう思っていた時期もありました
もしかして (スコア:0)
JPEG2000の時代来た？
Re:もしかして (スコア:2)
JPEG XR [wikipedia.org]とかいうフォーマットがあるそうで…
VOCALOIDみたいな音声合成系 (スコア:0)
CAD (スコア:0)
を動かすマシンの性能を1段低いもので良くなるのですね。
理論の方でしっくり収まらないんじゃないか？ (スコア:0)
フーリエ変換は、直交変換の一種である。
直交変換は、線形変換の一種である。
なんてことを考え出すと、どう考えていいものやら。
計算手順は示せるけど、定式化した上であれこれ
考えるのは難しい種類の話かも。
Re:理論の方でしっくり収まらないんじゃないか？ (スコア:1)
スパースってことは、次元の低い部分空間で片付くってことさ。
the.ACount