Premium
Deterministic sparse FFT algorithms
Author(s) -
Plonka Gerlind,
Wannenwetsch Katrin
Publication year - 2015
Publication title -
pamm
Language(s) - English
Resource type - Journals
ISSN - 1617-7061
DOI - 10.1002/pamm.201510323
Subject(s) - fast fourier transform , interval (graph theory) , bounded function , algorithm , combinatorics , fourier transform , mathematics , computer science , discrete mathematics , mathematical analysis
In this paper we consider sparse signals ${\bf x}\in {\bf C}^N$ which are known to vanish outside a support interval of length bounded by m < N . For the case that m is known, we propose a deterministic algorithm of complexity ${\cal O}(m\log m)$ for reconstruction of x from its discrete Fourier transform $\widehat{\bf x}\in {\bf C}^N.$ (© 2015 Wiley‐VCH Verlag GmbH & Co. KGaA, Weinheim)