張松江 周 密 張傳林

(暨南大學(xué)信息科學(xué)技術(shù)學(xué)院 廣東 廣州 510000)

?

步長(zhǎng)自適應(yīng)的前向后向匹配追蹤算法

張松江 周 密 張傳林

(暨南大學(xué)信息科學(xué)技術(shù)學(xué)院 廣東 廣州 510000)

稀疏度自適應(yīng)的匹配追蹤算法(SAMP)是基于壓縮感知理論的信號(hào)重建經(jīng)典算法。針對(duì)稀疏度未知的信號(hào)重建，提出步長(zhǎng)自適應(yīng)的前向后向匹配追蹤(AFBMP)算法，AFBMP算法在稀疏度自適應(yīng)匹配追蹤算法的框架下，前向搜索過程中采用對(duì)數(shù)型自適應(yīng)變化的步長(zhǎng)選擇匹配原子，然后通過后向策略修正前向階段造成的錯(cuò)誤，刪除支撐集中的部分錯(cuò)誤原子，最終實(shí)現(xiàn)信號(hào)的精確逼近。實(shí)驗(yàn)表明AFBMP算法比SAMP算法能夠更加高效地重建稀疏度未知的信號(hào)。

壓縮感知 重構(gòu) 前向后向 稀疏度自適應(yīng) 匹配追蹤算法

0 引 言

隨著科學(xué)技術(shù)的飛速發(fā)展，在信號(hào)的采樣和處理過程中，利用信號(hào)的帶寬來表示信號(hào)已不能滿足現(xiàn)實(shí)的需要，因?yàn)殡S著信號(hào)攜帶的信息量逐漸增加，采樣速度和處理速度就會(huì)變得越來越慢，同時(shí)這些數(shù)據(jù)的存儲(chǔ)問題也是不容忽視的。雖然人們采用一種壓縮的方式來表示信號(hào)，但是這種方式會(huì)導(dǎo)致大量的信息資源被拋棄，所以采用帶寬來表示信號(hào)的信息是不合理的。而信號(hào)的稀疏性是近幾年信號(hào)處理領(lǐng)域的新寵，它可以更加本質(zhì)地表示信號(hào)，因此基于信號(hào)的稀疏性提出的壓縮感知理論得到了廣泛的認(rèn)可。

壓縮感知理論(CS)[1,2]作為一種全新的采樣理論，利用隨機(jī)采樣獲取信號(hào)的離散樣本，然后通過非線性重建算法對(duì)信號(hào)進(jìn)行重建。該理論指出：如果信號(hào)在某個(gè)變換域上是稀疏的或者認(rèn)為是可以壓縮的，那就可以通過一個(gè)新的觀測(cè)矩陣將高維的信號(hào)映射到一個(gè)低維空間中，這樣就可以將問題轉(zhuǎn)化為最優(yōu)化問題，進(jìn)而重構(gòu)出原始信號(hào)。該理論通過稀疏性以及等距約束準(zhǔn)則來完成高速率的采樣，又包含了大量的重要信息。壓縮感知理論因?yàn)榭梢酝瑫r(shí)完成數(shù)據(jù)的采集和壓縮，大大節(jié)約了時(shí)間和資源，所以得到了廣泛的應(yīng)用。

