基于CoSaMP算法的信號冗余分析

金 秋,王宏艷，范欣妍

(中國人民解放軍裝備學院， 北京 101416)

【信息科學與控制工程】

基于CoSaMP算法的信號冗余分析

金 秋,王宏艷，范欣妍

(中國人民解放軍裝備學院， 北京 101416)

以稀疏表示理論為出發(fā)點，分析信號的壓縮感知理論與傳統(tǒng)Nyquist采樣定理的理論對比結果，根據(jù)CoSaMP算法和IFFT信號重構結果，定性和定量地分析了信號內(nèi)部冗余性與利用這種冗余特征進行減運算量處理的可行性，進一步探討信號的非均勻化處理，包括分數(shù)域和分形等方法在信號處理領域的適應性。

非均勻化處理；稀疏表示理論；壓縮感知；CoSaMP算法

20世紀90年代,信號處理領域出現(xiàn)了一種全新的劃時代的處理方法——信號的稀疏表示[1]。稀疏表示理論的思想產(chǎn)生后給信號處理領域注入了活力，發(fā)展而來的壓縮感知理論在各個方面都得到重大應用，使得信號處理的發(fā)展邁開大的步伐。信號的稀疏表示從一種全新的角度，揭示了將信息而不是其載體作為處理對象的可行性，用很少的數(shù)據(jù)量恢復出接近完整信息的能力，讓它迅速在通信領域大放光彩。在信號處理領域，若采用經(jīng)典的處理方法即用Nyquist采樣定理處理信號，相對于稀疏表示理論對信號的處理，會表現(xiàn)出數(shù)據(jù)量較大的特點，減緩處理效率。稀疏表示理論所發(fā)展的壓縮感知理論對信號的處理優(yōu)勢從本質(zhì)上反映了信號內(nèi)部有很大的相干性，本研究使用傳統(tǒng)采樣方法對信號進行IFFT與CoSaMP算法對信號的重構，從而對信號本身的信息進行稀疏性分析，進一步探討了未來信號處理趨勢，展示非均勻處理方法的優(yōu)勢。

1 稀疏表示理論

1993年Mallat提出，任何信號都可以用超完備字典表示，并且這個超完備字典越稀疏，其重構的信號越精確[2]。這表明，任何信號經(jīng)過變換都具有稀疏性，如圖1所示，讓信號表現(xiàn)出稀疏性的關鍵就在于這個字典的建立。

圖1 信號的稀疏表示

根據(jù)信號理論，對于時域信號X∈Rm,可以用一組完備正交基Ψi∈Rm表示

(1)

其中：α為n×1的系數(shù)向量；Ψ=[Ψ1,Ψ2,…,Ψn]為一組完備基，若式(1)中αn僅有k個元素不為零，則認為信號X在Ψ上稀疏，并稱Ψ為信號X的系數(shù)字典。

受Ψ維數(shù)影響，此時α中系數(shù)必然大多數(shù)不為0，所以α定是非稀疏的。將信號分解為n個m維向量Ψj∈Rm，j=1,2,…,n(n>m)的線性組合

(2)

此時對于Ψ=[Ψ1,Ψ2,…,Ψn]∈Rm×n(n>m)來說，n個向量不可能是正交基，必然存在線性相關。為了和式(1)情況下的基區(qū)分開來，式(2)情況下的列向量通常被稱作框架或者原子，很顯然，原子的集合是冗余的，是過完備的。過完備的框架所組成的矩陣Ψ=[Ψ1,Ψ2,…,Ψn]∈Rm×n(n>m)被定義為字典或者庫[3]。字典Ψ=[Ψ1,Ψ2,…,Ψn]∈Rm×n(n>m)中行小于列，其秩為m。

式(2)由于其過完備性特點可得出一個過完備方程，所以在求信號的稀疏解時可以得到無窮多解，如何在這無窮多解中尋找到一個最符合要求的解，便成為信號稀疏化的重點。常用方法是通過矩陣的和范數(shù)進行匹配追蹤(MP)或者基追蹤(NP)等方法進行優(yōu)化求解，達到用極少系數(shù)的稀疏Ψ來表示信號的目的[4]。

