Empirical Evaluation of Typical Sparse Fast Fourier Transform Algorithms

Abstract Computing the Sparse Fast Fourier Transform(sFFT) of a K-sparse signal of size N 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 lgorithms have been proposed, which can be classfied 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 theoretical analysis includes the following contents: five operations of ignal, 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, N, K by a standard testing platform and record the run time, percentage of the signal sampled and L0;L1;L2 error with eight different sFFT algorithms. The result of experiments satisfies the inferences obtained in theory.