李 超, 王 沛, 王傳正

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234)

一種改進(jìn)的變步長自適應(yīng)匹配追蹤算法

李 超, 王 沛*, 王傳正

(上海師范大學(xué) 信息與機(jī)電工程學(xué)院,上海 200234)

壓縮感知是利用信號的稀疏性和可壓縮性進(jìn)行信號處理的新理論.針對壓縮感知中信號稀疏度未知的問題,提出了一種改進(jìn)的變步長自適應(yīng)匹配追蹤(MVssAMP)算法.該算法通過計算余量與測量矩陣的相關(guān)性,自適應(yīng)地選擇候選集原子,并且通過可變步長更新支撐集,實現(xiàn)信號的精確重建.該算法通過設(shè)置一個參數(shù)來控制步長變化.仿真結(jié)果表明:該算法在誤差范圍內(nèi)實現(xiàn)了信號精確重建,并且重建性能優(yōu)于其他同類算法.

壓縮感知; 信號處理; 匹配追蹤; 自適應(yīng)

0 引 言

壓縮感知(CS)[1-2]理論突破了傳統(tǒng)的奈奎斯特采樣定理,通過遠(yuǎn)低于奈奎斯特采樣的速率對信號進(jìn)行采樣,很大程度上節(jié)約了時間與運算單元.被廣泛地應(yīng)用于語音與圖像處理方面[3-4].

信號的重建算法是CS理論中的一個重要的方面,重建算法的關(guān)鍵是從壓縮感知得到的低維數(shù)據(jù)中精確的恢復(fù)出原始的高維信號.目前國內(nèi)外學(xué)者提出了眾多經(jīng)典壓縮感知重構(gòu)算法,如基追蹤法(BP)[5],匹配追蹤(MP)算法[6],正交匹配追蹤(OMP)算法[7],正則化正交匹配追蹤(ROMP)算法[8],壓縮采樣匹配追蹤(CoSaMP)算法[9]與子空間追蹤算法(SP)[10]等.然而上述的算法都是以已知信號的稀疏度為前提的,在實際應(yīng)用的過程中,信號的稀疏度往往是未知的.文獻(xiàn)[11]提出了稀疏度自適應(yīng)匹配追蹤(SAMP)算法,此算法可以在稀疏度未知的情況下實現(xiàn)對信號的精確重建,但是此算法中用于更新原子候選集大小的步長是固定的,將會帶來精度不夠與過估計的問題.文獻(xiàn)[12-13]均提出了變步長的思想,變步長匹配追蹤(VSAMP)算法通過大步長快速逼近信號的稀疏度,再通過小步長完成對稀疏度的精確估計.該算法可以較好地實現(xiàn)信號的精確重建.然而該算法大步長均采用當(dāng)前步長的固定倍數(shù),可以預(yù)見的是若初始步長過小,時間將會增多,若初始步長過大,重構(gòu)的精確度將會下降.

本文作者提出了一種改進(jìn)的變步長自適應(yīng)匹配追蹤(MVssAMP)算法,通過一個參數(shù)對步長進(jìn)行控制,并且通過分析選取調(diào)整為最優(yōu)參數(shù),獲得了較好的重建效果.

1 壓縮感知與重建算法

