高速フーリエ変換の新アルゴリズムをMITが開発　従来の１０倍の速度で携帯動画もHD化か

The faster-than-fast Fourier transform
For a large range of practically useful cases, MIT researchers find a way to increase the speed of one of the most important algorithms in the information sciences.
CAMBRIDGE, Mass. ? The Fourier transform is one of the most fundamental concepts in the information sciences. It’s a method for representing an irregular signal
? such as the voltage fluctuations in the wire that connects an MP3 player to a loudspeaker ? as a combination of pure frequencies. It’s universal in signal processing,
but it can also be used to compress image and audio files, solve differential equations and price stock options, among other things.

The reason the Fourier transform is so prevalent is an algorithm called the fast Fourier transform (FFT), devised in the mid-1960s, which made it practical to calculate
Fourier transforms on the fly. Ever since the FFT was proposed, however, people have wondered whether an even faster algorithm could be found.


http://web.mit.edu/press/2012/faster-fourier-transforms.html

日本語でおｋ

今更かよMITは

超高速フーリエ変換か
ffftだなftthみたいだ

マジかよ！それめちゃくちゃ凄くね。

↓日本語

フーリエ変換を10倍速くする新アルゴリズムをMITの研究者たちが開発?携帯でHDビデオも可能?

200年の歴史を持つ数学公式が改良されるなんて、めったにあることではない。フーリエ変換は最初、1811年にジョゼフ・フーリエというフランス人が提唱したが、
しかしその真価が認められたのは20世紀の半ばになってからだ。彼のテクニックは複雑な信号を複数の成分信号に分解してそのそれぞれを別々に送信ないし処理し、
それらを合成して元の信号を無傷で作り出せる、というものだ。

1965に、フーリエ変換が急にもてはやされる事件が起きた。それはJames CooleyとJohnが、この変換をコンピュータを使ってリアルタイムで行うやり方を発見したことだ。
そして今年、2012年には、また新たな重要な改良が提唱された。

http://jp.techcrunch.com/archives/20120118improvement-on-age-old-mathematical-principle-could-yield-improved-images-video/

我々の母校なだけはあるな

>>1
ふむそういうことか

フーリエ変換を理解するのは、難しくはない。たとえば、音楽を送信したくても、個々の楽器や個々の周波数成分を別々に送ることはできない。そこで、すべての周波数成分を積み重ねて
一つの信号にする。それは個々の周波数成分よりも複雑な形をしているが、受信側ではそれを解釈できる。複雑な信号をその成分周波数に分解する処理を、フーリエの方法を使って行い、
それらの成分周波数から元の信号を合成する処理はフーリエ逆変換で行う。こうやってエンコード/デコードできるのは音声だけではなく、たとえば画素（ピクセル）が色などをビットの値で
表している信号だと考えると、画像やビデオもこの方法で表現できる。というわけで、今やフーリエ変換/逆変換は至るところで使われている。

しかし、歴史が古く、広範に使われているこの方法も、アルゴリズムには改良の余地がある、とMITの研究者たちは考えた。1965年に確立した、デジタルの、つまり“離散的な”フーリエ変換は、
効率がそれほど良くない。そして研究者たちは、8×8(==64)の数値ブロックのうち、57は無視できる、無視しても画像の質に悪影響は現れないことを見つけた。

ただしそれは、単純に要らないものを捨てるという話ではなく、その新しいテクニックは元の信号を複数の小さな信号に分解する方法を変えることによって、重要な信号とそうでない信号
を容易に選り分けられるようにしている。そして信号を構成するビット数を削減して、必要な部分だけ残すのだ。

なんだよ・・要らない信号を捨てて速くするってこと？
それ意味ないじゃない。
無線ＬＡＮとかの信号ってノイズだぜ？見た目。
要る要らないの判別なんてできないし。

こんな話がなぜ、TechCrunchに載るのか？　それは、FaceTimeやSpotifyを支えているのも、このような研究だからだ。それは、多くのスタートアップの誕生も、支えている。このような、
信号処理のもっとも基本的な部分の改良は、数年後ないし数十年後に実用のレベルに大きな影響が現れる。まだこの改良アルゴリズムは無名だが、信号の圧縮と送信の速度をこれまでの
10倍は速くするという。携帯電話で、4K(==4000×2000)のビデオを撮れる/送れるようになるかな？　また、オーディオやビデオの高速で高品質なストリーミングを、狭い帯域でできるように
なるかもしれない。それとも、Wi-Fi上で高速なビッグデータ処理ができる？　今はまだ何とも言えないけど、ファンダメンタルの改良が実用レベルに影響を及ぼさないことは、ふつうありえないからね。

研究論文を書いたのは、MITコンピュータ科学人工知能研究所(MIT CSAIL)のDina KatabiとPiotr Indyk、そして彼らの学生のEric PrinceとHaitham Hassaniehだ。まだ一般公開はされていないが、
ここで読むことができる。

http://arxiv.org/abs/1201.2501v1

FFタクティクススレ

>>11のリンク先の内容

Nearly Optimal Sparse Fourier Transform

