摘要： 稀疏快速傅里叶变换需要信号以傅氏域的稀疏度为先验信息,但稀疏度通常是未知的,在一定程度上限制了算法的应用。为此,提出一种新的稀疏傅里叶变换算法。在下采样域进行能量检测,得到稀疏度的初始值,通过增大下采样维度提高稀疏度估计的准确性,从而近似估计稀疏度,设定阈值剔除冗余信息从而得到较好效果。实验结果表明,当信号长度大于219或稀疏度小于900时,该算法性能优于西方快速傅里叶变换,且具有较强的鲁棒性。

关键词: 快速傅里叶变换, 稀疏表示, 稀疏度自适应, 运行时间, 降维

Abstract: Sparse Fast Fourier Transform(sFFT) requires the signal to have the sparsity of the Fourier domain as prior information,but the sparsity is usually unknown,which limits the application of the algorithm to a certain extent.therefore,a new sparse Fourier transform algorithm is proposed.The energy is detected in the downsampling domain to get the initial value of the sparsity.The accuracy of the sparsity estimation is increased by increasing the downsampling dimension so as to estimate approximatively the sparsity,and the threshold is set to eliminate the redundant information to obtain the better result.Experimental results show that the performance of the algorithm is superior to Faster Fourier Transform in the West(FFTW) when the signal sizes is greater than 219 or the sparsity is less than 900,and the algorithm has strong robustness.

Key words: Fast Fourier Transform(FFT), sparse representation, sparsity adaptive, runtime, dimension reduction

中图分类号: 

• TP391