雖然壓縮感知理論可以大大降低采樣和計(jì)算的成本，但是如何設(shè)計(jì)出一種快速的魯棒的重建算法是該理論的核心問題。隨著對(duì)CS理論研究的不斷深入，為了通過低維數(shù)據(jù)來實(shí)現(xiàn)對(duì)原始信號(hào)的重構(gòu)，近年來越來越多的重構(gòu)算法被提出。目前貪婪迭代算法是學(xué)者們研究最多的算法，這種算法重構(gòu)精度高、計(jì)算量小并且易于實(shí)現(xiàn)。比如Mallat等人采用正交策略提出了正交匹配追蹤算法(OMP)[4,5]、Needell又在正交匹配追蹤算法放入基礎(chǔ)上加入正則化思想，提出正則化正交匹配追蹤算法(ROMP)[6]、Tropp根據(jù)隨機(jī)測(cè)量矩陣思提出了壓縮采樣匹配追蹤算法(CoSaMP)[7]、Dai借鑒回溯序貫編碼理論，提出了子空間追蹤算法(SP)[8]以及Donoho等人考慮稀疏度未知的情況，打破傳統(tǒng)局限，提出了一種稀疏度自適應(yīng)的匹配追蹤算法(SAMP)[9,10]。貪婪迭代算法因其重建速度快和精度高而得到廣泛應(yīng)用，然而大部分貪婪算法都是通過已知稀疏度來控制算法重建的迭代次數(shù)，而在實(shí)際問題中，稀疏度不一定是已知的，并且當(dāng)稀疏度固定時(shí)也可能會(huì)對(duì)重構(gòu)精度造成影響。

SAMP算法突破了傳統(tǒng)的匹配算法要以稀疏度已知為前提的限制，解決了在稀疏度未知的條件下的重建問題。SAMP算法的重建速度主要取決于固定步長(zhǎng)的選擇，雖然在重構(gòu)精度上有了一定的提高，但是依然不能得到滿意的效果。另外根據(jù)該算法的迭代機(jī)制，每次迭代過程中都會(huì)增加支撐集中的原子個(gè)數(shù)，這樣就會(huì)有越來越多的原子被加入到支撐集中，而又無法刪除支撐集中部分錯(cuò)誤原子，所以該算法有一定的局限性。為了解決這一問題，有學(xué)者提出了MSAMP算法[11]，該算法在SAMP算法的框架下通過原子匹配估計(jì)稀疏度，然后利用階段步長(zhǎng)來實(shí)現(xiàn)對(duì)原始信號(hào)的估計(jì)，但這種算法在同一階段的步長(zhǎng)依然是一個(gè)固定值，因此重構(gòu)精度很大程度上依賴于每個(gè)階段步長(zhǎng)的選擇。而LSAMP算法[12]則是在不同的階段采用了對(duì)數(shù)型變化的步長(zhǎng)，該算法在采樣率較低時(shí)重構(gòu)效果依然很好。但是這些算法本質(zhì)上都屬于前向貪婪算法，前向算法最大的缺點(diǎn)就是不能修改前一步迭代造成的錯(cuò)誤，原子一旦被選入支撐集便無法刪除。例如圖1所示，假設(shè)特征向量x是由觀測(cè)矩陣中的向量α1、α2構(gòu)成，然而觀測(cè)矩陣中另外一個(gè)向量α3比其他兩個(gè)向量更接近特征向量x，這樣當(dāng)采用像OMP、SAMP這類前向貪婪算法時(shí)首先會(huì)選擇α3，之后才會(huì)選擇α1、α2，并且這類算法還不能刪除α3，這樣的結(jié)果并不是我們想要的。事實(shí)上，只有在觀測(cè)矩陣中的向量不相關(guān)時(shí)前向貪婪算法才比較適用。

圖1 特征向量圖示

考慮到前向貪婪算法的缺點(diǎn)，很容易想到利用后向貪婪算法來進(jìn)行改善。后向貪婪算法首先選擇全部原子，然后逐一刪除使重建誤差最小的原子。這種算法雖然不會(huì)陷入局部最優(yōu)問題，但是其計(jì)算代價(jià)非常高，因?yàn)橐话闱闆r下觀測(cè)矩陣中M<

