Deterministic Sparse Fourier Approximation Via Approximating Arithmetic Progressions

We present a deterministic algorithm for finding the significant Fourier frequencies of a given signal f ∈ C^N and their approximate Fourier coefficients in running time and sample complexity polynomial in log N, L₁(f̂)/||f̂||₂, and 1/τ, where the significant frequencies are those occupying at least a τ-fraction of the energy of the signal, and L₁(f̂) denotes the L₁-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, ε and an arithmetic progression P in Z_N, runs in time polynomial in ln N and 1/ε, and returns a set A_P that ε-approximates P in Z_N in the sense that |E_x∈APe^2πiω/N - E_x∈Pe^2πiωx/N| <; ε for all ω = 0,..., N-1. In other words, we show there is an explicit construction of sets A_P of size polynomial in lnN and 1/ε that ε-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.