王芳星，劉順蘭

(杭州電子科技大學(xué)通信工程學(xué)院，浙江 杭州 310018)

摘要：針對壓縮感知中未知稀疏度信號的重構(gòu)問題，提出了一種改進(jìn)的正則化自適應(yīng)匹配追蹤算法。它通過自適應(yīng)變步長迭代對信號稀疏度進(jìn)行估計，并將其作為初始支撐集長度，然后在分階段迭代中正則化篩選原子，最終實(shí)現(xiàn)信號的精確重構(gòu)。仿真結(jié)果表明，該算法重構(gòu)信號的性能和效率均優(yōu)于子空間追蹤算法、正交匹配追蹤算法和稀疏度自適應(yīng)匹配追蹤算法。

關(guān)鍵詞：信號重構(gòu)；壓縮感知；稀疏度；自適應(yīng)；正則化

DOI: 10.13954/j.cnki.hdu.2015.01.016

一種改進(jìn)的正則化自適應(yīng)匹配追蹤算法

王芳星，劉順蘭

(杭州電子科技大學(xué)通信工程學(xué)院，浙江 杭州 310018)

摘要：針對壓縮感知中未知稀疏度信號的重構(gòu)問題，提出了一種改進(jìn)的正則化自適應(yīng)匹配追蹤算法。它通過自適應(yīng)變步長迭代對信號稀疏度進(jìn)行估計，并將其作為初始支撐集長度，然后在分階段迭代中正則化篩選原子，最終實(shí)現(xiàn)信號的精確重構(gòu)。仿真結(jié)果表明，該算法重構(gòu)信號的性能和效率均優(yōu)于子空間追蹤算法、正交匹配追蹤算法和稀疏度自適應(yīng)匹配追蹤算法。

關(guān)鍵詞：信號重構(gòu)；壓縮感知；稀疏度；自適應(yīng)；正則化

DOI:10.13954/j.cnki.hdu.2015.01.016

收稿日期：2014-04-14

通信作者：

作者簡介：王芳星(1988-)，男，江西余江縣人，在讀研究生，壓縮感知.劉順蘭教授，E-mail: liushunlan@163.com.

中圖分類號：TN911.72

文獻(xiàn)標(biāo)識碼：：A

文章編號：：1001-9146(2015)01-0079-05

Abstract:This paper presents a modified regularization adaptive matching pursuit(MRAMP) algorithm for the problem that reconstruct signals with unknown sparsity in compressed sensing. The proposed algorithm adaptively estimates the sparsity with difference steps through stage by stage and set it to the length of the initial support， then gets the accurate target signal by regularization screening of atoms in every stage. Simulation results show that the performance and efficiency of the proposed algorithm is better than subspace pursuit(SP) algorithm， orthogonal matching pursuit(OMP) algorithm and SAMP algorithm.

0引言

壓縮感知(Compressive Sensing， CS)理論充分利用了信號的稀疏度來獲取和處理信號[1]。重構(gòu)算法是壓縮感知理論的關(guān)鍵技術(shù)，其中貪婪算法結(jié)構(gòu)簡單，運(yùn)算少，因此得到很好的運(yùn)用。正交匹配追蹤(Orthogonal Matching Pursuit，OMP)算法[2]是傳統(tǒng)的貪婪算法，它在每次迭代中選取一個原子更新支撐集，效率較低。然而，正則化正交匹配追蹤(Regularized Orthogonal Matching Pursuit， ROMP)算法[3]在每次迭代過程中選取多個支撐集原子重構(gòu)信號，其重構(gòu)速度比OMP算法快。之后出現(xiàn)的子空間追蹤(Subspace Pursuit， SP)算法[4]引入了回溯思想，重構(gòu)復(fù)雜度較低。但上述算法必須已知信號稀疏度，而稀疏度自適應(yīng)匹配追蹤(Sparsity Adaptive Matching Pursuit， SAMP)算法[5]不需要稀疏度作為先驗(yàn)信息。本文針對未知稀疏度信號的重構(gòu)，將SAMP算法的自適應(yīng)、SP算法的回退篩選和ROMP算法的正則化原子選擇相結(jié)合，提出了一種改進(jìn)的正則化自適應(yīng)匹配追蹤(MRAMP)算法并將其與OMP、SAMP和SP算法進(jìn)行了性能比較。仿真結(jié)果表明，MRAMP算法對信號的重構(gòu)性能和效率優(yōu)于其它幾種算法。