2 稀疏表示理論的信號感知應用與傳統(tǒng)采樣方法比較

2.1壓縮感知理論

稀疏表示理論的應用在信號處理過程中發(fā)展為壓縮感知(CS)理論。壓縮感知理論包含信號稀疏表示、信號的非相干檢測以及信號重構算法等3個核心內(nèi)容[5]。對信號X進行時域觀測，則有

Y=ΦX

(3)

其中Φ∈Rm×n為觀測的矩陣，Y∈Rm×n為觀測所得的觀測值。由于方程欠定，所以不能夠用測量值Y求得信號X。故將式(2)代入式(3)，可得

Y=ΦX=ΦΨα=θα

(4)

由于是稀疏的，可通過稀疏優(yōu)化求解

min‖α1‖s.t.Y=θα

(5)

用基于范數(shù)來求解信號的最優(yōu)化解，信號同樣可以重構[6]，目前已經(jīng)拓展為算法的優(yōu)化求解。

2.2Nyquist采樣定理

美國電信工程師H.奈奎斯特于1928年提出：當信號函數(shù)f(t)的最高頻率分量為fm時,f(t)的值可由一系列采樣間隔小于或等于1/(2fm)的采樣值來確定,即采樣點的重復頻率f≥(2fm)[7]。這為均勻化的采樣提供了一定程度的約束，在迄今為止的很長一段時間內(nèi)，為信號采樣頻率和帶寬設置提供了基本的指導。

2.3 對比分析

傳統(tǒng)重構方法主要是利用對滿足Nyquist采樣定理的信號采樣值進行IFFT變換，其效果相當于用采樣值個數(shù)的sinc函數(shù)去逼近原始函數(shù)，在本質(zhì)上對均勻采樣值進行了遍歷運算，無論能量集中還是冗余量，其依據(jù)為信號的連續(xù)性以及有限帶寬。而基于稀疏理論的CS重構信號的算法則是利用信號經(jīng)過變換和處理后產(chǎn)生的稀疏性，通過信號的另一種表示，對信號所用到的數(shù)據(jù)進行壓縮和選取，通過較少的關鍵信息最優(yōu)化獲得更好的恢復效果[8]。特別對分布于高頻段的信號處理時，用傳統(tǒng)方法進行采樣會使得采樣帶寬更加寬大，采樣結果產(chǎn)生大的冗余，浪費了很大帶寬。如若根據(jù)信號在其他表示方法下獲得稀疏性表示，采用CS方法能更好地處理[9]。理論上信號均能通過運算獲得稀疏性，在實際應用中大部分信號也可壓縮，所以CS方法具有很大的應用前景。

3 CoSaMP算法信號重構

本節(jié)專門通過介紹基于壓縮感知的壓縮采樣匹配追蹤(CompressiveSampling MP)算法[10]以為下節(jié)仿真實驗奠定基礎。該算法是D.Needell提出的重構算法，算法本質(zhì)是一種貪婪算法，其算法流程[11]為

輸入：稀疏度K，恢復矩陣θ,測值Y

1) 初始賦值：r0=y，V0=[ ],t=1;

2) 求2K個最大匹配時原子的索引：

|rt-1,θj|, 2k};

3) 構建候選集：C=Vt-1∪B;

算法流程如圖2所示。

圖2 CoSaMP算法流程

基于壓縮感知的CoSaMP算法在一定稀疏度下，可以做到在信號的低數(shù)據(jù)處理量下對信號進行采集重構。

4 實驗仿真

4.1 IFFT與CoSaMP算法信號重構

4.1.1 IFFT重構

生成稀疏度K=30，長度N=1 000的信號，觀測信號長度M=200，如圖3所示。對得到的信號進行頻域分析，得圖4所示的頻譜。

