Empirical Evaluation of Typical Sparse Fast Fourier Transform Algorithms

Abstract

Computing the Sparse Fast Fourier Transform(sFFT) has emerged as a critical topic for a long time. The sFFT algorithms decrease the runtime and sampling complexity by taking advantage of the signal’s inherent characteristics that a large number of signals are sparse in the frequency domain. More than ten sFFT algorithms have been proposed, which can be classified into many types according to filter, framework, method of location, method of estimation. In this paper, the technology of these algorithms is completely analyzed in theory. The performance of them is thoroughly tested and verified in practice. The techniques involved in different sFFT algorithms include the following contents: five operations of signal, three methods of frequency bucketization, five methods of location, four methods of estimation, two problems caused by bucketization, three methods to solve these two problems, four algorithmic frameworks. All the above technologies and methods are introduced in detail and examples are given to illustrate the above research. After theoretical research, we make experiments for computing the signals of different SNR, length, sparsity by a standard testing platform and record the run time, percentage of the signal sampled and $L_{0},L_{1},L_{2}$ error with eight different typical sFFT algorithms. The result of experiments satisfies the inferences obtained in theory. It helps us to optimize these algorithms and use them selectively.

Keywords

• Sparse Fast Fourier Transform(sFFT)
• flat filter
• spike train filter
• Dirichlet kernel filter bank
• sub-linear algorithms
• computational complexity