目前壓縮感知理論在很多方面得到了應(yīng)用，比如：吳延海提出了基于改進(jìn)SP算法的壓縮感知圖像重構(gòu)[13]，廖斌提出了一種基于壓縮感知的盲數(shù)字水印算法[14]，李秀霞提出了基于壓縮感知的合成孔徑雷達(dá)圖像目標(biāo)識(shí)別[15]等。越來越多的學(xué)者們將壓縮感知利用到人臉識(shí)別、醫(yī)學(xué)CT圖像重建、語音識(shí)別、衛(wèi)星遙感圖像融合、無線傳感器網(wǎng)絡(luò)、探地雷達(dá)成像中。因此對(duì)壓縮感知理論的進(jìn)一步研究就變得十分有意義。

1 壓縮感知理論以及重構(gòu)算法

假設(shè)x為長(zhǎng)度為N的原始稀疏信號(hào)，即x的稀疏度為K，K<

通常采用求解以下最優(yōu)化問題來從測(cè)量信號(hào)y中重建出信號(hào)x：

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

(1)

對(duì)于式(1)求最優(yōu)解問題是NP難題[16-18]，而最小化l2范數(shù)問題又不能保證解的稀疏性。但是Candes等人指出，如果x足夠稀疏，Φ滿足約束等距條件RIP(Restricted Isometry Property)[19]時(shí)：

(2)

其中， δK∈(0,1)表示K稀疏度下的約束等距常數(shù)，此時(shí)就可以將問題轉(zhuǎn)化為求解l1范數(shù)最小化：

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

(3)

通過利用匹配追蹤算法就可以進(jìn)行對(duì)式(3)的近似求解。OMP算法、ROMP算法等都是在給定稀疏度的基礎(chǔ)上進(jìn)行的重構(gòu)，然而在實(shí)際應(yīng)用中，信號(hào)的稀疏度K往往是未知的，這在一定程度上給信號(hào)的重構(gòu)帶來了挑戰(zhàn)，于是Thong T.Do等人為了解決這一問題，提出了稀疏度自適應(yīng)的匹配追蹤算法，將信號(hào)重構(gòu)問題轉(zhuǎn)化為分階段處理的過程，打破了傳統(tǒng)的稀疏度已知的限制。之后更多學(xué)者專注于對(duì)SAMP算法的改進(jìn)，比如變步長(zhǎng)的MSAMP算法和對(duì)數(shù)型變步長(zhǎng)的LSAMP算法。這些算法很好地解決了步長(zhǎng)固定問題，重構(gòu)效果也得到了很大的改善。

2 SAMP算法及其改進(jìn)

SAMP算法實(shí)現(xiàn)了在稀疏度未知的情況下對(duì)信號(hào)的重構(gòu)。該算法首先選取步長(zhǎng)step，然后計(jì)算余量r和觀測(cè)矩陣Φi的內(nèi)積，其中Φi表示觀測(cè)矩陣的每一列，根據(jù)內(nèi)積值，選取size個(gè)最大的相關(guān)系數(shù)，將這些系數(shù)所對(duì)應(yīng)的原子加入到索引集中。接著合并上一階段產(chǎn)生的支撐集得到候選集，再進(jìn)行一次余量與候選集的內(nèi)積，同樣選取size個(gè)相關(guān)系數(shù)最大的原子作為支撐集F。此時(shí)更新余量r，如果當(dāng)前余量小于迭代前的余量，則繼續(xù)迭代，否則進(jìn)入下一階段，根據(jù)步長(zhǎng)更新支撐集容量size=size×step，重復(fù)上述步驟，直到余量r小于某個(gè)閾值停止迭代。

具體算法如下：

(1) 余量r=y，支撐集長(zhǎng)度size=step，階段stage=1，支撐集F=?；

(2) 計(jì)算余量r和Φi內(nèi)積的絕對(duì)值，從中選取size個(gè)最大值對(duì)應(yīng)的索引值得到索引集S；

(3) 將索引集與上一階段的支撐集進(jìn)行合并，得到候選集C=F∪S，再計(jì)算候選集與余量的內(nèi)積，并提取size個(gè)最大值，將其相對(duì)應(yīng)的原子加入到支撐集Fnew；

