Deterministic Sparse Fourier Approximation Via Approximating Arithmetic Progressions

作者：Akavia Adi^*

来源：IEEE Transactions on Information Theory, 2014, 60(3): 1733-1741.

DOI：10.1109/TIT.2013.2290027

• Algorithm design and analysis
• combinatorial mathematics
• computational efficiency
• discrete Fourier transforms
• fast Fourier transforms
• noise
• signal processing algorithms
• signal reconstruction
• signal sampling

We present a deterministic algorithm for finding the significant Fourier frequencies of a given signal f is an element of C-N and their approximate Fourier coefficients in running time and sample complexity polynomial in log N, L-1((f) over cap)/parallel to(f) over cap parallel to(2), and 1/tau, where the significant frequencies are those occupying at least a tau-fraction of the energy of the signal, and L-1((f) over cap) denotes the L-1-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-N. As a central tool, we prove there is a deterministic algorithm that takes as input N, e and an arithmetic progression P in Z(N), runs in time polynomial in ln N and 1/epsilon, and returns a set A(P) that epsilon-approximates P in Z(N) in the sense that vertical bar Ex is an element of A(P) e(2 pi i omega x/N) - Ex is an element of Pe(2 pi i omega x/N)vertical bar < epsilon for all omega = 0, ... , N - 1. In other words, we show there is an explicit construction of sets A(P) of size polynomial in ln N and 1/epsilon that epsilon-approximate given arithmetic progressions P in Z(N). 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.

• 出版日期2014-3