A deterministic sparse FFT algorithm for vectors with small support

Abstract

In this paper we consider the special case where a discrete signal $\mathbf{x}$ of length N is known to vanish outside a support interval of length $m<N$. If the support length $m$ of $\mathbf{x}$ or a good bound of it is a-priori known we derive a sublinear deterministic algorithm to compute $\mathbf{x}$ from its discrete Fourier transform. In case of exact Fourier measurements we require only $\mathcal{O}(m\log m)$ arithmetical operations. For noisy measurements, we propose a stable $\mathcal{O}(m\log N)$ algorithm.

16 pages