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

次の記事

速報:ラリー・ペイジ、Google+ユーザーが9000万人突破と発表―60%が毎日利用

fou

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

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

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

しかし、歴史が古く、広範に使われているこの方法も、アルゴリズムには改良の余地がある、と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だ。まだ一般公開はされていないが、ここで読むことができる。

[原文へ]
[jpTechCrunch最新記事サムネイル集]
[米TechCrunch最新記事サムネイル集]
(翻訳:iwatani(a.k.a. hiwa))

“フーリエ変換を10倍速くする新アルゴリズムをMITの研究者たちが開発–携帯でHDビデオも可能?” への7件のフィードバック

  1. Inetgate より:

    このアルゴリズム、1960年代に出てきた高速フーリエ変換(FFT)の改良とのことですが、信号処理としてみた場合、DCTやDST等の変換方法と比較してどの程度速いのだろうかと。

  2. AnonymousCoward より:

    >* 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) http://arxiv.org/abs/1201.2501v1 
    え、結局O(N*logN)のアルゴリズムじゃん。しかも、approximalだし。
    つーか、画像や動画送りたいだけなら、最初からO(N)で計算できるDWTベースの圧縮コーデック使えば良いんじゃん?JPEG2000とかOggとか。見た目と圧縮比(&計算量)のバランス取るだけだったら、「DFTの近似計算を高速にやります」のどこに注目する要素があるの分からんね。

    DFTを(近似計算でも)高速化することから発展が見込める分野があるとすれば、Facetime(笑)やSpotify(笑)じゃなくて、Siriのような音声認識だったり、Google Similar Imagesのような画像認識系のサービスだろう。(まだ周波数領域での処理は外せないだろうし)

    技術常識を加味すればこういう推論になるはずなんだが、

    それは、多くのスタートアップの誕生も、支えている。 
    >携帯電話で、4K(==4000×2000)のビデオを撮れる/送れるようになるかな?

    とか、イミフすぎる。なんか「MITだからスゴーイ」的なステマ記事なんかね。

    • K. Xagawa より:

      ちょっと論点を読み間違えていると思います。

      彼らの論文は全体の計算量が k = o(N)のときには、Θ(N)を下回るので、かなりの高速化が出来たという話です。
      たとえばk = √Nのときには k lg N ≦ N が N≧4 で成立します。

    • AnonymousCoward より:

      DWT と k-sparse を理解していないコメントだな…

  3. AnonymousCoward より:

    >* 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) http://arxiv.org/abs/1201.2501v1 
    え、結局O(N*logN)のアルゴリズムじゃん。しかも、approximalだし。
    つーか、画像や動画送りたいだけなら、最初からO(N)で計算できるDWTベースの圧縮コーデック使えば良いんじゃん?JPEG2000とかOggとか。見た目と圧縮比(&計算量)のバランス取るだけだったら、「DFTの近似計算を高速にやります」のどこに注目する要素があるの分からんね。

    DFTを(近似計算でも)高速化することから発展が見込める分野があるとすれば、Facetime(笑)やSpotify(笑)じゃなくて、Siriのような音声認識だったり、Google Similar Imagesのような画像認識系のサービスだろう。(まだ周波数領域での処理は外せないだろうし)

    技術常識を加味すればこういう推論になるはずなんだが、

    それは、多くのスタートアップの誕生も、支えている。 
    >携帯電話で、4K(==4000×2000)のビデオを撮れる/送れるようになるかな?

    とか、イミフすぎる。なんか「MITだからスゴーイ」的なステマ記事なんかね。

  4. Nobody より:

    翻訳からはFFT開発者のチューキーの名前が落ちてるよ。

コメントを残す

以下に詳細を記入するか、アイコンをクリックしてログインしてください。

WordPress.com ロゴ

WordPress.com アカウントを使ってコメントしています。 ログアウト / 変更 )

Twitter 画像

Twitter アカウントを使ってコメントしています。 ログアウト / 変更 )

Facebook の写真

Facebook アカウントを使ってコメントしています。 ログアウト / 変更 )

Google+ フォト

Google+ アカウントを使ってコメントしています。 ログアウト / 変更 )

%s と連携中

フォロー

新しい投稿をメールで受信しましょう。

現在396人フォロワーがいます。