亀岡的プログラマ日記

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

とりあえずNOSFTのアブストだけ訳しておく。

NOSFT = Nearly Optimal Sparse Fourier Transform

Twitterで急に飛んできたので。FFTに変わるものなのかとか全然分からずに、とりあえずメモ的に。

原文

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.

適当訳

我々は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)個のサンプル信号を用いる必要があることを示し、提案アルゴリズムの成果をしめす。

もにょもにょ

信号処理屋さんじゃないので、本文の解読はかなり無理ゲーですた。とりあえず最初k-sparseという話がわからなくてごそごそしてたらこんなんみつけました。

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

スパースってのは”疎”ってことで、つまり高々k個の非ゼロ成分を持つ信号をk-スパースな信号というわけ。同じようにkスパースな近似というのは、高々k個しか非ゼロ成分を持たないような形に信号を近似する、ということなんだろうな。。。

あとΩ関数がわからなかったんですけど、これもOと同じくランダウの記号なんですね!!!

ここではランダウの記号として知られるいくつかの異なる記法を記す。 Ω(n) → 漸近的に下に有界

Oは上に有界(計算量は高々〜)なのに対し、Ωは下に有界(計算量は少なくとも・・・)という表し方をするんですね・・・

しかしkスパースを仮定して良いような信号ってそんなにあるんだろうか。。。かなり疎な信号ってことになりそうですよね。ふうむ。。。

追記

関係有るの・・・かな・・・?