基于回溯正則化的前向搜索正交匹配追蹤算法研究

陶 亮， 劉海鵬*， 王 蒙， 董士謙

(1.昆明理工大學(xué) 信息工程與自動(dòng)化學(xué)院， 云南 昆明 650500;2.華能瀾滄江水電股份有限公司， 云南 昆明 650200)

隨著數(shù)字化的快速發(fā)展，我們正處在數(shù)字時(shí)代，身處這樣時(shí)代的重要特征就是所有的信號(hào)采集都必須有相應(yīng)的數(shù)字化軟硬件支撐。然而，隨著人們對(duì)信息量的大量需求，越來越需要更大的帶寬來攜帶信息，傳統(tǒng)的信號(hào)采樣受限于奈奎斯特定理，采樣速率低下，所以急需一種新的信號(hào)采樣方法，在這種情況下壓縮感知被提了出來。

壓縮感知是由Donoho[1](美國(guó)科學(xué)院院士)、Candes等[2]提出來的一種革命性信息獲取和處理方面的理論，帶來了全新數(shù)據(jù)處理方式。壓縮感知的主要原理是利用原始信號(hào)具有稀疏性或者在某個(gè)變換域中具有稀疏性，然后用一個(gè)觀測(cè)矩陣對(duì)其進(jìn)行觀測(cè)降維，得到一個(gè)維度遠(yuǎn)小于原始信號(hào)但信息量卻與原始信號(hào)基本等同的觀測(cè)值，最后再將原始信號(hào)從觀測(cè)值恢復(fù)出來的一個(gè)過程。有效的解決了奈奎斯特[3]采樣存在的不足，減少了存儲(chǔ)和計(jì)算資源。

目前關(guān)于壓縮感知的研究主要是如何精確的將原始信號(hào)從觀測(cè)值中恢復(fù)出來，即信號(hào)的重構(gòu)，在信號(hào)重構(gòu)各類方法中，貪婪算法由于其耗時(shí)短、過程簡(jiǎn)單而受到高度關(guān)注。例如匹配追蹤(Matching Pursuit，MP)、正交匹配追蹤[4](Orthogonal Matching Pursuit，OMP)、前向搜索正交匹配追蹤(Look Ahead Orthogonal Matching Pursuit，LAOMP)算法等等。

但是上述算法重構(gòu)精度仍然不夠精確，其中OMP算法是在MP算法基礎(chǔ)上改進(jìn)的，而LAOMP算法是在OMP算法上改進(jìn)的，LAOMP算法目前得到較為廣泛的應(yīng)用，但是LAOMP算法采用前向搜索策略(Look Ahead Residual,LAR)得到的原子不一定就是最優(yōu)的原子，即重構(gòu)精度存在不足。因此，本文在LAOMP算法的基礎(chǔ)上加以改進(jìn)，提出了一種回溯正則化前向搜索正交匹配追蹤(Backtracking Regularized Look Ahead Orthogonal Matching Pursuit，BRLAOMP)算法。該算法在LAOMP算法選擇原子的基礎(chǔ)上，又加入了回溯策略和正則化來挑選原子，使選擇出來用以重構(gòu)的原子能達(dá)到最佳，所以該算法的重構(gòu)精度與同類算法相比明顯得到提高。

1 算法描述

1.1 LAOMP算法

OMP算法作為最早的貪婪迭代算法之一，其思想對(duì)之后的各種貪婪算法有著極其重要的意義，它沿用了MP算法中的原子選擇準(zhǔn)則。OMP算法以貪婪的方式選擇原子(通常將感知矩陣中的每一列稱為原子)，在每次迭代中，找出感知矩陣中的每一列向量與殘差，相乘得到最大內(nèi)積值對(duì)應(yīng)的原子，并在其中找到該原子所對(duì)應(yīng)的索引值進(jìn)行存儲(chǔ)；然后更新原子集，更新殘差；最后判斷是否滿足迭代停止條件，進(jìn)而輸出估計(jì)信號(hào)。但是OMP算法在每次進(jìn)行原子選擇的時(shí)候選擇的原子未必是最優(yōu)的，而且每次迭代中僅僅選擇一個(gè)原子來更新，也將消耗很多時(shí)間。于是Saket Chatterjee等[5-7]在OMP算法的基礎(chǔ)上提出了LAOMP算法。