假設(shè)K稀疏信號x長度為N,測量矩陣為ΦM×N(M

y=Φx.

(1)

重建算法就是試圖通過測量信號y實現(xiàn)對原始信號x的重建.通常通過求解下式最小l0范數(shù)問題:

min‖x‖0,s.t.y=Φx.

(2)

在實際中允許存在一定的誤差,所以求解式(2)的最優(yōu)化問題通常用一個簡單的近似求解形式代替,如下式(3),其中δ為一個極小的常量.

(3)

上述l0范數(shù)最小問題是一個NP-hard問題,無法直接求解.Donoho和Saunders[14]提出,當(dāng)測量矩陣滿足有限等距性質(zhì)(RIP) 時,可以通過求解一個更加簡單的最小l1范數(shù)優(yōu)化問題得到與式(2)等價的解.

min‖x‖1, s.t.,y=Φx.

(4)

基于l1范數(shù)優(yōu)化求解的貪婪迭代算法應(yīng)運而生.由于本研究是以SAMP算法為基礎(chǔ),下面重點基于SAMP介紹貪婪迭代算法.SAMP是在稀疏度未知的前提下,對信號進(jìn)行精確重構(gòu),具有更好的實際應(yīng)用空間.它通過一個特定步長不斷選取原子,并且借助CoSaMP與SP的回溯思想篩選原子,從而得到與信號最相關(guān)的原子集合,恢復(fù)出原始信號.

SAMP算法首先通過式(5)計算殘差余量與測量矩陣中各列原子的相關(guān)性,然后選取步長大小L的最大值,構(gòu)成新選出的候選索引集.

(5)

然后將新選出的候選索引集與原索引候選集合并,選取合并后對應(yīng)索引集對應(yīng)的測量矩陣中的列向量,組成支撐集.求解y=Φx的最小二乘解

x=arg min‖y-Φx‖=Φ?y.

(6)

選取x中絕對值最大的L項,計算其對應(yīng)的索引集及索引集對應(yīng)的列向量集合,同時計算殘差:

rnew=y-ΦΦ?y.

(7)

當(dāng)殘差滿足迭代中止條件時,退出迭代,最后一次迭代得到的x即為恢復(fù)出的信號,否則通過步長更新索引集與支撐集長度,返回繼續(xù)迭代,直至滿足迭代中止條件.由此可知,SAMP算法是以步長L代替信號稀疏度K,并且一步步對實際的K進(jìn)行逼近,從而完成對信號的估計與恢復(fù).然而可以看出的在SAMP算法中,步長的選取具有重要的影響,通常為了達(dá)到較高的恢復(fù)精度,步長會選取一個較小的數(shù)值,但重建速度將大為下降,耗費大量的時間.后來提出的VSAMP算法采用變化步長逼近稀疏度K,大步長直接選取了小步長的2倍,為了重建精度,同樣小步長選取了一個較小的數(shù)值,雖然比SAMP所有改善,但是大步長的選取仍然需要較多的時間.

SAMP與VSAMP算法均采用SP與CoSaMP的回溯思想,算法的重構(gòu)復(fù)雜度遠(yuǎn)低于BP算法.同時每次迭代選取多個支撐集原子,重構(gòu)速度也大大提高.本文作者提出的MVssAMP算法同樣采用回溯思想篩選支撐集原子,復(fù)雜度較SAMP與VSAMP略有下降.

2 MVssAMP算法

通過閱讀大量的文獻(xiàn),與反復(fù)的實驗可知:為實現(xiàn)信號的精確恢復(fù),更好地逼近信號稀疏度K,步長必須選取一個較小的數(shù)值,同時重構(gòu)算法必須盡可能地減少重構(gòu)時間.在SAMP與VSAMP的基礎(chǔ)上進(jìn)行改進(jìn),提出了一種改進(jìn)的變步長自適應(yīng)匹配追蹤算法(MVssAMP).

MVssAMP算法的步驟如下:

輸入:測量值y,測量矩陣Φ,步長s

步驟一:初始化:初始?xì)埐顁0=y,初始支撐集大小L=s,索引集Ω=?,迭代次數(shù)t=1;

步驟二:通過式(5)計算殘差與測量矩陣的內(nèi)積,選取絕對值最大的L項,對應(yīng)的索引值構(gòu)成索引集Ωadd.

步驟三:合并索引集,T=Ω∪Ωadd.

步驟七:更新步長:如果size(T)≤β×M,則L=L+α×s;否則L=L+s.

3 仿真結(jié)果與分析

在Matlab平臺上對本算法進(jìn)行仿真.以此說明MVssAMP算法的重建性能.

首先在小步長的情況下,對不同參數(shù)α重構(gòu)性能進(jìn)行測試,如圖1所示.本次仿真采用信號長度N=256,稀疏度K=60,測量值M=128,小步長選取s=[1,3,5],α選取1到10.選取高斯矩陣為測量矩陣.進(jìn)行300次蒙特卡洛仿真實驗.仿真結(jié)果表明在初始步長為小步長的情況下,參數(shù)α=5時信號的重建成功率最高,重建性能最好,故下面的仿真均選取最優(yōu)參數(shù)α=5.

圖2為本算法的重建效果圖,從圖2中可以看出信號的重建效果較好,重構(gòu)誤差幅度的數(shù)量級為10-14.

圖1 不同參數(shù)下的信號重建概率

圖2 MVssAMP算法重建信號

下面將MVssAMP算法、VSAMP算法與傳統(tǒng)的SAMP算法進(jìn)行比較.為了避免過估計,選取s=1,分別在不同稀疏度K的條件下(圖3)與不同測量值M的條件下(圖4)進(jìn)行仿真實驗.

由圖3可以看出當(dāng)K≤50時,3種算法均可以完全重建信號.當(dāng)55≤K≤65時,SAMP與VSAMP算法的重建成功率大大下降,雖然MVssAMP算法也有下降,然而成功的概率遠(yuǎn)遠(yuǎn)大于前兩種算法.尤其是當(dāng)60≤K≤65時,SAMP算法與VSAMP算法的成功率趨向于0,而本算法依然有較高的重建成功率,在K=63時,重建成功率依然會達(dá)到70%.

由圖4可以看出,三種算法在相同采樣點的情況下重建成功率相似,但是MVssAMP相對于VSAMP與SAMP算法依然有所提高,在采樣點數(shù)在60～70,MVssAMP算法有5%～10%的提高,在85～100也有3%左右的提高.

