论文标题
关于多尺度稀疏快速傅立叶变换算法的性能
On Performance of Multiscale Sparse Fast Fourier Transform Algorithm
论文作者
论文摘要
很长一段时间以来，计算大小n的k-sparse信号的稀疏快速傅立叶变换（SFFT）已成为关键主题。 SFFT算法通过利用信号固有的特征来降低运行时和采样复杂性，即频域中大量信号稀疏（例如，传感器，视频数据，音频，医学图像等）。 SFFT的第一阶段是通过其中一个过滤器之一的频率桶化：与其他SFFT算法相比，使用平面滤波器的SFFT算法更方便，更有效，因为过滤的信号都集中在时域和频域中。到目前为止，2013年，马萨诸塞州理工学院（MIT）提出了三种SFFT算法SFFT1.0，SFFT2.0，SFFT3.0，SFFT3.0算法。仍然尚未实施SFFT4.0算法的SFFT4.0算法。本文将在理论上全面讨论该算法，并在实践中实施。证明SFFT4.0算法的性能取决于两个参数。运行时和采样复杂性的直接比率与多尺度参数以及与扩展参数的逆比相对比。鲁棒性是直接比例与扩展参数的比例，并且与多尺度参数的反比例为逆比。与三种类似的算法或其他四种类型的算法相比，SFFT4.0算法具有出色的运行时和采样复杂性，比FFTW算法要好十到一百倍，尽管该算法的鲁棒性是培养基的。
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.