LAOMP算法作為一種應(yīng)用較為普遍的壓縮感知重構(gòu)算法，與OMP算法相比，主要采用了前向搜索策略。該算法在選擇原子的過程中，通過判斷所選原子對(duì)未來迭代的影響來選擇最佳的原子。該算法的原理是首先選擇出若干最大內(nèi)積所對(duì)應(yīng)的原子，并將這個(gè)原子所對(duì)應(yīng)的索引存儲(chǔ)起來，然后逐次迭代，比較這些原子對(duì)最終殘差的影響，最終選擇殘差中二范數(shù)最小的一個(gè)原子所對(duì)應(yīng)的索引加入到支撐集中，然后更新原子集，更新殘差，判斷是否滿足終止條件，輸出近似信號(hào)，以達(dá)到對(duì)原信號(hào)的重構(gòu)。

LAOMP算法的核心是LAR算法，具體描述如下：

輸入：傳感矩陣AM×N，觀測(cè)向量YM×N，稀疏度k，先前支撐集Ipre，新選擇的原子索引t。

迭代過程：

1)迭代次數(shù)k=1∶L；

3)更新支撐集Ik=Ipre∪tk；

5)更新殘差rk=Y-AIkθIk；

6)判斷是否滿足迭代停止條件‖rk‖2>‖rk-1‖，若滿足，則停止迭代，否則，重復(fù)步驟1—6。

輸出：rk=Y-AIkθIk。

對(duì)于給定的稀疏度k，候選原子索引集Ipre，原子索引t，LAR算法最后得到K個(gè)元素候選集并返回最后的殘差，LAR算法可以定義LAR函數(shù)如下：

r=LAR(Y,A,k,Ipre,t)。

(1)

1.2 BRLAOMP算法

LAOMP算法雖然相對(duì)于OMP算法能更好地選出迭代需要的原子，但是，OMP算法、LAOMP算法等，在每一次迭代的時(shí)候都是尋找傳感矩陣中的每一列與殘差相乘的最大內(nèi)積值所對(duì)應(yīng)的原子，稱之為最佳原子，但是由于數(shù)據(jù)的隨機(jī)不確定性以及運(yùn)算中可能出現(xiàn)的復(fù)數(shù)，導(dǎo)致所選擇的最大內(nèi)積值未必就是最大的值，所以最終通過前向搜索策略(LAR)得出的原子不一定就是最優(yōu)的原子，鑒于此，本文提出了BRLAOMP算法，該算法在LAOMP算法的基礎(chǔ)上增強(qiáng)了挑選原子的力度。BRLAOMP算法首先通過殘差相乘的方式選擇內(nèi)積最大的前2L個(gè)原子，接著用最小二乘法求出這些原子的稀疏表示系數(shù)估計(jì)θ，去除L個(gè)系數(shù)估計(jì)θ數(shù)值較小的原子，即用回退篩選[8-9]的思想選擇保留L系數(shù)較大的原子。然后對(duì)這L個(gè)原子進(jìn)行正則化[10-11]，選出能量最大的原子集，最后將這些能量最大的原子加入到LAR中，選擇殘差性能最佳的原子，更新支撐集，更新殘差，直至滿足終止條件并輸出結(jié)果。

BRLAOMP算法的核心是由回溯策略、正則化和LAR算法3個(gè)部分組成。LAR算法已經(jīng)介紹了，接下來介紹回溯策略和正則化算法。

1.2.1 回溯策略

回溯策略也就是回退篩選，其基本思想是從一條路往前走，能進(jìn)則進(jìn)，不能進(jìn)就退回來。本文對(duì)它的基本操作是先選出2L個(gè)內(nèi)積值最大的原子，然后直接用最小二乘法求出每個(gè)原子稀疏表示系數(shù)估計(jì)θ，對(duì)這2L個(gè)系數(shù)進(jìn)行降序排列，選出前L個(gè)系數(shù)最大的原子對(duì)應(yīng)的索引。就可以把一些內(nèi)積值較大卻并非是最佳原子的原子去掉。這樣經(jīng)過回退篩選得到的原子擁有更好的重構(gòu)精度。具體操作如下：

1)初始余量r0=Y，索引值集合Ω=?，J=?；支撐集P=?；

2)用公式u={uj=||,j=1,2,…,N}余量與感知矩陣的內(nèi)積取絕對(duì)值，并從中尋找2L個(gè)最大值的原子對(duì)應(yīng)的索引值存入J中；

3)令Ω=Ω∩J，用θ=(ΩTΩ)-1ΩTY求得信號(hào)逼近系數(shù)θ，取前L個(gè)最大系數(shù)的原子放入支撐集P中，等待下一步操作。

1.2.2 正則化算法

正則化是從支撐集P中尋找符合|u(i)|<2|u(j)|的原子，其中u指的是各原子與殘差的內(nèi)積值，正則化過程能夠在一個(gè)原子集中篩選出能量較大的原子，是一種簡(jiǎn)單有效的原子篩選方法，這樣篩選出來的原子一定程度上提高了重構(gòu)精度。正則化算法過程如下：

