论文标题
关于使用混叠滤波器的稀疏快速傅立叶变换算法的性能
On Performance of Sparse Fast Fourier Transform Algorithms Using the Aliasing Filter
论文作者
论文摘要
很长一段时间以来，计算大小n的k-sparse信号的稀疏快速傅立叶变换（SFFT）已成为关键主题。 SFFT中主要有两个阶段：频率桶化和频谱重建。频率铲斗等同于通过以下一个过滤器将频率系数放入B存储桶中：Dirichlet内核过滤器，扁平过滤器，混叠滤波器等。光谱重建等于识别在其存储桶中隔离的频率。到目前为止，有40多种不同的SFFT算法通过其独特的方法来计算离散的傅立叶变换（DFT）。为了正确使用它们，紧迫的主题是如何在理论和实践中分析和评估这些算法的性能。本文主要使用混叠滤波器讨论SFFT算法。在第一部分中，本文介绍了三个框架的技术：基于压缩传感（CS）求解器的单发框架，基于两部分图形的剥离框架以及基于二进制树搜索的迭代框架。然后，我们得出了六种相应算法的性能的结论：SFFT-DT1.0，SFFT-DT2.0，SFFT-DT3.0，FFAST，R-FFFAST和DSFFT算法。在第二部分中，我们通过标准测试平台来制作两类实验，以计算不同的SNR，不同n，不同K的信号，并记录运行时间，信号采样的百分比以及在稀疏情况下和普通稀疏情况下的运行时间，L0，L1，L1，L2误差。实验的结果满足了理论上获得的推论。
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. There are mainly two stages in the sFFT: frequency bucketization and spectrum reconstruction. Frequency bucketization is equivalent to hashing the frequency coefficients into B buckets through one of these filters: Dirichlet kernel filter, flat filter, aliasing filter, etc. The spectrum reconstruction is equivalent to identifying frequencies that are isolated in their buckets. More than forty different sFFT algorithms compute Discrete Fourier Transform(DFT) by their unique methods so far. In order to use them properly, the urgent topic of great concern is how to analyze and evaluate the performance of these algorithms in theory and practice. The paper mainly discusses the sFFT Algorithms using the aliasing filter. In the first part, the paper introduces the technique of three frameworks: the one-shot framework based on the compressed sensing(CS) solver, the peeling framework based on the bipartite graph and the iterative framework based on the binary tree search. Then, we get the conclusion of the performance of six corresponding algorithms: sFFT-DT1.0, sFFT-DT2.0, sFFT-DT3.0, FFAST, R-FFAST and DSFFT algorithm in theory. In the second part, we make two categories of experiments for computing the signals of different SNR, different N, different K by a standard testing platform and record the run time, percentage of the signal sampled and L0, L1, L2 error both in the exactly sparse case and general sparse case. The result of experiments satisfies the inferences obtained in theory.
