Deterministic Sparse Fourier Approximation via Fooling Arithmetic Progressions

Abstract

A significant Fourier transform (SFT) algorithm, given a threshold $\tau$ and oracle access to a function f, outputs (the frequencies and approximate values of) all the $\tau$-significant Fourier coefficients of f, i.e., the Fourier coefficients whose magnitude exceeds $\tau \|f\|_2^2$. In this paper we present the first deterministic SFT algorithm for functions f over ZN which is: (1) Local, i.e., its running time is polynomial in log N, 1/$\tau$ and $L_1(\hat{f})$ (the L1 norm of f's Fourier transform). (2) Robust to random noise. This strictly extends the class of compressible/Fourier sparse functions over ZN efficiently handled by prior deterministic algorithms. As a corollary we obtain deterministic and robust algorithms for sparse Fourier approximation, compressed sensing and sketching. As a central tool, we prove that there are: 1. Explicit sets A of size poly((ln N)d, 1/$\varepsilon$) with $\varepsilon$-discrepancy in all rank d Bohr sets in ZN. This extends the Razborov-Szemeredi-Wigderson result on $\varepsilon$-discrepancy in arithmetic progressions to Bohr sets, which are their higher rank analogue. 2. Explicit sets AP of size poly(ln N, 1/$\varepsilon$) that $\varepsilon$-approximate the uniform distribution over a given arithmetic progression P in ZN, in the sense that |E$x \in A$\chi$(x) -E$x \in P$\chi$(x)| < $\varepsilon$ for all linear tests $\chi$ in ZN. This extends results on small biased sets, which are sets approximating the uniform distribution over the entire domain, to sets approximating uniform distributions over (arbitrary size) arithmetic progressions. These results may be of independent interest.