Recent Advances in the Sparse Fourier Transform

Sparse Fourier transform (SFT) is a novel algorithm for discreting Fourier transform (DFT) on sparse signals, and is more efficient than the traditional fast Fourier transform (FFT). Reviewing the theoretical framework, restrictions and the key technical problems such as random spectrum permutation, window filtering and subsampled FFT, our different kinds of reconstruction means:hash mapping, aliasing-based search, phase decoding, binary search were introduced based on the latest theoretical achievements of the algorithms. Finally, some applications based on SFT were introduced, and its outlooks were presented.