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

王芳星，劉順蘭

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

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

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

DOI: 10.13954/j.cnki.hdu.2015.01.016

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

王芳星，劉順蘭

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

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

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

DOI:10.13954/j.cnki.hdu.2015.01.016

收稿日期：2014-04-14

通信作者：

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

中圖分類(lèi)號(hào)：TN911.72

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

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

1壓縮感知

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

(1)

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

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

Y=ΦX=ΦΨα=Θα

(2)

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

2稀疏度估計(jì)

本文通過(guò)原子匹配測(cè)試的方法給出初始稀疏度的估計(jì)。下面先給出兩個(gè)命題。

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

3MRAMP算法

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

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

(3)

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

(4)

(5)

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

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

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

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

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

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

圖1　MRAMP算法流程圖

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

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

(6)

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

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

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

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

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

測(cè)量向量長(zhǎng)度M=64，高斯白噪聲環(huán)境中，不同信噪比(Signal Noise Ratio， SNR)下各算法對(duì)信號(hào)的重構(gòu)概率如圖5所示。由圖5可知，各算法的準(zhǔn)確重構(gòu)概率隨著信噪比的增大而增大，MRAMP算法的準(zhǔn)確重構(gòu)概率優(yōu)于SP、OMP、SAMP算法，當(dāng)信噪比大于10 dB時(shí)，所有算法均能準(zhǔn)確重構(gòu)信號(hào)。當(dāng)信噪比為7 dB時(shí)，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)概率對(duì)比

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

5結(jié)束語(yǔ)

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

[7]朱延萬(wàn),趙擁軍,孫兵.一種改進(jìn)的稀疏度自適應(yīng)匹配追蹤算法[J].信號(hào)處理,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