Deterministic sparse FFT for M-sparse vectors

Citation

Plonka G, Wannenwetsch K, Cuyt A & Lee W (2018) Deterministic sparse FFT for M-sparse vectors. Numerical Algorithms, 78 (1), pp. 133-159. https://doi.org/10.1007/s11075-017-0370-5

Abstract
In this paper, we derive a new deterministic sparse inverse fast Fourier transform (FFT) algorithm for the case that the resulting vector is sparse. The sparsity needs not to be known in advance but will be determined during the algorithm. If the vector to be reconstructed is M-sparse, then the complexity of the method is at most O(M^2 logN) if M^2 < N and falls back to the usual O(N logN) algorithm for M^2 ≥ N. The method is based on the divide-and-conquer approach and may require the solution of a Vandermonde system of size at most M × M at each iteration step j if M^2 < 2^j . To ensure the stability of the Vandermonde system, we propose to employ a suitably chosen parameter σ that determines the knots of the Vandermonde matrix on the unit circle.

Keywords
Sparse signals; Vandermonde matrices; Discrete Fourier transform; Sparse FFT

Journal
Numerical Algorithms: Volume 78, Issue 1