  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
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 ofthem is
thoroughly tested and verified in practice. The theoretical analysis includes
thefollowing 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, 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.