圖3 K值與信號重建概率

圖4 M值與信號重建概率

表1給出了3種算法的平均重建時間.MVssAMP在保證較高重建概率的條件下,耗費的重建時間也有所減少.

表1 重建算法與平均重建時間 (s)

通過上述對各種算法的比較,本算法相對于其他算法有一定的優(yōu)勢.

4 結(jié) 論

通過對壓縮感知理論中各種經(jīng)典重建算法的研究,在SAMP算法與VSAMP算法的基礎(chǔ)上提出了一種改進(jìn)的變步長自適應(yīng)匹配追蹤算法.本算法通過一個最優(yōu)參數(shù)的選取,調(diào)整步長變化的大小,從而較快較精確地追蹤到支撐集,對信號進(jìn)行重建.經(jīng)過仿真分析,在最優(yōu)參數(shù)下,本算法可以獲得更好的重建性能.

[1] Candes E J.Compressive sampling [C].Proceedings of the International Congress of Mathematicians,2006,3(8):1433-1452.

[2] Candes E J,Romberg J K,Tao T.Stable signal recovery from incomplete and inaccurate measurements [J].Communications on Pure and Applied Mathematics,2006,59(8):1207-1223.

[3] Ye L,Yang Z,Wang T J,et al.Compressed sensing of speech signal based on row echelonmeasurement matrix and dual affine scaling interior point reconstruction method [J].Acta Electronica Sinica,2012,40(3):429-434.

[4] Ran D F U,Jin W,Ming Y E,et al.Cloud image fusion using compressed sensing in aliasing free contourlet domain [J].Acta Photonica Sinica,2011,40(6):955-960.

[5] Fan J,Lv J.A selective overview of variable selection in high dimensional feature space [C].Statistica Sinica,2010,20(1):101-148.

[6] Mallat S G,Zhang Z.Matching pursuits with time-frequency dictionaries [C].Signal Processing IEEE Transactions on,1993,41(12):3397-3415.．

[7] Tropp J,Gilbert A C.Signal recovery from random measurements via orthogonal matching pursuit [C].Information Theory IEEE Transactions on,2007,53(12):4655-4666.

[8] Needell D,Vershynin R.Signal recovery from incomplete and inaccurate measurements via regularized orthogonal matching pursuit [J].Selected Topics in Signal Processing,2010,4(2):310-316.

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

[10] Dai W.Subspace pursuit for compressive sensing signal reconstruction [C].Information Theory IEEE Transactions on,2009,55(5):2230-2249.

[11] Do T,Nguyen N,et al.Sparse adaptive matching pursuit algorithm for practical compressed Sensing [C].Signals Systems and Computers 2008 42nd Asilomar Conference on IEEE,2008,23(3):581-587.

[12] Gao Rui,Zhao R ZH,Hu S H H.Adaptive matching pursuit reconstruction algorithm based on compressed sensing [J].Acta Optica Sinica.2010,30(6):1639-1644.

[13] Bi X,Chen X,Zhang Y,et al.Variable step size stage-wise adaptive matching pursuit algorithm for image compressed sensing [C].Signal Processing Communication and Computing (ICSPCC) 2013 IEEE International Conference on,Kunming:IEEE,2013.

[14] Zhao R Z H,Liu X Y,Sun M G,et al.Wavelet de-noising via sparse representation [J].Science Information,2009,52(8):1371-1377.

(責(zé)任編輯：包震宇)

An improved variable step size adaptive matching pursuit algorithm

Li Chao, Wang Pei*, Wang Chuanzheng

(College of Information,Mechanical and Electrical Engineering,Shanghai Normal University,Shanghai 200234,China)

Compressed sensing is a new theory of using signal sparsity and compressibility for signal processing.To solve the problem that the signal sparse is unknown in compressed sensing,an modified variable step size adaptive matching pursuit(MVssAMP) algorithm is put forward in this paper.This algorithm achieves the accurate reconstruction of the signal by calculating the correlation between the residual and the measurement matrix,then adaptively selecting candidate sets of atoms,and updating the support set via variable step size.The algorithm controls the step size change by setting a parameter.The simulation results show that the algorithm can achieve the accurate reconstruction of the signal within its error range,and the reconstruction performance is superior to other similar algorithms.

compressed sensing; signal processing; matching pursuit; self-adaption

2015-09-17

李 超(1990-),男,碩士研究生,主要從事數(shù)字信號處理方面的研究.E-mail:79917803@qq.com

導(dǎo)師簡介:王 沛(1970-),女,副教授,主要從事圖像處理方面的研究.E-mail:peiwang@shnu.edu.cn

TN 929.5

A

1000-5137(2017)02-0213-05

*通信作者