圖3 稀疏信號的產(chǎn)生

圖4 信號頻譜

計算信號頻譜，并使用IFFT對信號進行還原，結果如圖5。

圖5 頻域傅里葉反變換

通過仿真產(chǎn)生出擁有復雜頻譜的信號，并對其進行IFFT變換，記錄5次仿真的恢復殘差和對應數(shù)據(jù)的L1范數(shù)，如表1所示。

表1 IFFT仿真數(shù)據(jù)

從實驗所得的仿真數(shù)據(jù)可以看出，傳統(tǒng)處理方法對信號的恢復殘差平均值為2.233 0，信號變換過程中所利用的數(shù)據(jù)量用L1范數(shù)衡量，計算得出IFFT變換所使用一維L1信號范數(shù)平均值為7.607 4。

4.1.2 CoSaMP算法信號重構

產(chǎn)生與圖3同樣約束的信號，并進行CoSaMP算法重構，重構結果如圖6示，記錄5次仿真的恢復殘差和對應數(shù)據(jù)的L1范數(shù)，如表2所示。

圖6 CoSaMP算法

CoSaMP算法對信號的恢復殘差平均值為1.493 2e-15。與第4.1節(jié)中IFFT恢復殘差相差非常之大，說明應用基于壓縮感知理論的CoSaMP算法對于復雜帶寬信號有著非常突出的優(yōu)勢，在信號處理上有著更小數(shù)量級的誤差。

通過CoSaMP算法所使用的信號L1范數(shù)平均值為1.542 1，相差4.933倍。換言之，使用CoSaMP算法大大的減少了運算和恢復所使用的數(shù)據(jù)量。傳統(tǒng)采樣利用脈沖串函數(shù)進行均勻采集，對于能量集中頻譜復雜的信號處理顯得捉襟見肘，而CoSaMP算法在較少數(shù)據(jù)量的條件下得到了低于傳統(tǒng)采樣很大誤差的重構信號，說明了壓縮感知信號的巨大優(yōu)勢，也說明了信號采集過程中本不需要很多的采集量，說明信號本身具有巨大的冗余。

表2 CoSaMP算法仿真數(shù)據(jù)

4.2CoSaMP算法重構范數(shù)與誤差關系分析

由圖7可知，CoSaMP算法重構信號所使用數(shù)據(jù)的L1范數(shù)與恢復殘差之間有粗略的相關性，表現(xiàn)為L1范數(shù)越小，恢復殘差越小。根據(jù)式2.3可知，通過極小化變換系數(shù)L1范數(shù)即最優(yōu)化條件下的稀疏解，矩陣Θ就可以更好地滿足用來估計原始信號的約束條件。

圖7 4.1.2實驗次數(shù)及對應數(shù)據(jù)折線

4.3 基于仿真實驗的理論拓展分析

CS中對數(shù)據(jù)的獲取，與傳統(tǒng)意義上利用脈沖串函數(shù)均勻采集數(shù)據(jù)的方法截然不同。信號的稀疏程度越高，恢復出原始信號所需的運算量越少，也就是感知量越少，通過這一點極大地提高了信號處理和感知的速率。一般來說，信號中能量或功率集中的部分，攜帶著信號的絕大部分信息。信號的稀疏處理實際上揭示了信號信息間的極大相干性，將信號從形式和數(shù)學處理進一步擴展為對信號所攜帶的信息的直接處理。從另一個角度來看，對于高冗余的目標使用非均勻手段，針對其特定的信息進行提取，能使目標的利用率得到很大提升。用非均勻的手段解決問題，適用于信息在信號中的分布特點，往往使工作事半功倍。

5 結論

壓縮感知理論針對于信號處理在一定程度上打破了經(jīng)典采樣定理的束縛，無論是在信號圖像，還是其他領域，這種方法也給我們一定的啟示。比如，均勻的處理方法可以得到信號信息，但是往往要付出大的計算量和冗余空間的代價。真正的高效處理問題，就要在問題內(nèi)部尋找其重點部分。信號的冗余性使我們認識到，信號內(nèi)的信息有很大的相干性和自相似性，所以稀疏理論和分形理論[12]等非均勻處理方法必然可以在該領域有所作為。

