一种稀疏度自适应的稀疏傅里叶变换算法

刘 仲,李立春,李慧启

(信息工程大学 信息系统工程学院,郑州 450001)

0 概述

在信号处理领域,离散傅里叶变换(Discrete Fourier Transform,DFT)是最基本的算法之一。而快速傅里叶变换(Fast Fourier Transform,FFT)是最快的DFT算法之一,其算法复杂度只有O(nlogan)。目前,计算DFT的算法复杂度为Θ(n),均与信号长度成正比。在图像处理[1]、宽带频谱感知[2-4]、机器学习理论[5]、多尺度分析[6]、卫星通信[7]等众多科学领域中,许多实际信号都有一定程度的稀疏性或可压缩性。这种结构特殊、广泛存在的信号成为了信号处理领域热门的研究方向。针对离散傅里叶变换,几种频域稀疏的亚线性算法[8-11]相继被提出,但这些算法由于结构的限制只适用于非常稀疏的信号。

近几年,稀疏快速傅里叶变换(sparse Fast Fourier Transform,sFFT)算法成为研究稀疏信号的一大热点,并相继提出了一些实用的sFFT算法。该类算法利用信号频域的稀疏性对频率进行“分桶”,使DFT运算的点数成倍减少,然后通过其他方法实现对原信号完整频谱的重构,从而使算法的复杂度与信号长度成亚线性关系,进而提高信号处理速度。近年来稀疏傅里叶变换的算法硕果累累,研究人员提出了许多算法。这些算法降低了算法复杂度[12-13],拓宽了维度适用范围[14],并实现了算法的并行加速[15],并且推广到了其他变换域[16]。但稀疏傅里叶变换都需要信号以傅氏域的稀疏度为先验信息,通常稀疏度K是未知的,在一定程度上限制了上述算法的应用。为此,针对未知稀疏度的信号,本文提出一种稀疏度自适应的稀疏傅里叶变换算法(Sparsity Adaptive Algorithm for Sparse Fast Fourier Transform,SAsFFT)。……