Fast Computing DFT Method for Sparse Signals Based on Downsampling
Abstract
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.
Keywords
Sparse signal, MPP, Downsampling, Over-determined.
DOI
10.12783/dtetr/iceea2016/6729
10.12783/dtetr/iceea2016/6729
Refbacks
- There are currently no refbacks.