1壓縮感知

壓縮感知理論的應(yīng)用需要信號是稀疏或者近似稀疏的，設(shè)X是有限長離散時間信號，可看作空間RN內(nèi)N×1維列向量，假定Ψ={ψ1，ψ2，...，ψN}是RN內(nèi)一組標(biāo)準(zhǔn)正交基，則信號X可表示為：

(1)

式中，Ψ為N×N矩陣，α為投影系數(shù)[αi]=[〈X，ψi〉]構(gòu)成的N×1維列向量?？梢?，X和α是同一個信號的不同表示。如果α中非零元素個數(shù)為K(K<

設(shè)計一個與變換基不相關(guān)的M×N(M

Y=ΦX=ΦΨα=Θα

(2)

式中，Θ=ΦΨ為M×N矩陣，稱為恢復(fù)矩陣。

2稀疏度估計

本文通過原子匹配測試的方法給出初始稀疏度的估計。下面先給出兩個命題。

在SAMP算法中，初始稀疏度設(shè)為1或階段步長取一個較小值，則需要多次匹配、更新、信號估計和殘差更新，降低了算法效率。若初始稀疏度隨便設(shè)為某一常數(shù)或取一個較大的階段步長則會影響算法的精度。針對以上問題，根據(jù)命題2可不斷增加K0的值來對稀疏度進(jìn)行初始估計，當(dāng)條件不滿足時，K0為稀疏度初始估計值，同時可得到初始?xì)埐詈统跏茧A段步長。

3MRAMP算法

SP算法主要思想是回溯迭代，每次迭代首先計算殘差r，然后選擇觀測矩陣Φ的各個原子φi中與殘差最匹配的原子，得到相關(guān)系數(shù)u：

u={ui|ui=|〈r，φi〉|，i=1，2，…，N}

(3)

將u中最大值對應(yīng)的索引S并入支撐集索引F，更新支撐集ΦF，并采用最小二乘法進(jìn)行信號估計以及更新殘差：

(4)

(5)

輸入：M維測量向量Y，M×N觀測矩陣Φ，階段迭代步長step≠0，δK。

1)初始稀疏度K0=1，稀疏度估計步長step1=step，索引集F0=?，S=?(空集)；

2)通過式(3)計算相關(guān)系數(shù)u，并從u中取出K0個最大值對應(yīng)的索引值存入索引集F0中；

5)初始化階段stage=1，初始化迭代次數(shù)n=1，初始階段步長step=「0.5step1?，初始支撐集長度size=K0，索引集F=F0；

6)通過式(3)計算u，取出u中size個最大值對應(yīng)的索引值存入S中；

7)將選出的size個相關(guān)系數(shù)進(jìn)行正則化并將得到的索引值存入S0中，然后將S0并入索引集F，更新支撐集ΦF；

圖1　MRAMP算法流程圖

4算法仿真結(jié)果和分析

為了說明MRAMP算法的正確性和有效性，本文采用正弦信號進(jìn)行實(shí)驗(yàn)。

(6)

式中，f1=100 Hz，f2=200 Hz，f3=300 Hz，采樣頻率fs=800 Hz，ts=1/fs。測量向量長度M=64，原始信號長度N=256，觀測矩陣Φ和稀疏變換矩陣Ψ分別取高斯隨機(jī)矩陣和傅里葉變換矩陣。稀疏度估計步長step1=1，參數(shù)δK=0.35，ε=10-6。

MRAMP算法重構(gòu)信號的仿真結(jié)果如圖2所示，從圖2可以看出該算法能夠很好的重構(gòu)原始信號，并且重構(gòu)均方誤差較小。