Haitham Hassanieh, Piotr Indyk, Dina Katabi, Eric Price

We consider the problem of computing the k-sparse approximation to the discrete Fourier transform of an n-dimensional signal. We show:
* An O(k log n)-time algorithm for the case where the input signal has at most k non-zero Fourier coefficients, and
* An O(k log n log(n/k))-time algorithm for general input signals.
Both algorithms achieve o(n log n) time, and thus improve over the Fast Fourier Transform, for any k = o(n). Further, they are the first known algorithms that satisfy this property.
Also, if one assumes that the Fast Fourier Transform is optimal, the algorithm for the exactly k-sparse case is optimal for any k = n^{\Omega(1)} . We complement our algorithmic
results by showing that any algorithm for computing the sparse Fourier transform of a general signal must use at least \Omega(k log(n/k)/ log log n) signal samples, even
if it is allowed to perform adaptive sampling.

↓新アルゴリズムの論文（PDF）
http://arxiv.org/PS_cache/arxiv/pdf/1201/1201.2501v1.pdf

今後ソフトウェアだけで効率超良くなるの？
凄くね
お前も使うなら金出せよとか言われるのかな

>>9
FFTの高速化じゃなくてただの近似計算じゃん

日本語でおk

FFFTってか

うん、論文の一番最初にニアリーってあるね。
ええ・・使えるのこれ。

でも冷静に考えると10バイトってショボいな。コンピュータの世界では。

これは低周波と高周波をカットってこととちがうの

不可逆な情報の切り捨てと引換に高速化するという話なのか
動的に分解能を変化させることで情報を損なわずに計算量を最適化するという話なのか
それとも別の話なのか
日本語の解説記事を読んだだけでははっきりしないので
arXivのプレプリントを読んでみる

文系脳の馬鹿な俺でも分かるように説明してください＞＜

スーパーファストフーリエとらんすふぁー

動画コーデックの進化ってすごいよな
TVも放送波で自動アップデートできるようにすべき

すっげーな
この分野って既に研究しつくされてたように思ってたけど違うのか

ffftpか

フーリエ変換ってこんな所で使われてたのか

ﾏｻﾁｭｰﾁｪｯﾁｭ

不可逆かよ

家畜に神はいないっ！

これは凄いな

よくわからないけどケツ毛の一本一本まで鮮明に携帯で見れるようになるの？すごいな

なんだよ、これでも日本語かよっ！！ぜんっぜんわかんねーぞ！！

>>18
"Nearly Optimal Sparse Fourier Transform"なんだから
ニアリーは「オプティマル」の部分にかかってるんじゃないの？

「この問題を解くアルゴリズムの時間計算量は，少なくともこれより大きい」という
計算量の下界を示した上で
今回提案する新アルゴリズムの計算量がかなりいい線いってるから
ほぼ最適なアルゴリズムなんだよ，という感じで

黒糖フークレエかと思った

パラパラ漫画と同じで、錯覚を利用してるんだろ
機械はごまかせないが人間はごまかせる

計算が軽くなるのと、帯域って別じゃね？

すげーな

>>34
たぶん近似的な最適 Sparse？ フーリエ変換とかって訳になる思う。
中身読まないと分からないけど、近似するって点は変わらないんだと
思うよ。

アグリアスがどうのこうの

をおすげえ！！！

フーリエ変換とは別物というか、選別してるんかな

略称はTFTFFT？

MITなつかしいなー
学食のマサチュー丼の旨さは異常

(はやくしろ)

フーリエ級数は高校の時に音声認識ソフト作るときに使ったくらいだったけどいろんな事に使われてるんだな

>>39
＞近似するって点はかわらない

そうみたい
信号 X をフーリエ変換した N 次元周波数ベクトルを Vx
N 個の成分のうちゼロでないものが k 個しかないベクトルで
Vx をもっともよく近似するものを Vy として

Vyと同じく非ゼロ要素が k 個しかないベクトルで
近似度合いが Vy （最適近似）と比較して
定数 C 倍以内におさまるようなベクトル Vx' を計算するアルゴリズム

ということみたいだ
フーリエ変換のことは全然知らなかったけど
この k-sparse なアルゴリズムだけで応用分野がずらずら書いてある

>>47
ああ〜・・似たようなものは合わせちゃうってことかな。
なるほど。。映像の場合どうなるだろうか。ちょっと考えないと。

そうかフーリエ変換して逆変換しても禿は治らないのか

要するに重み付きフーリエ変換ということで宜しいか

これって、一種のデータ改竄だよね。

信号処理屋の俺が帰宅したら詳しく解説してやんよ。
それにしてもMITなつかしなあ。相撲部の後輩達は元気でやってっかなあ。

