金 秋,王宏艷，范欣妍

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

【信息科學(xué)與控制工程】

基于CoSaMP算法的信號(hào)冗余分析

金 秋,王宏艷，范欣妍

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

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

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

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

1 稀疏表示理論

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

圖1 信號(hào)的稀疏表示

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

(1)

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

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

(2)

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

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

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

2.1壓縮感知理論

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

Y=ΦX

(3)

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

Y=ΦX=ΦΨα=θα

(4)

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

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

(5)

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

2.2Nyquist采樣定理

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

2.3 對(duì)比分析

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

3 CoSaMP算法信號(hào)重構(gòu)

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

輸入：稀疏度K，恢復(fù)矩陣θ,測(cè)值Y

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

2) 求2K個(gè)最大匹配時(shí)原子的索引：

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

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

算法流程如圖2所示。

圖2 CoSaMP算法流程

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

4 實(shí)驗(yàn)仿真

4.1 IFFT與CoSaMP算法信號(hào)重構(gòu)

4.1.1 IFFT重構(gòu)

生成稀疏度K=30，長度N=1 000的信號(hào)，觀測(cè)信號(hào)長度M=200，如圖3所示。對(duì)得到的信號(hào)進(jìn)行頻域分析，得圖4所示的頻譜。

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

圖4 信號(hào)頻譜

計(jì)算信號(hào)頻譜，并使用IFFT對(duì)信號(hào)進(jìn)行還原，結(jié)果如圖5。

圖5 頻域傅里葉反變換

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

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

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

4.1.2 CoSaMP算法信號(hào)重構(gòu)

產(chǎn)生與圖3同樣約束的信號(hào)，并進(jìn)行CoSaMP算法重構(gòu)，重構(gòu)結(jié)果如圖6示，記錄5次仿真的恢復(fù)殘差和對(duì)應(yīng)數(shù)據(jù)的L1范數(shù)，如表2所示。

圖6 CoSaMP算法

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

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

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

4.2CoSaMP算法重構(gòu)范數(shù)與誤差關(guān)系分析

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

圖7 4.1.2實(shí)驗(yàn)次數(shù)及對(duì)應(yīng)數(shù)據(jù)折線

4.3 基于仿真實(shí)驗(yàn)的理論拓展分析

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

5 結(jié)論

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

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

[1] 何昭水,謝勝利,傅予力.信號(hào)的稀疏性分析[J].自然科學(xué)進(jìn)展,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] 謝浪雄.稀疏表示理論及其應(yīng)用研究[D].廣州：廣東工業(yè)大學(xué),2015.

[4] 趙亮.信號(hào)稀疏表示理論及應(yīng)用研究[D].哈爾濱：哈爾濱工程大學(xué),2012.

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

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

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

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

[9] 石光明,劉丹華,高大化,等.壓縮感知理論及其研究進(jìn)展[J].電子學(xué)報(bào),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算法的精確重構(gòu)[J].計(jì)算機(jī)應(yīng)用研究,2015,32(8):2554-2557.

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

(責(zé)任編輯楊繼森)

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算法的信號(hào)冗余分析[J].兵器裝備工程學(xué)報(bào)，2017(9):126-129.