Learning Significant Fourier Coefficients over Finite Abelian Groups
Learning Significant Fourier Coefficients over Finite Abelian Groups
复制标题
学习有限阿贝尔群上的显着傅立叶系数
DOI：
--
复制
发表时间：
2008
期刊：
影响因子：
--
通讯作者：
Adi Akavia
中科院分区：
文献类型：
--
作者：
Adi Akavia
傅立叶变换是计算机科学中使用最广泛的工具之一。计算长度为N的信号的傅里叶变换可以使用快速傅里叶变换（FFT）算法在时间Θ（Nlog N）中完成。这个时间界限显然不能被改进到低于Θ（N），因为输出本身的长度是N。尽管如此，事实证明，在许多应用中，仅找到有效的傅立叶系数就足够了，即，傅立叶系数占据，比方说，至少1%的信号的能量。这激发了本条目中讨论的问题：有效地找到和近似给定信号的重要傅立叶系数（简称SFT）的问题。SFT的一个简单的解决方案是首先计算给定信号的整个傅立叶变换，然后只输出重要的傅立叶系数;因此，与计算整个傅立叶变换的算法相比，不会产生复杂性改进。相比之下，SFT可以在运行时间内更有效地求解，同时阅读N个信号条目中的最多θ（log N）[2]。SFT的这种快速算法为来自不同领域的应用开辟了道路，包括计算学习，纠错码，密码学和算法。现在我们正式定义SFT问题，将注意力限制在离散信号上。我们使用函数记法，其中信号是有限交换群G上的函数f：G → C，其能量为|G| ∑ x∈G f（x）2，其最大振幅为<$f <$∞ def = max {|f（x）||x ∈ G}。1为了便于说明，我们不失一般性地假定G = ZN 1 × ZN 2 ×。. .× ZNk，对于N1，. . .，Nk ∈ Z+（即，正整数），并且ZN是整数模N的加法群。f的傅里叶变换是函数f ∈：G → C，定义为每个α =（α1，. . .，αk）∈ G，
Fourier transform is among the most widely used tools in computer science. Computing the Fourier transform of a signal of length N may be done in time Θ(N log N) using the Fast Fourier Transform (FFT) algorithm. This time bound clearly cannot be improved below Θ(N), because the output itself is of length N . Nonetheless, it turns out that in many applications it suffices to find only the significant Fourier coefficients, i.e., Fourier coefficients occupying, say, at least 1% of the energy of the signal. This motivates the problem discussed in this entry: the problem of efficiently finding and approximating the significant Fourier coefficients of a given signal (SFT, in short). A naive solution for SFT is to first compute the entire Fourier transform of the given signal and then to output only the significant Fourier coefficients; thus yielding no complexity improvement over algorithms computing the entire Fourier transform. In contrast, SFT can be solved far more efficiently in running time Θ̃(log N) and while reading at most Θ̃(log N) out of the N signal’s entries [2]. This fast algorithm for SFT opens the way to applications taken from diverse areas including computational learning, error correcting codes, cryptography and algorithms. We now formally define the SFT problem, restricting our attention to discrete signals. We use functional notation where a signal is a function f : G → C over a finite abelian group G, its energy is ‖f‖2 def = 1 |G| ∑ x∈G f(x) 2, and its maximal amplitude is ‖f‖∞ def = max {|f(x)| |x ∈ G}.1 For ease of presentation we assume without loss of generality that G = ZN1 × ZN2 × . . .× ZNk for N1, . . . , Nk ∈ Z+ (i.e., positive integers), and ZN is the additive group of integers modulo N . The Fourier transform of f is the function f̂ : G → C defined for each α = (α1, . . . , αk) ∈ G by