Loading…

On Performance of Sparse Fast Fourier Transform Algorithms Using the Flat Window Filter

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...

Full description

Saved in:
Bibliographic Details
Published in:IEEE access 2020, Vol.8, p.79134-79146
Main Authors: Li, Bin, Jiang, Zhikang, Chen, Jie
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:2169-3536
2169-3536
DOI:10.1109/ACCESS.2020.2989327