輸入：回退篩選得到的支撐集P。

初始化：初始化最大能量值Emax=0,自變量t=1。

迭代過程：

1)將支撐集P中L個(gè)原子對(duì)應(yīng)的索引值存入J中；

2)計(jì)算P中的原子與余量的內(nèi)積值存入Jval中；

3)外部循環(huán)次數(shù)k=1∶L

①存儲(chǔ)本次尋找的最佳索引值Jpos(t)=J(k)；

②存儲(chǔ)本次尋找的能量最大值En=Jval(k)2；

③內(nèi)部循環(huán)次數(shù)m=(k+1)∶L

a)尋找符合條件|u(i)|<2|u(j)|的內(nèi)積值Jval(k)<2×Jval(m)；

b)自變量更新t=t+1；

c)索引值Jpos(t)=J(m)；

d)能量更新En=En+Jval(k)2；

如果不滿足條件，結(jié)束內(nèi)部循環(huán)。

5)如果最大能量值En>Emax；

6)更新索引值Jt=Jpos(1∶t)；

7)更新能量值Emax=En。

輸出：索引值pos=Jt，能量值val=Emax。

定義正則化過程公式：

[Val,pos]=Re(P,L)。

(2)

1.2.3BRLAOMP算法具體步驟

輸入：傳感矩陣AM×N，觀測(cè)矩陣YM×N。

初始化：近似系數(shù)θ=0，初始?xì)埐顁0=Y，支撐集I=?,pos_theta=[]；索引值集合Ω=?，J=?；支撐集P=?。

迭代過程：

1)外部循環(huán)次數(shù)k=1∶M；

2)計(jì)算A的各列與殘差的內(nèi)積u=ATrk-1；

3)對(duì)內(nèi)積做降序排列，取前2L個(gè)內(nèi)積最大的原子對(duì)應(yīng)的索引放入J中；

4)令Ω=Ω∪J，θ=(ΩTΩ)-1ΩTY求得信號(hào)逼近系數(shù)θ，對(duì)θ降序排列，取前L個(gè)最大系數(shù)的原子放入支撐集P中；

5)正則化[Val,pos]=Re(P,L)；

6)內(nèi)部循環(huán)次數(shù)l=1∶L；

a)由LAR得到殘差值r=LAR(Y,A,k,Ipye,t)；

b)存儲(chǔ)殘差nl=‖r‖2；

c)選擇殘差值的二范數(shù)最小的原子對(duì)應(yīng)的索引值ik；

7)更新支撐集Ik=Ik-1∪ik；

9)存儲(chǔ)支撐集pos_theta=Ik；

10)判斷是否滿足迭代終止條件‖rk‖2>‖rk-1‖。

2 仿真結(jié)果和分析

驗(yàn)證本文提出的回溯正則化前向搜索正交匹配追蹤(BRLAOMP)算法實(shí)現(xiàn)信號(hào)的高精度重構(gòu)，以下仿真結(jié)果是在MATLAB R2014a環(huán)境下進(jìn)行。

2.1 一維信號(hào)重構(gòu)實(shí)驗(yàn)

2.1.1 一維信號(hào)高精度重構(gòu)

先用一維重構(gòu)實(shí)驗(yàn)來測(cè)試本算法是否可以精確地將原始信號(hào)從觀測(cè)值中恢復(fù)出來，實(shí)驗(yàn)結(jié)果如圖1所示，其中橫坐標(biāo)表示信號(hào)的維數(shù)，圖中有12條黑線表示原始信號(hào)，12個(gè)黑點(diǎn)表示恢復(fù)出來的信號(hào)，12是設(shè)置的稀疏度，從圖中可以看出黑點(diǎn)與黑線高度重合，表示信號(hào)被完整地恢復(fù)出來。

2.1.2 BRLAOMP算法穩(wěn)定性驗(yàn)證

測(cè)試本算法在不同稀疏度下的恢復(fù)情況，當(dāng)恢復(fù)殘差小于10-16時(shí)認(rèn)定重構(gòu)成功，計(jì)算出不同稀疏度一維信號(hào)重構(gòu)的概率，實(shí)驗(yàn)結(jié)果如圖2所示，其中橫坐標(biāo)表示測(cè)量數(shù)，縱坐標(biāo)表示重構(gòu)率。重構(gòu)率達(dá)到100表示恢復(fù)成功，從圖中可以看出，測(cè)量數(shù)在150左右時(shí)，所有不同稀疏度的信號(hào)全部成功恢復(fù)。

