一种基于迭代更新的稀疏傅里叶变换改进算法

Improved Sparse FFT Algorithm Based on Iterative Update

快速傅里叶变换（FFT）是信号分析领域的重要算法，具有极其重要的地位。稀疏傅里叶变换（SFFT）是一种低复杂度的傅里叶变换算法，其计算速度是FFT的10～100倍，但是目前的SFFT算法均需要知道信号的稀疏度。针对该问题，文章提出了一种基于迭代更新的SFFT改进算法。该算法在信号稀疏度未知的情况下，通过循环迭代对信号进行更新并设置合适的噪声门限来终止迭代。实验结果表明，该算法计算精度高，抗噪性能好，能很好地解决稀疏度未知信号的频谱分析问题，扩展原算法的适用性。

Fast Fourier Transform （FFT） algorithm plays an important role in signal analysis. Sparse Fourier Transform （SFFT） is one kind of FFT algorithm with low complexity. The computation speed of SFFT is 10 - 100 times faster than that of FFT. However, for traditional SFFT algorithm, it needs to know the corresponding sparse coefficients. To solve this problem, a new SFFT algorithm based on iterative update is presented in this paper. Without knowing the sparse coefficients of a signal, the proposed algorithm can function well by using iteration to update the signal and set a proper noise threshold to terminate the iteration. Experiment results demonstrate that the proposed algorithm has characteristic of high accuracy and good performance on anti-noise. Furthermore, the improved sparse FFT algorithm can be used to analyze the spectrum without knowing the sparse coefficients. Thus, the applicability of SFFT is extended.