  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(e.g., sensors, video data, audio, medical image, etc.). The
first stage of sFFT is frequency bucketization through one of these filters:
Dirichlet kernel filter, flat filter, aliasing filter, etc. Compared to other
sFFT algorithms, the sFFT algorithms using the flat filter is more convenient
and efficient because the filtered signal is concentrated both in the time
domain and frequency domain. Up to now, three sFFT algorithms sFFT1.0, sFFT2.0,
sFFT3.0 algorithm have been proposed by the Massachusetts Institute of
Technology(MIT) in 2013. Still, the sFFT4.0 algorithm using the multiscale
approach method has not been implemented yet. This paper will discuss this
algorithm comprehensively in theory and implement it in practice. It is proved
that the performance of the sFFT4.0 algorithm depends on two parameters. The
runtime and sampling complexity are in direct ratio to the multiscale parameter
and in inverse ratio to the extension parameter. The robustness is in direct
ratio to the extension parameter and in inverse ratio to the multiscale
parameter. Compared with three similar algorithms or other four types of
algorithms, the sFFT4.0 algorithm has excellent runtime and sampling complexity
that ten to one hundred times better than the fftw algorithm, although the
robustness of the algorithm is medium.