(5) 若‖rnew‖2≥‖r‖2，則進(jìn)行下一迭代階段，stage=stage+1，利用初始步長(zhǎng)更新支撐集容量size=stage×step，返回步驟(2)繼續(xù)迭代；否則更新支撐集和余量F=Fnew，r=rnew，此時(shí)迭代次數(shù)k=k+1，返回步驟(2)繼續(xù)迭代。

從上述算法中可以看到各個(gè)迭代階段步長(zhǎng)step的取值是一個(gè)常數(shù)，步長(zhǎng)的選擇關(guān)系到支撐集的容量，因此該算法的重構(gòu)精度與該步長(zhǎng)選擇有很大的關(guān)系。但是該算法的最大缺點(diǎn)就是不能后向刪除部分錯(cuò)誤原子，在原子的原子過程中很有可能會(huì)產(chǎn)生一些錯(cuò)誤的、冗余的原子，如果沒有辦法進(jìn)行二次修正，不僅會(huì)影響算法的時(shí)間，也會(huì)影響算法的精度。因此本文結(jié)合以上算法的優(yōu)點(diǎn)，針對(duì)不能后向刪除錯(cuò)誤原子提出了利用對(duì)數(shù)型自適應(yīng)變化步長(zhǎng)的前向后向算法來實(shí)現(xiàn)信號(hào)的重建。

3 步長(zhǎng)自適應(yīng)的前向后向匹配追蹤算法

SAMP算法雖然突破了在傳統(tǒng)匹配算法中對(duì)稀疏度的限制，但是通過相關(guān)實(shí)驗(yàn)表明，為了加快重構(gòu)速度，初始步長(zhǎng)step取較大值時(shí)，算法只需要很少的迭代次數(shù)，但是算法的效率就會(huì)很低。如果想保證算法的重構(gòu)精度，step取很小的值時(shí)，迭代次數(shù)就會(huì)大大增加。另外傳統(tǒng)的算法在選擇原子過程中支撐集的容量是不斷增加的，但是又無法刪除那些錯(cuò)誤的或者冗余的原子。因此選取合適的步長(zhǎng)和利用后向策略來對(duì)算法進(jìn)行修正是提高算法性能的關(guān)鍵。根據(jù)文獻(xiàn)[12]結(jié)合對(duì)數(shù)函數(shù)的性質(zhì)，在SAMP算法的框架下，提出了步長(zhǎng)自適應(yīng)變化的前向后向匹配算法。該算法首先進(jìn)行前向選擇匹配原子，然后進(jìn)行向后剔除部分錯(cuò)誤原子[20]，在確保重建精度的情況下，彌補(bǔ)了前向貪婪算法自身的缺點(diǎn)。接下來將從兩個(gè)方面對(duì)新算法進(jìn)行具體描述：步長(zhǎng)選擇和算法描述。

3.1 步長(zhǎng)選擇

根據(jù)相鄰迭代階段重建信號(hào)差的變化規(guī)律，設(shè)置兩個(gè)閾值ε1、ε2(ε1>ε2)，當(dāng)‖xt-xt-1‖>ε1時(shí)，選取一個(gè)較大的步長(zhǎng)，實(shí)現(xiàn)快速逼近；當(dāng)ε2<‖xt-xt-1‖<ε1時(shí)，選取較小的步長(zhǎng)，以實(shí)現(xiàn)逐漸逼近，此時(shí)步長(zhǎng)變?yōu)樯想A段步長(zhǎng)的一半；當(dāng)‖xt-xt-1‖<ε2時(shí)說明相鄰階段的能量差變化趨于平穩(wěn)，則停止迭代。

設(shè)步長(zhǎng)step為：

step(s)=alog2s+b

(4)

(5)

而當(dāng)采取緩慢逼近策略時(shí)就選取前一階段步長(zhǎng)的一半，即：

(6)

這里的步長(zhǎng)均向上取為正整數(shù)，c≥1的正整數(shù)，M、N分別表示觀測(cè)信號(hào)和待估信號(hào)的長(zhǎng)度。