目前針對信號中含載信息的處理方法越來越受到關注。雖然在效果上非常顯著，但這種尋找最優(yōu)表示方法在使用過程中需要很多條件。實踐始終在接近理論，但是還是有一定出入，為下一步的研究加上了斯芬克斯式困難。在未來高精尖的研究中，非均勻、非平穩(wěn)、非理想狀態(tài)的處理和運算方式必然取代均勻、平穩(wěn)、理想狀態(tài)的思維推論，有望成為常態(tài)。

[1] 何昭水,謝勝利,傅予力.信號的稀疏性分析[J].自然科學進展,2006(9):1167-1173.

[2] MALLAT S,ZHANGZ.Adaptive time-frequency transform[C]//IEEE International Conference on Acoustics,Speech,and Signal Processing:Digital Speech Processing.IEEE Computer Society,1993:241-244.

[3] 謝浪雄.稀疏表示理論及其應用研究[D].廣州：廣東工業(yè)大學,2015.

[4] 趙亮.信號稀疏表示理論及應用研究[D].哈爾濱：哈爾濱工程大學,2012.

[5] 江海,林月冠,張冰塵,等 基于壓縮感知的隨機噪聲成像雷達[J].電子與信息學報,2011(3):672-676.

[6] 高雪.基于壓縮感知的圖像重構算法研究[D].哈爾濱：哈爾濱理工大學,2015.

[7] 奧本海姆,謝弗,董士嘉,等.數(shù)字信號處理[M].北京:科學出版社,1980.

[8] DONOHO D L.Compressed sensing[J].IEEE Trans.on Information Theory,2006，52(4)：1289-1306.

[9] 石光明,劉丹華,高大化,等.壓縮感知理論及其研究進展[J].電子學報,2009,37(5):1070-1081.

[10] NEEDELL D,TROPP J A.CoSaMP:Iterative signal recovery from incomplete and inaccurate samples[J].Applied & Computational Harmonic Analysis,2009,26(3):301-321.

[11] 郎利影,王勇,白文慶,等.基于壓縮感知CoSaMP算法的精確重構[J].計算機應用研究,2015,32(8):2554-2557.

[12] 孫洪軍,趙麗紅.分形理論的產(chǎn)生及其應用[J].遼寧工學院學報,2005(2):113-117.

(責任編輯楊繼森)

SignalRedundancyAnalysisBasedonCoSaMPAlgorithm

JIN Qiu， WANG Hongyan, FAN Xinyan

(Academy of Equipment Command & Technology of PLA, Beijing 101416, China)

Aiming at the expansion of the new method of signal processing, from the sparse representation theory as the starting point, combining the signal compression perception theory with the traditional Nyquist sampling theorem, the internal performance of the signal is a great redundancy, and through CoSaMP Algorithm and IFFT transform, the results are analyzed and compared.The feasibility of the internal redundancy and the redundancy processing are analyzed qualitatively and quantitatively.Further, the nonuniformization of the signal includes fractional domain and fractal method will be in the signal processing and will be a great development.

nonuniformization; sparse representation theory; compression perception; CoSaMP algorithm

2017-04-20；

：2017-05-20

金秋(1995—)，男，碩士研究生，主要從事通信與信息工程研究。

10.11809/scbgxb2017.09.026

format:JIN Qiu，WANG Hongyan, FAN Xinyan.Signal Redundancy Analysis Based on CoSaMP Algorithm[J].Journal of Ordnance Equipment Engineering,2017(9):126-129.

TN911.7

：A

2096-2304(2017)09-0126-04

本文引用格式：金秋,王宏艷，范欣妍.基于CoSaMP算法的信號冗余分析[J].兵器裝備工程學報，2017(9):126-129.