圖2　MRAMP算法重構(gòu)信號

M取不同值時，各個算法300次重構(gòu)實(shí)驗(yàn)的平均運(yùn)行時間如圖3所示。由圖3可以看出，MRAMP算法的平均運(yùn)行時間要明顯少于OMP算法、SAMP算法和SP算法。

圖3　M取不同值時，不同算法的平均運(yùn)行時間

測量向量長度M=64，高斯白噪聲環(huán)境中，不同信噪比(Signal Noise Ratio， SNR)下各算法對信號的重構(gòu)概率如圖5所示。由圖5可知，各算法的準(zhǔn)確重構(gòu)概率隨著信噪比的增大而增大，MRAMP算法的準(zhǔn)確重構(gòu)概率優(yōu)于SP、OMP、SAMP算法，當(dāng)信噪比大于10 dB時，所有算法均能準(zhǔn)確重構(gòu)信號。當(dāng)信噪比為7 dB時，MRAMP、OMP、SAMP和SP算法的重構(gòu)概率分別為0.780 0、0.720 0、0.594 0和0.682 0，表明同一信噪比下，MRAMP算法的重構(gòu)概率高于其它幾種算法。因此，在噪聲環(huán)境下，MRAMP算法的重構(gòu)性能優(yōu)于OMP、SAMP和SP算法。

圖4　不同算法準(zhǔn)確重構(gòu)概率對比

圖5　不同信噪比下，信號的重構(gòu)概率

5結(jié)束語

本文在已有的壓縮感知重構(gòu)算法研究的基礎(chǔ)上，將信號的稀疏度估計、SAMP算法的自適應(yīng)、SP算法的回退篩選和ROMP算法的正則化原子選擇相結(jié)合，提出了MRAMP算法。算法通過原子匹配測試得出初始稀疏度作為初始支撐集長度和小能量殘差作為初始?xì)埐?，減少了整個算法迭代次數(shù)，使算法效率得到提高。在變步長分階段迭代過程中逐漸減小迭代步長并利用正則化選取能量最大的原子來更新支撐集，從而更快更精確地逼近信號稀疏度，當(dāng)前后兩次估計信號的差值達(dá)到某一設(shè)定的閥值以下便能精確的重構(gòu)未知稀疏度的信號。仿真結(jié)果表明，MRAMP算法重構(gòu)性能和效率明顯優(yōu)于OMP、SAMP和SP算法。

參考文獻(xiàn)

[1]Donoho D L .Compressed sensing[J].IEEE Trans Information Theory,2006,52(4):1 289-1 306.

[2]Tropp J A , Gilbert A C. Signal recovery from random measurements via orthogonal matching pursuit[J]. IEEE Trans on Information Theory,2007,53(12):4 655-4 666.

[3]Needell D , Vershynin R. Uniform uncertainty principle and signal recovery via regularized orthogonal matching pursuit[J]. Foundations of Computational Mathematics,2009,9(3):317-334.

[4]Dai W , Milenkovic O. Subspace pursuit for compressive sensing signal reconstruction[J] . IEEE Trans on Information Theory,2009,55(5):2 230-2 249.

[5]DO T T, Lu Gan , Nguyen N, et al. Sparsity adaptive matching pursuit algorithm for practical compressed sensing[C]//Pacific Grove: IEEE Computer Society,2008:581-587.

[6]楊成,馮魏,馮輝,等.一種壓縮采樣中的稀疏度自適應(yīng)子空間追蹤算法[J].電子學(xué)報,2010,38(4):1 914-1 917.

[7]朱延萬,趙擁軍,孫兵.一種改進(jìn)的稀疏度自適應(yīng)匹配追蹤算法[J].信號處理,2012,28(1):80-86.

A Modified Regularization Adaptive Matching Pursuit Algorithm

Wang Fangxing ，Liu Shunlan

(SchoolofCommunicationEngineering，HangzhouDianziUniversity，HangzhouZhejiang310018，China)

Key words: signal reconstruction; compressive sensing; sparsity; adaptation; regularization