3.2 算法描述

(1) 初始化稀疏度：余量r=y，支撐集F，支撐集長(zhǎng)度size=step，階段stage=1，迭代次數(shù)t=1，索引值集合S=?，候選集C=?；

(2) 計(jì)算相關(guān)系數(shù)，從中提取size個(gè)最大值對(duì)應(yīng)的索引值放入到集合S中；

(3) 合并索引集S與支撐集F，得到候選集C=F∪S，再計(jì)算候選集中索引值對(duì)應(yīng)的原子與余量的內(nèi)積，并提取size個(gè)最大值對(duì)應(yīng)的索引值得到新的支撐集F；

(4) 由最小二乘得到xt=argmin‖y-ΦFxt-1‖2，更新余量rt=y-Φtxt-1；

(5) 如果‖xt-xt-1‖>ε1則轉(zhuǎn)步驟(6)，否則轉(zhuǎn)步驟(8)；

(6) 如果‖rt‖≥‖rt-1‖則轉(zhuǎn)入步驟(7)，否則轉(zhuǎn)入步驟(9)；

(7) 進(jìn)入下一階段，stage=stage+1，利用式(5)求出新步長(zhǎng)step，擴(kuò)大支撐集大小size=size+step，t=t+1,返回步驟(2)；

(8) 如果‖xt-xt-1‖<ε2則停止迭代，否則轉(zhuǎn)入步驟(10)；

(9) 更新支撐集和余量返回步驟(2)繼續(xù)迭代；

(10) 進(jìn)入小步長(zhǎng)階段，stage=stage+1，利用式(6)求出新步長(zhǎng)step，擴(kuò)大支撐集大小size=size+step，t=t+1，返回步驟(2)；

(12) j=argmini∈Fq(F/i)；

(13) d-=q(F/j)-q(F)；

(14) d+=ε3；

(15) 如果d-d+；

4 實(shí)驗(yàn)與分析

實(shí)驗(yàn)一

為了驗(yàn)證本文算法的有效性，通過MATLAB處理平臺(tái)對(duì)該算法進(jìn)行了驗(yàn)證。實(shí)驗(yàn)一中采用長(zhǎng)度為N=256的一維高斯稀疏信號(hào)，觀測(cè)矩陣為部分快速傅里葉變換矩陣(FFT)。閾值設(shè)置為ε1=e-6，迭代停止條件閾值ε2=e-12，ε3=e-14。在實(shí)驗(yàn)一中比較了SAMP算法、MSAMP算法、LSAMP算法和AFBMP算法在不同采樣率下的重構(gòu)效果。實(shí)驗(yàn)中除本文算法以外其他算法的參數(shù)均按照原參考文獻(xiàn)中設(shè)置。實(shí)驗(yàn)表明該算法的重構(gòu)效果很好，相對(duì)誤差非常小，能夠很好地對(duì)原始信號(hào)進(jìn)行重建，在理論上說明了新算法的有效性。

圖2是SAMP、MSAMP算法、LSAMP算法與AFBMP算法在不同采樣率下重構(gòu)信號(hào)信噪比的比較。其中橫坐標(biāo)表示采樣率，縱坐標(biāo)為信噪比，實(shí)驗(yàn)結(jié)果顯示，該算法在前向階段通過采用對(duì)數(shù)型變化的步長(zhǎng)選取匹配原子，后向階段刪除錯(cuò)誤原子，使得該算法的性能得到了明顯的提升，AFBMP算法提高了對(duì)原始信號(hào)的重構(gòu)精度。

圖2 不同采樣率下重構(gòu)信號(hào)的信噪比