圖1 一維信號(hào)的重構(gòu)實(shí)驗(yàn) 圖2 一維信號(hào)準(zhǔn)確重構(gòu)概率

2.2 二維信號(hào)重構(gòu)實(shí)驗(yàn)

2.2.1 3種算法重構(gòu)實(shí)驗(yàn)對(duì)比

圖3 在高斯信號(hào)下的ERP對(duì)比圖

對(duì)OMP算法、LAOMP算法、BRLAOMP算法進(jìn)行精確重構(gòu)率(ERP)對(duì)比實(shí)驗(yàn)，在不考慮噪聲的情況下，稀疏基矩陣選擇小波變換正交基，觀測(cè)矩陣[12-18]選擇高斯隨機(jī)矩陣[19-20]。仿真參數(shù)設(shè)置如下：令原信號(hào)X分別為長(zhǎng)度700的高斯隨機(jī)信號(hào)和長(zhǎng)度為1000的二值信號(hào)，稀疏度K設(shè)置為25。原信號(hào)為高斯隨機(jī)信號(hào)，壓縮比區(qū)段設(shè)置為[0.13,0.2]，共8個(gè)點(diǎn)，測(cè)量次數(shù)為90次。結(jié)果如圖3所示，可以看出隨著壓縮比的增大，3種算法的ERP均增大，但本算法的增大效果更明顯。其中在壓縮比相同的情況下，本算法ERP要比另外兩種算法效果好，能在較低的壓縮比下也能達(dá)到滿意的效果，當(dāng)壓縮比達(dá)到0.19時(shí)重構(gòu)率(ERP)就趨近1，即趨近于完全重構(gòu)。而另外兩種算法的重構(gòu)率分別為0.8、0.9。由此可見本算法的優(yōu)越性。

2.2.2 二維圖像重構(gòu)實(shí)驗(yàn)比較

以圖像的峰值信噪比(PSNR)和相對(duì)誤差(RE)作為圖像恢復(fù)質(zhì)量的評(píng)判依據(jù)，壓縮比M/N分別選取0.3、0.5、0.7。其中稀疏基矩陣采用小波變換矩陣，測(cè)量矩陣采用高斯隨機(jī)矩陣。仿真結(jié)果如圖4、圖5、圖6所示，可以看出，對(duì)于同一幅二維圖片，在壓縮比分別為0.3、0.5、0.7中，壓縮比為0.3的圖片最模糊，而壓縮比為0.7最為清晰，壓縮比為0.5的清晰度介于二者之間，但在壓縮比相同的情況下，本文提出的BRLAOMP算法重構(gòu)的圖像均比另外兩種算法重構(gòu)得到的圖片清晰。

圖4 壓縮比為0.3的二維圖像重構(gòu)實(shí)驗(yàn)

圖5 壓縮比為0.5的二維圖像重構(gòu)實(shí)驗(yàn)

圖6 壓縮比為0.7的二維圖像重構(gòu)實(shí)驗(yàn)

2.2.3 二維圖像重構(gòu)質(zhì)量比較

當(dāng)壓縮比相同時(shí)，BRLAOMP算法的峰值信噪比(PSNR)最大，而相對(duì)誤差(RE)最小，見表1。說明BRLAOMP算法重構(gòu)質(zhì)量?jī)?yōu)于另外兩種算法，且隨著壓縮比的增大，各算法的PSNR均增大，而RE均減小，但BRLAOMP算法效果最為明顯，其PSNR均大于其他算法，RE均小于其他算法，可見該算法的優(yōu)越性。

表1 壓縮比為0.3、0.5、0.7時(shí)二維圖像重構(gòu)質(zhì)量比較

3 結(jié)論及討論

本文在LAOMP算法的基礎(chǔ)上引入了回溯思想和正則化算法，強(qiáng)化了對(duì)原子的選擇，提出了一種改進(jìn)的前向搜索正交匹配追蹤(BRLAOMP)算法。經(jīng)過仿真對(duì)比，發(fā)現(xiàn)該算法的重構(gòu)質(zhì)量明顯優(yōu)于LAOMP算法。但在運(yùn)行時(shí)間上，BRLAOMP算法比較長(zhǎng)。如在一維信號(hào)重構(gòu)實(shí)驗(yàn)中，OMP算法重構(gòu)時(shí)間約為0.06 s，LAOMP算法的重構(gòu)時(shí)間為0.19 s，BRLAOMP算法的重構(gòu)時(shí)間約為0.29 s，這是由于本算法用了3種方式來篩選原子，故在重構(gòu)時(shí)間上表現(xiàn)出劣勢(shì)，后續(xù)將針對(duì)算法運(yùn)行時(shí)間方面做進(jìn)一步研究。