Fast Computing DFT Method for Sparse Signals Based on Downsampling

Fast Fourier transform (FFT) costs O(N log N) for transforming a signal of length N. Previously researchers introduced the sparse fast Fourier transform (sFFT) with computational complexity O(K log N) for exactly K-sparse signal and O(K log N log(N K)) for generally K-sparse signal. In this paper, a new method to fast compute DFT of generally sparse signals is presented. Firstly, the original signal is downsampled with different time shifts, and the discrete Fourier Transforms (DFTs) of downsampled signals are calculated by FFT. Then the DFTs are used to determine and measure the K non-zero (significant) freq. grids by combining the moment preserving problem (MPP) with the BigBand method. The proposed method is hardware-friendly, and simulation results show that proposed method has better recovery performance compared with other methods.