圖3比較了四種算法在不同采樣率下的重構(gòu)相對(duì)誤差。實(shí)驗(yàn)發(fā)現(xiàn)，SAMP算法在不同采樣率下的重構(gòu)誤差相對(duì)很高，而MSAMP算法和LSAMP算法是對(duì)原來算法的改進(jìn)在一定程度上均降低了重構(gòu)的相對(duì)誤差，而AFBMP算法結(jié)合了前面幾種算法的優(yōu)點(diǎn)，使得重構(gòu)相對(duì)誤差變得更低。我們發(fā)現(xiàn)，在相同采樣率下，AFBMP算法比其他三種算法的相對(duì)誤差低很多，因此該算法充分保證了對(duì)稀疏信號(hào)的重構(gòu)精度，同時(shí)也證明了該算法的有效性。

圖3 不同采樣率下幾種算法的相對(duì)誤差

實(shí)驗(yàn)二

為了更為充分地說明新算法在實(shí)際問題中的應(yīng)用，本文實(shí)驗(yàn)二對(duì)大小為256×256的圖像進(jìn)行實(shí)驗(yàn)。閾值設(shè)置為ε1=e-6，迭代停止條件閾值ε2=e-12，ε3=e-14。將本文算法和經(jīng)典SAMP算法、MSAMP算法對(duì)三組測(cè)試圖像進(jìn)行比較。圖4表明，改進(jìn)的SAMP算法重構(gòu)效果均好于經(jīng)典SAMP算法，而AFBMP算法的重構(gòu)效果也明顯好于其他算法，同時(shí)也證實(shí)了本文算法的實(shí)用價(jià)值。

圖4 二維圖像重建效果

表1是這三組測(cè)試圖進(jìn)行重構(gòu)的運(yùn)行時(shí)間，從上節(jié)的實(shí)驗(yàn)可知不同的采樣率下對(duì)算法性能的影響很大，因此采樣率為0.5的情況下重構(gòu)時(shí)間如表1所示。

表1 不同圖像不同算法的重構(gòu)時(shí)間

通過表1可以看出在相同的采樣率下，對(duì)于不同的圖像，各種算法的重構(gòu)時(shí)間也有所不同，而AFBMP算法的重構(gòu)時(shí)間略低于傳統(tǒng)的SAMP算法，進(jìn)一步說明了本文算法在運(yùn)行時(shí)間上有一定的優(yōu)勢(shì)。

5 結(jié) 語

本文深入研究了壓縮感知理論的經(jīng)典算法，在稀疏度未知的情況下結(jié)合SAMP算法，提出了一種對(duì)數(shù)型自適應(yīng)步長(zhǎng)的前向后向匹配算法。SAMP算法在迭代過程中固定步長(zhǎng)可能會(huì)導(dǎo)致過估計(jì)或者欠估計(jì)的問題，并且迭代結(jié)束之后不能刪除某些冗余原子和錯(cuò)誤原子。針對(duì)這兩個(gè)問題，在SAMP算法框架基礎(chǔ)上，前向迭代過程中采用改進(jìn)的對(duì)數(shù)型可變化的步長(zhǎng)選取匹配原子，而向后階段逐一測(cè)試支撐集中的每一個(gè)原子，刪除前向階段所產(chǎn)生的錯(cuò)誤原子，通過設(shè)置雙閾值來控制步長(zhǎng)選擇和停止準(zhǔn)則，分段逐步實(shí)現(xiàn)對(duì)稀疏度的逼近，最終實(shí)現(xiàn)信號(hào)的精確重構(gòu)。實(shí)驗(yàn)結(jié)果表明，新算法可以較好地實(shí)現(xiàn)未知稀疏度信號(hào)的重建，且重建性能明顯優(yōu)于SAMP算法。

[1] Candes E J,Wakin M B.An introduction to compressive sampling[J].IEEE Signal Proc Mag,2008,25(2):21-30.

[2] Donoho D L.Compressed sensing[J].IEEE Transactions on Information Theroy,2006,52(4):1289-1306.

[3] Chen S B,Donoho D L,Saunders M A.Atomic decomposition by basis pursuit[J].SiamJ.Sci.comput,2001,20(1):129-159.

