Sparse Fast Fourier Transform for Exactly and Generally K-Sparse Signals by Downsampling and Sparse Recovery

Sung-Hsien Hsieh, Chun-Shien Lu, Soo-Chang Pei

Fast Fourier Transform (FFT) is one of the most important tools in digital signal processing. FFT costs O(N \log N) for transforming a signal of length N. Recently, Sparse Fourier…