Deterministic Sparse Fourier Approximation Via Approximating Arithmetic Progressions
Deterministic Sparse Fourier Approximation Via Approximating Arithmetic Progressions
复制标题
通过近似算术级数进行确定性稀疏傅立叶逼近
DOI：
--
复制
发表时间：
2014
影响因子：
2.5
通讯作者：
Adi Akavia
中科院分区：
文献类型：
--
作者：
Adi Akavia
本文提出了一种确定性算法，用于计算给定信号f ∈ CN的有效傅里叶频率<sup></sup>及其近似傅里叶系数，其运行时间和样本复杂度多项式为logN，<sub>L1</sub>（f ∈ N）/||f||<sub>2</sub>和1/τ，其中有效频率是占据信号能量的至少τ分数的频率，并且<sub>L1</sub>（f ω）表示<sub></sub>f的傅里叶变换的L1范数。此外，该算法对加性随机噪声具有鲁棒性。这严格地扩展了可压缩/傅立叶稀疏信号的类，有效地处理了以前的确定性算法中的信号在C<sup>N</sup>。作为一个中心工具，我们证明了存在一个确定性算法，该算法将N，ε和Z N中的算术级数P作为输入<sub></sub>，在ln N和1/ε中的时间多项式中运行，并返回一个集合<sub>AP</sub>，在Z N中ε-逼近P<sub>，</sub>在这个意义上，|E <sub>x∈A</sub><sub></sub> Pe <sup>2πiω/N</sup>- E <sub>x∈</sub> Pe <sup>2πiωx/N</sup>| <; ε对于所有ω = 0，...，N-1换句话说，我们证明了存在lnN中的大小多项式的集合AP和1/ε的显式构造，其ε-逼近给定的Z<sub>N</sub>中的算术级数P。<sub></sub>这扩展结果的小偏差集，这是一套近似整个域，以套近似一个给定的算术级数，这个结果可能是独立的利益。
We present a deterministic algorithm for finding the significant Fourier frequencies of a given signal f ∈ C<sup>N</sup> and their approximate Fourier coefficients in running time and sample complexity polynomial in log N, L<sub>1</sub>(f̂)/||f̂||<sub>2</sub>, and 1/τ, where the significant frequencies are those occupying at least a τ-fraction of the energy of the signal, and L<sub>1</sub>(f̂) denotes the L<sub>1</sub>-norm of the Fourier transform of f. Furthermore, the algorithm is robust to additive random noise. This strictly extends the class of compressible/Fourier sparse signals efficiently handled by previous deterministic algorithms for signals in C<sup>N</sup>. As a central tool, we prove there is a deterministic algorithm that takes as input N, ε and an arithmetic progression P in Z<sub>N</sub>, runs in time polynomial in ln N and 1/ε, and returns a set A<sub>P</sub> that ε-approximates P in Z<sub>N</sub> in the sense that |E<sub>x∈A</sub><sub>P</sub>e<sup>2πiω/N</sup> - E<sub>x∈P</sub>e<sup>2πiωx/N</sup>| <; ε for all ω = 0,..., N-1. In other words, we show there is an explicit construction of sets A<sub>P</sub> of size polynomial in lnN and 1/ε that ε-approximate given arithmetic progressions P in Z<sub>N</sub>. This extends results on small-bias sets, which are sets approximating the entire domain, to sets approximating a given arithmetic progression; this result may be of independent interest.