Combinatorial sublinear-time Fourier algorithms (Q972615)

Let \(f\) be a sufficiently smooth \(2\pi\)-periodic function which is well approximated by a \(k\)-sparse trigonometric polynomial \[ {\tilde f}(x) = \sum_{j=1}^k c_j\, \exp ({\mathrm i}\, \omega_j\, x) \] with integer frequencies \(\omega_j \in [-N/2,\, N/2]\) and complex coefficients \(c_j \neq 0\), where the smallest possible \(N\) is much larger than \(k\). The aim is the efficient recovery of all parameters \(\omega_j\), \(c_j\) \((j=1,\ldots, k)\) using as few sampled values of \(f\) as possible. Compressed sensing methods provide a robust framework for reducing the number of samples. In this interesting paper, the author presents a novel fast algorithm of deterministic parameter recovery. The main result is a Fourier algorithm which has runtime \({\mathcal O}(k^2\,(\log N)^4)\) and requires \({\mathcal O}(k^2\, (\log N)^3)\) sampled values of \(f\). This new Fourier algorithm is based on several discrete Fourier transforms of small lengths and uses number theoretic group testing methods and the Chinese Remainder Theorem. A simple relaxation of this deterministic method provides a new randomized Fourier algorithm which has sublinear runtime \({\mathcal O}(k\,(\log N)^5)\) and requires \({\mathcal O}(k\, (\log N)^4)\) sampled values of \(f\). Numerical tests show the performance of the deterministic Fourier algorithm.