[4] Mallat S,Zhang Z.Matching Pursuit with time-frequency dictionaries[J].IEEE Trans.Sig.Proc,1993,41(12):3397-3415.

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

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

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

[8] Dai W,Milenkovic O.Subspace pursuit for compressive sensing signal reconstruction[J].IEEE Transactions on information theory,2009,55(5):2230-2249.

[9] 郭永紅,楊毅彬.一種稀疏自適應(yīng)的正交互補(bǔ)匹配追蹤算法[J].計(jì)算機(jī)工程與應(yīng)用,2013,49(7):144-146.

[10] Donoho D L,Tsaig Y,Drori I,et al.Sparse solution of underdetermined linear equations by stage wise orthogonal matching pursuit[J].IEEE Transaction on Information Theroy,2012,58(2):1094-1121.

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

[12] 畢學(xué)霞,尚振宏.一種基于變步長(zhǎng)的稀疏度自適應(yīng)匹配追蹤算法[J].系統(tǒng)仿真學(xué)報(bào),2014,26(9):2116-2125.

[13] 吳延海,閆迪.基于改進(jìn)SP算法的壓縮感知圖像重構(gòu)[J].計(jì)算機(jī)應(yīng)用與軟件,2013,30(7):200-203,216.

[14] 廖斌,任美玲,徐俊剛.一種基于壓縮感知的盲數(shù)字水印算法[J].計(jì)算機(jī)應(yīng)用與軟件,2014,31(2):307-311.

[15] 季秀霞,卞曉曉.基于壓縮感知的合成孔徑雷達(dá)圖像目標(biāo)識(shí)別[J].計(jì)算機(jī)應(yīng)用與軟件,2013,30(12):120-123.

[16] 李然,干宗良,朱秀昌.基于最佳線性估計(jì)的快速壓縮感知圖像重建算法[J].電子與信息學(xué)報(bào),2012,34(12):3006-3012.

[17] Baraniukr R.Compressive sensing[J].IEEE Signal Processing Magazine,2007,24(4):118-126.

[18] Candes E,Romberg J,Tao T.Robust uncertainty principles:exact signal reconstruction from highly incomeplete frequency information[J].IEEE Transactions on Information Theory,2006,52(2):489-509.

[19] Do T T,Gan L,Nguyen N,et al.Sparisity adaptive matching pursuit algorithm for practical compressed sensing[J].IEEE Asilomar Conference on Signals,Systems and Computers,2008,10(7):581-587.

[20] Wei Tang,Zhenwei Shi.Regularized simultaneouss forward-backward greedy algorithm for sparse unmixing of hyperspectral data[J].IEEE Transactions on geoscience and remote sensing,2014,52(9):5271-5288.

ADAPTIVE STEPSIZE FORWARD-BACKWARD MATCHING PURSUIT ALGORITHM

Zhang Songjiang Zhou Mi Zhang Chuanlin

(School of Information and Science Technology,Jinan University,Guangzhou 510000,Guangdong,China)

Sparsity adaptive matching pursuit algorithm (SAMP) is a classical algorithm of signal reconstruction based on compressed sensing theory. Aiming at reconstructing signals with unknown sparsity, we presented an adaptive stepsize forward-backward matching pursuit algorithm (AFBMP). In the framework of SAMP, AFBMP selects matching atoms in its forward search process by using logarithmic adaptive changing steps, and then amends the mistakes caused in forward stage by backward strategy to delete part of the false atoms in support set, and finally realises accurate signal approaching. Experiments show that the AFBMP algorithm can reconstruct the signals with unknown sparsity more efficiently than SAMP algorithm.

Compressed sensing Reconstruction Forward-backward Sparsity adaptive Matching pursuit algorithm

2015-09-15。張松江，碩士，主研領(lǐng)域：圖像處理。周密，碩士。張傳林，教授。

TP391.9

A

10.3969/j.issn.1000-386x.2016.11.057