
The problem of computing the Sparse Fast Fourier Transform(sFFT) of a K-sparse signal of size N has received significant attention for a long time. The first stage of sFFT is hashing the frequency coefficients into $B(\approx {K})$ buckets named frequency bucketization. The process of frequency bucketization is achieved through the use of filters: Dirichlet kernel filter, aliasing filter, flat filter, etc. The frequency bucketization through these filters can decrease runtime and sampling complexity in low dimensions. It is a hot topic about sFFT algorithms using the flat filter because of its convenience and efficiency since its emergence and wide application. The next stage of sFFT is the spectrum reconstruction by identifying frequencies that are isolated in their buckets. Up to now, there are more than thirty different sFFT algorithms using the sFFT idea as mentioned above by their unique methods. An important question now is how to analyze and evaluate the performance of these sFFT algorithms in theory and practice. In this paper, it is mainly discussed about sFFT algorithms using the flat filter. In the first part, the paper introduces the techniques in detail, including two types of frameworks, five different methods to reconstruct spectrum and corresponding algorithms. We get the conclusion of the performance of these five algorithms, including runtime complexity, sampling complexity and robustness in theory. In the second part, we make three categories of experiments for computing the signals of different SNR, different $N$ , and different $K$ by a standard testing platform and record the run time, percentage of the signal sampled, and $L_{0},L_{1},L_{2}$ error both in the exactly sparse case and general sparse case. The result of experiments is consistent with the inferences obtained in theory. It can help us to optimize these algorithms and use them correctly in the right areas.
computational complexity, Electrical engineering. Electronics. Nuclear engineering, flat window filter, sub-linear algorithms, Sparse fast Fourier transform (sFFT), TK1-9971
computational complexity, Electrical engineering. Electronics. Nuclear engineering, flat window filter, sub-linear algorithms, Sparse fast Fourier transform (sFFT), TK1-9971
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 16 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
