読者です 読者をやめる 読者になる 読者になる

亀岡的プログラマ日記

京都のベッドタウン、亀岡よりだらだらとお送りいたします。

おお、TechCrunchにNOSFTがのってる。でもよくわかんねぇよコレ。

ちょっと今日はへろへろなので軽い話題でも。

先週末くらいに、フーリエ変換を高速化するアルゴリズムについて紹介しました。

NOSFT=近似最適スパースフーリエ変換、とでも訳すべきなんでしょうかね。TechCrunch記事にはこうあります。

しかし、歴史が古く、広範に使われているこの方法も、アルゴリズムには改良の余地がある、とMITの研究者たちは考えた。1965年に確立した、デジタルの、つまり“離散的な”フーリエ変換は、効率がそれほど良くない。そして研究者たちは、8×8(==64)の数値ブロックのうち、57は無視できる、無視しても画像の質に悪影響は現れないことを見つけた。 ただしそれは、単純に要らないものを捨てるという話ではなく、その新しいテクニックは元の信号を複数の小さな信号に分解する方法を変えることによって、重要な信号とそうでない信号を容易に選り分けられるようにしている。そして信号を構成するビット数を削減して、必要な部分だけ残すのだ。

どうも的を得ないですよね。無視出きる、ってなによ。元来的な意味は実はこうです。

x0 の N 個の成分のうち 0 でない値をとるものは高々 K 個である,ということが分かっているものとする.このとき,「ベクトル x0 は K -スパースてである」と呼ぶことにする.

ここでは圧縮センシングの数理、となっていますので、センサ信号列のようなほとんど経時変化がなく異常時だけ反応するような信号列に対して言っているのかなぁ、という感じがします。上記引用PDFの内容もKスパースであることが既知の信号から、実際にどの成分がスパースなのかを推定する方法について書かれています。

ではフーリエ変換におけるスパースってなんなんでしょうか?

論文の中をちょろっとだけ覗いてみましょう。

At a high level, sparse Fourier algorithms work by binning the Fourier coefficients into a small number of bins. Since the signal is sparse in the frequency domain, each bin is likely to have only one large coefficient, which can then be located (to find its position) and estimated (to find its value).

周波数領域でスパースだから、小さい周波数帯域毎に瓶を分けてやったら、各領域には1つの大きなフーリエ係数しか残らないんじゃね?っていうのが基本概念っぽいですね。つまり、信号が周波数領域で十分に(時間分解能に対して?)離散的だったばあいですね。

うーん、これTechCrunchの中の人概念取り違えてませんか?つまりディジタルという意味で"離散的"であるのと、ディジタルに取った時の標本化周波数(に比例する周波数分解能)に対して、さらに”離散的”であること。この2つがごっちゃになっているから記事が何言っているのかわかんない気がします。

えっとそれから、この部分がいかにもこのアルゴリズムの先進的なことろのような書き方をしてますが、この周波数瓶を使う方法は、

We start with an overview of the techniques used in prior works.

とあるように本質的ではないはずです。ざっと読んだだけなの詳しくはわかりませんが、この論文で”New Technic”とされているのは次の二点です。

  • Location & Estimation
    • 位置推定が高速。本当にk-スパースなケース(近似しないケース)では、二点のサンプル点の情報のみからどの点が値を持っているのかを計算できる。一般的な場合はK-スパースな近似を行うが、従来のように1ビットずつ復元するのではなく、O(log log n)オーダーのbitをもつブロック単位で復元する。
  • updating the signal
    • ここはよく理解できていませんが、信号から確定したフーリエ係数のみを減算する際に、信号全体から減算していた高コストな方法から、瓶ごとに減算する低コストな方法に変えた、というところですね。信号処理に詳しい人読んで教えてください。。。

だから結局、周波数分解能に対して実際の周波数の分布が疎らになる場合に有効っぽいですね。てっきり時間的な話かと勘違いしていました。アルゴリズムのオーバービューまではかなりわかりやすい英語に感じたので、頑張れる人は頑張ってみては?