　　　　　　　 lヽ ﾉ l　　　　　　　　ｌ l　ｌ ヽ　　 ヽ
　 )'ｰーノ(　 |　|　 | ､　　　　　 / l｜ ｌ　ハヽ　　|ｰ‐''"ｌ
　/　Ｆ　　|　|　|／| ﾊ　　/ / ,/ /|ﾉ /l /　ｌ l ｌ|　ｌ　 Ｆ ヽ
　l 　 ･　　i´ |　ヽ､| |ｒ|| |　//--‐'" 　 ｀'メ､_ｌﾉ| /　 ・　 /
　|　 Ｆ　　l　 トー-トヽ| |ノ　''"´｀　　　ｒｰ-/// |　 Ｆ　｜
　|　 ･　　 |／　　 　 | l ||､　''"""　 j　""''/ | |ヽｌ 　・　｜
　|　 Ｔ 　 |　　 　 　 | l |　ヽ,　 　― 　 ／　| |　ｌ　 Ｔ　 |
　| 　 !!　 |　　 　 /　| | |　　 ` ｰ-‐ ' ´||　,ﾉ| |　|　　!!　｜
ノｰ‐---､,|　 　 /　│ｌ､l　　　　　　 　 |ﾚ' ,ﾉﾉ　ﾉハ､_ノヽ
　/ 　　 　 　 ／　ノ⌒ヾ､　 ヽ　　　 ノハ,　　　 　 |
,/ 　 　　　,イーｆ'´ /´　　＼　| ,／´ ｜ヽl　　　 　 |
　　　　 ／-ト、|　┼―- ､_ヽﾒr'　, -=ｌ''"ハ　　　　|　 ｌ
　　 ,／　 　|　ヽ 　＼　　_,ノｰｆ' ´　　ﾉノ　 ヽ　 　｜　|
､_　　　 _ ‐''ｌ　　`ー‐―''" ⌒'ｰ--‐'´｀ヽ､_ 　　_,ノ　ノ

努力はしている!

お前ら画像すら圧縮されてデータ切り捨てられてることも知らんのか
一生bmpで保存してろよ低脳

>>51
いや違うだろ
要求誤差に収まる近似法

俺たちの後輩頑張ってるな

フーリエ変換そのものを効率化したわけじゃないのね、ちょっと残念

アニメをエンコする時　ffmpeg + x264　を使ってるけど
30分につき3.68GBのTSファイルが250MBまで小さくなる
普通エンコには1200秒ほどかかるけど、このアルゴリズムがx264で採用されれば120秒でエンコが終わるのか

>>55
可逆の画像圧縮って流行らないの？

中学生しかいないのか
旧速でアフィられてろよ

フーリエ変換とモンロー効果のコトバの響きのかっこよさは異常

FFTってネーミングかっこいい
いまいちよくわからんけど

ラプラスはラプラス変換を何に使ってたの？

さすが我が母校、実に応援のしがいがある。

FFTスレ
アグリアスかわいいよアグリアス
シドからいつもエクスカリバー取り上げてアグリアスに装備させてたっけなあ

命！

これでCTよりMRIの勢力拡大するかな？

近似の定数Cの評価は４章の冒頭と定理4.9にある
k-sparseなフーリエ変換がどこで使えるかについては
１章イントロにいろんな分野がずらーっと書いてある

多倍長乗算の時に速いらしいけど難しそうなので筆算で済ませてる

>>60
デジタルにした時点で標本化と量子化がなされてるだろ
そこからは圧縮しないって意味かも知れんが

隠れマルコフモデルでつまづいてしまった

高速フーリエ変換より高速ってもうなにがなんだか

名前どうなんだろ
AFFTとかかね？

>>71
同じことロスレス厨に言ってこい

これ結局離散フーリエ変換自体はFFTでやるの？
FFTした後で、周波数空間内の似てるベクトルで近似するの？
デジタル信号処理は習ったけどサッパリ

どうせマルチコアにオプティマイズしたとかそのレベルだろ

>>59
エンコードのうちフーリエ変換が関わる部分はどれだけかって事ぐらい考えろよw
一番時間かかるのは動き検出だろうが畜生

グラフィックイコライザと脳波の分析ぐらいしか知らん

>>71
win標準のペイントツールで、白い画像に一本線を描いただけの画像とか
そんな難しいことしてんの。

条件付きじゃん。まぁこれなら可能っぽいかな

>>60
可逆だと圧縮率が上がらない

地デジに応用すれば
チャンネルの切替とか早くなるの？

>>60
加工用には充分使われてるだろ

>>80
ペイントツールで太い直線を斜めに描いたうえで
キャンパスをどんどん拡大表示していくと
真っ直ぐな直線だと思っていた境界部分が
四角いドットの階段になるよね
>>71が言ってるのはそういうことなんじゃないかな？

たとえば銀塩写真を電子化したら，スキャナで取り込んでデジタル化した時点で量子化される
みたいな

>それらを合成して元の信号を無傷で作り出せる、
無傷では無いんじゃないのか

高速スーフリ変換に見えた

さすがマチャチューチェッチュ工科大学

理屈がさっぱりわからんで理系行ったことを後悔した

>>60
gifやpngがあるじゃん
動画は可逆だと圧縮率が低すぎるし、一瞬だから可逆である必要がない

結局非可逆変換だろ
この記事を書いた記者は本質を理解してない

近似かよ

重複だけど誘導していいのだろうか？