一種稀疏度自適應的稀疏傅里葉變換算法

劉 仲,李立春,李慧啟

(信息工程大學 信息系統工程學院,鄭州 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)。

1 稀疏傅里葉變換算法

稀疏傅里葉變換算法通過時域降維對頻域稀疏的信號進行處理,將信號的頻域信息壓縮到低維空間中,在快速傅里葉變換后,通過定位和估值2個環節重構得到頻域信號。稀疏傅里葉變換算法的流程如圖1所示。

圖1 稀疏傅里葉變換算法流程

1.1 信號的稀疏表示

x=Fs

(1)

其中,s是信號x在正交基F上的投影系數向量。若s中只有K個系數不為0,其他N-K個系數全為0,那么信號x在頻域上是K-稀疏的,K表示信號x的稀疏度。若s中K個系數值較大,其他N-K個系數很小,且幾乎為0,則稱信號x在頻域上是近似K-稀疏的。若一個信號在頻域上能夠被稀疏表示,則該信號可進行稀疏傅里葉變換,也可以降維到低維空間中。

1.2 時域降維

如果信號在頻域能夠被稀疏表示,當設置若干個桶且桶數比頻率數更多時,那么按照一定規則將各個有效頻率分到這些桶中,每個桶中只存在唯一的頻率。從頻域角度考慮,將每個桶視為一個序列單元,那么長序列可被映射為短序列。對短序列進行快速傅里葉變換,則算法復雜度將大幅度降低。sFFT的時域降維過程可以表示為:

y=ΨB×Nx

(2)

將每一桶作為一個序列單元進行處理,其方法是取桶中的一個有效頻點代表該桶的值,該步驟稱為下采樣。下采樣對x中的元素按索引進行等間隔的累加,其處理過程如式(3)所示。

(3)

為保證取到每一個有效頻點,利用頻域卷積定理,將時域信號與窗函數2個矢量相乘,則在頻域上各桶內唯一存在的有效頻點展寬成多個頻點,這樣在下采樣時就能夠取到有效頻點。本文所使用的窗函數取自文獻[11]的平滑窗函數。

1.3 頻域重構

在正交頻分復用(OFDM)技術的頻偏估計方法中,2個采樣點之間的相位差與頻點坐標呈線性關系。漸近法從相位差角度出發,運用該原理中不同頻率所對應相位不同的特點,通過對相位區間進行能量檢測判斷有效頻率的存在與否。該類方法可對相位二分查找,或劃分成多區段查找[17]逐步迭代得到頻率。二分漸近法保證了算法的魯棒性,但復雜度相對較高;相比之下多區段漸進法速度較快,復雜度較低,但魯棒性較差。

統計法主要從重復統計角度出發,利用哈希映射、孫子定理[11]等方法先確定下采樣所對應頻域中存在頻點的桶,反推出原始信號中可能包含的頻率,通過改變重排參數對哈希逆映射的多次統計,或對不同參數下得到的線性同余方程求解,得到原始信號中的有效頻率。由于統計法的重排隨機進行,因此會產生一定的頻率沖突。在每次循環中存在的虛警也會產生極少量的重構信息誤差[17]。但統計法均衡了算法復雜度和魯棒性,該方法性能較為穩定,具有較好的研究前景。

2 稀疏度自適應的稀疏傅里葉變換算法

為解決未知稀疏度的問題,基于sFFT-1算法的優勢,本文提出了SAsFFT算法。本節從算法總體流程、稀疏度估計的影響因素和稀疏度的確定3個部分介紹SAsFFT算法。

2.1 算法總體流程

SAsFFT利用了信號的頻域稀疏性,在信號稀疏度未知的前提下,通過迭代逐步估計得到信號的稀疏度,從而使算法適用于未知稀疏度的信號。SAsFFT與現有的sFFT算法相比,其改進在于增加了對稀疏度的估計和檢測過程。該算法可以分為3個步驟,其總體流程如圖2所示。

步驟3有效分量篩選。對稀疏傅里葉變換的結果進行能量檢測,剔除無效的虛警分量,得到最終的k個傅氏域信息。

圖2SAsFFT算法流程

2.2 稀疏度估計的影響因素

利用第2.1節中信號的稀疏特性,以及稀疏傅里葉變換中時域降維的性質對頻域稀疏的離散信號進行稀疏度的估計得到預測稀疏度。稀疏度估計的流程如下:

子步驟1初始化預測稀疏度;

子步驟2時域降維;

子步驟3快速傅里葉變換;

對預測稀疏度準確性的影響因素主要有2個:頻譜碰撞和窗函數卷積。本節主要從以下的2個方面進行分析。

