Deterministic Sparse Fourier Transform with an ell_infty Guarantee

In this paper we revisit the deterministic version of the Sparse Fourier Transform problem, which asks to read only a few entries of $x \in $\mathbb{C}$^n$ and design a recovery algorithm such that the output of the algorithm approximates $\widehat{x}$, the Discrete Fourier Transform (DFT) of $x$. The randomized case has been well-understood, while the main work in the deterministic case is that of Merhi et al.@ (J Fourier Anal Appl 2018), which obtains $O(k^2{\log }^{-1}k\cdot {\log }^{5.5}n)$ samples and a similar runtime with the ${\mathrm{\ell }}_2\mathrm{/}{\mathrm{\ell }}_1$ guarantee. We focus on the stronger ${\mathrm{\ell }}_{\mathrm{\infty }}\mathrm{/}{\mathrm{\ell }}_1$ guarantee and the closely related problem of incoherent matrices. We list our contributions as follows.

1. We find a deterministic collection of $O(k^2\log n)$ samples for the ${\mathrm{\ell }}_{\mathrm{\infty }}\mathrm{/}{\mathrm{\ell }}_1$ recovery in time $O(nk{\log }^{2}n)$, and a deterministic collection of $O(k^2{\log }^{2}n)$ samples for the ${\mathrm{\ell }}_{\mathrm{\infty }}\mathrm{/}{\mathrm{\ell }}_1$ sparse recovery in time $O(k^2{\log }^{3}n)$.
2. We give new deterministic constructions of incoherent matrices that are row-sampled submatrices of the DFT matrix, via a derandomization of Bernstein’s inequality and bounds on exponential sums considered in analytic number theory. Our first construction matches a previous randomized construction of Nelson, Nguyen and Woodruff (RANDOM’12), where there was no constraint on the form of the incoherent matrix. Our algorithms are nearly sample-optimal, since a lower bound of $\Omega(k^2

• k \log n)$ is known, even for the case where the sensing matrix can be arbitrarily designed. A similar lower bound of $\mathrm{\Omega }(k^2\log n\mathrm{/}\log k)$ is known for incoherent matrices.