Deterministic sparse FFT for \(M\)-sparse vectors (Q1751061)

In this interesting paper, the authors present a new deterministic sparse (inverse) fast Fourier transform (FFT), where the resulting vector \(\mathbf x \in {\mathbb C}^N\) with \(N = 2^J\) is \(M\)-sparse, i.e., \(\mathbf x\) contains only \(M\) nonzero components. This new algorithm which generalizes the sparse FFT of \textit{G. Plonka} and \textit{K. Wannenwetsch} [Numer. Algorithms 71, No. 4, 889--905 (2016; Zbl 1341.65056)] is based on a multi-scale reconstruction of \(\mathbf x\) and uses the solutions of well-conditioned Vandermonde-like systems in each iteration step. The unknown sparsity \(M\) is determined during the algorithm. The computational costs of this method is at most \({\mathcal O}(M^2\,\log N)\) if \(M^2 < N\) and falls back to \(\mathcal{O}(N\,\log N)\) if \(M^2 \geq N\). Numerical tests illustrate the performance of this method.