2.2.1 頻譜碰撞的影響

稀疏度決定了一個信號變換到下采樣域后的矢量維度,進而影響頻譜碰撞概率。首先可推導在未知稀疏度的條件下,設定稀疏度與碰撞概率的關系。文獻[11]給出了定理1,該定理限定了非零系數落入同一桶中的概率。

定理1若j≠0,n是2的冪次方,σ∈[1 ,n]是一個隨機奇數,則Pr[σj∈[-C,C]mod n]≤4C/n。

證明:令bi為下采樣域的第i個元素。考慮任意i,j∈S,由定理1有:

Prσ,τ[bi=bj]≤ Prσ,τ[|(σi+τ)mod n-(σj+τ)mod n|<

n/B]=Prσ,τ[|σ(i-j)|mod n

那么,從原時域的角度考慮,對于信號矢量x有:

得證。

2.2.2 窗函數卷積的影響

本節闡明窗函數的卷積會對信號中有效頻率產生虛警,使得估計的頻率數增加,導致預測稀疏度大于真實稀疏度。

根據文獻[17]中的定理3.3,以及對本文算法中信號和窗函數的假設,對降維過程結果可得如下的推論。

2.3 信號稀疏度的確定

2.4 算法復雜度分析

(4)

3 仿真結果與分析

為了驗證SAsFFT的可行性和魯棒性,本節對SAsFFT、FFTW和sFFT-1 3種算法進行了仿真實驗。仿真實驗分別是在不同信號長度、不同稀疏度下的算法對比,以及SAsFFT算法的魯棒性仿真。本文算法中所采用測試信號的產生方式參考了文獻[9]。時域降維過程使用的窗函數為2.2節中所定義的窗函數。

信號參數設置如下:信號x的矢量長度為n,在信號的傅氏域上從[1,n]中隨機選擇k個分量,各分量的幅度為1,相位隨機,其他分量設為0。在仿真結果中,每個點代表不同參數的信號,每個點是經過100次獨立的重復實驗的平均結果。在實驗中,與SAsFFT算法進行對比的是FFTW(the Faster Fourier Transform in the West)和sFFT-1[11]。

實驗平臺采用Ubuntu Linux 16.04版本,處理器為Intel(R) Core(TM) i5-4210M CPU @ 2.60 GHz,內存為8 GB。

3.1 信號長度對不同算法的影響比較

對于本文實驗,固定信號稀疏度參數k=50,選擇了8個不同的信號長度分別為n=217,218,…,224。在不同的信號長度下,對同一信號分別運行SAsFFT、 FFTW和sFFT-1,得到3種算法的平均運行時間對比如圖3所示。

圖3 不同信號長度的算法平均運行時間對比

從圖3中可以發現,在橫坐標為對數分度時,SAsFFT、FFTW和sFFT-1的運行時間均呈線性關系,SAsFFT和sFFT-1的斜率基本相同,且比FFTW的斜率小。SAsFFT與sFFT-1相比,在不同信號長度下SAsFFT的平均運算時間均相對較長,但平均運算時間差比較穩定。同時,由圖3可知,若信號稀疏度k=50,當信號長度n>219時,則SAsFFT運算速度比FFTW快。信號長度越長,SAsFFT的平均運算時間越短,其運算速度優勢體現就越明顯。

3.2 信號稀疏度對不同算法的影響比較

對于本文實驗,固定信號長度參數n=222,選擇了11個不同的信號稀疏度k=50,100,200,…,1 000。在不同的信號稀疏度下,對同一信號分別運行SAsFFT、FFTW和sFFT-1,得到3種算法的平均運行時間對比如圖4所示。

圖4 不同信號稀疏度的算法平均運行時間對比

從圖4可以觀察到,FFTW在不同信號稀疏度下運算時間基本保持不變,而SAsFFT和sFFT-1的平均運算時間均呈線性關系。在不同信號稀疏度下SAsFFT的平均運算時間比sFFT-1長,但兩者的平均運算時間差也比較穩定。當信號長度固定不變時,信號稀疏度為900,SAsFFT與FFTW的平均運算時間基本相等。因此,綜合來看,對于小于900的信號稀疏度,SAsFFT的運算時間更快。

除此之外,圖4給出了不同稀疏度下SAsFFT算法的迭代次數。當稀疏度k≤900時,迭代次數維持在2次,可見SAsFFT的稀疏度估計過程比較穩定,即SAsFFT算法的運算時間比較穩定,不會出現較大波動。

3.3 信號稀疏度對算法魯棒性的影響

(5)

在不同的信號稀疏度下,對同一信號分別運行SAsFFT,得到該算法的每符號平均l1誤差對比,如圖5所示。

圖5 不同信號稀疏度的魯棒性對比

由圖5可以得到,對于固定長度的信號,算法不同信號稀疏度的每符號平均l1誤差都小于10-6,算法保持了較高的穩定性,完全可以滿足絕大部分信號的實際應用需求。

4 結束語

本文提出一種基于稀疏度自適應的稀疏傅里葉變換算法。該算法根據頻譜碰撞和窗函數卷積對頻率檢測的影響估計,得到一個稍大于真實稀疏度的預測稀疏度,通過已有的稀疏傅里葉變換后,在算法的輸出中剔除冗余數據,從而得到較好的結果。根據數學理論分析和算法運行的實驗結果表明,該算法實現了未知稀疏度條件下的稀疏傅里葉變換,擴展了稀疏傅里葉變換算法的應用范圍;算法運算量小,復雜度低,在運算時間上快于傳統FFT算法,且完成傅里葉變換后的效果理想,驗證了算法的可靠性。

[1] CHANDRAKASAN A,GUTNIK V,XANTHOPOULOS T.Data Driven Signal Processing:An Approach for Energy Efficient Computing[C]//Proceedings of International Symposium on Low Power Electronics and Design.Washington D.C.,USA:IEEE Press,1996:347-352.

[2] DONOHO D L.Compressed Sensing[J].IEEE Transac-tions on Information Theory,2006,52(4):1289-1306.

[3] CANDES E J,WAKIN M B.An Introduction to Com-pressive Sampling[J].IEEE Signal Processing Magazine,2008,25(2):21-30.

[4] 盧 迅,李立春,李 鷗,等.非重構壓縮樣值跳頻信號時頻聯合估計算法[J].信息工程大學學報,2016,17(4):425-430.

[5] LINIAL N,MANSOUR Y,NISAN N.Constant Depth Circuits,Fourier Transform,and Learnability[J].Journal of the ACM,1989,40(3):607-620.

[6] DAUBECHIES I,RUNBORG O,ZOU A J.A Sparse Spectral Method for Homogenization Multiscale Problems[J].Siam Journal on Multiscale Modeling & Simulation,2007,6(3):711-740.

[7] 范星宇.低軌衛星星載通信信號處理關鍵技術研究[D].北京:北京理工大學,2014.

[8] GILBERT A C,GUHA S,INDYK P,et al.Near-optimal Sparse Fourier Representations via Sampling[C]//Proceed-ings of ACM Symposium on Theory of Computing.New York,USA:ACM Press,2002:152-161.

[9] GILBERT A C,MUTHUKRISHNAN S,STRAUSS M.Improved Time Bounds for Near-optimal Sparse Fourier Representations[C]//Proceedings of SPIE’05.Washington D.C.,USA:IEEE Press,2005:398-412.

[10] IWEN M A,GILBERT A,STRAUSS M.Empirical Evaluation of a Sub-linear Time Sparse DFT Algorithm[J].Communica-tions in Mathematical Sciences,2007,5(4):981-998.

[11] IWEN M A.Combinatorial Sublinear-time Fourier Algori-thms[J].Foundations of Computational Mathematics,2010,10(3):303-338.

[12] HASSANIEH H,INDYK P,KATABI D,et al.Simple and Practical Algorithm for Sparse Fourier Transform[C]// Proceedings of ACM-SIAM Symposium on Discrete Algorithms,Society for Industrial and Applied Mathematics.New York,USA:ACM Press,2012:1183-1194.

[13] 孟祥玉,李 靜,彭 華.一種基于迭代更新的稀疏傅里葉變換改進算法[J].信息工程大學學報,2016,17(6):669-674.

[14] INDYK P,KAPRALOV M.Sample-optimal Fourier Sampling in Any Constant Dimension[C]//Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science.Philadelphia,USA:IEEE Press, 2014:514-523.

[15] WANG C,MAURICIO A P,CHANDRASEKARAN S,et al.Parallel Sparse FFT[C]//Proceedings of Workshop on Irregular Applications:Architectures and Algorithms.New York,USA:ACM Press,2013:10-23.

[16] 周廣福,文成林,高敬禮.基于小波變換與稀疏傅里葉變換相結合的光場重構方法[J].電子學報,2017,45(4):782-790.

[17] HAITHAM H,INDYK P,KATABI D,et al.Nearly Optimal Sparse Fourier Transform[C]//Proceedings of the 44th ACM Symposium on Theory of Computing.New York,USA:ACM Press,2012:563-578.