稀疏傅里叶变换理论及研究进展

Recent Advances in the Sparse Fourier Transform

稀疏傅里叶变换(sparse Fourier transform,SFT)是一种稀疏信号离散傅里叶变换的新算法,比传统快速傅里叶变换(fast Fourier transform,FFT)更加高效.综述了SFT的理论框架、约束条件及频谱重排、窗函数滤波、降采样FFT等关键技术问题,结合算法最新理论成果,归纳出4种不同的重构方法:哈希映射法、混叠同余法、相位解码法、二分查找法.最后介绍了SFT理论的应用成果,并展望了其未来可能的发展方向.

Sparse Fourier transform（SFT）is a novel algorithm for discreting Fourier transform（DFT）on sparse signals,and is more efficient than the traditional fast Fourier transform（FFT）.Reviewing the theoretical framework,restrictions and the key technical problems such as random spectrum permutation, window filtering and subsampled FFT, our different kinds of reconstruction means：hash mapping,aliasing-based search,phase decoding,binary search were introduced based on the latest theoretical achievements of the algorithms.Finally,some applications based on SFT were introduced,and its outlooks were presented.