唐川雁，史姣姣

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

0 引 言

壓縮感知（Compressed Sensing，CS）[1]理論與奈奎斯特定理相比，最大的優(yōu)勢(shì)是減少了采樣數(shù)據(jù)，同時(shí)完成采樣和壓縮，有效降低了資源消耗與信號(hào)處理成本。壓縮感知已廣泛應(yīng)用于多個(gè)領(lǐng)域，如信道估計(jì)[2]、人臉識(shí)別[3]、圖像處理[4]、醫(yī)學(xué)應(yīng)用[5]等。

重構(gòu)算法作為CS的重要部分，解決的是從低維測(cè)量值中恢復(fù)出原始高維信號(hào)的問(wèn)題。重構(gòu)算法大致可分為三類(lèi)：凸優(yōu)化算法、貪婪迭代算法和組合優(yōu)化算法。其中貪婪類(lèi)算法計(jì)算復(fù)雜度較低，算法結(jié)構(gòu)簡(jiǎn)單易于實(shí)現(xiàn)，并且重構(gòu)效果好，是在實(shí)際中應(yīng)用較多的一類(lèi)算法，如正交匹配追蹤（Orthogonal Matching Pursuit，OMP）算法[6]、壓縮采樣匹配追蹤（Compressive Sampling Matching Pursuit，CoSaMP）算 法[7]和 子 空 間 追 蹤（Subspace Pursuit，SP）算法[8]等。雖然這些算法都能實(shí)現(xiàn)原始信號(hào)的準(zhǔn)確重構(gòu)，但前提條件是需要預(yù)知信號(hào)稀疏度。事實(shí)上，信號(hào)稀疏度通常是未知的，這使得上述算法的應(yīng)用范圍比較受限。為解決未知稀疏度類(lèi)信號(hào)的重構(gòu)問(wèn)題，Thong T D，Gan Lu等學(xué)者[9]提出了稀疏度自適應(yīng)匹配追蹤（Sparsity Adaptive Matching Pursuit，SAMP）算法。SAMP算法不需輸入稀疏度，在實(shí)際應(yīng)用中有巨大優(yōu)勢(shì)，因此近年來(lái)眾多學(xué)者對(duì)SAMP算法進(jìn)行研究和改進(jìn)，如文獻(xiàn)[10]結(jié)合原子匹配測(cè)試、正則化和回溯思想及變步長(zhǎng)選擇原子的方法，在不需要預(yù)知稀疏度的情況下，能夠準(zhǔn)確重構(gòu)原始信號(hào)，且與同類(lèi)算法相比迭代次數(shù)和重構(gòu)時(shí)間更少，性能更優(yōu)，不足的是該算法稀疏度估計(jì)值與真實(shí)值相比在大稀疏度時(shí)誤差較大。文獻(xiàn)[11]提出一種稀疏度估計(jì)方法來(lái)避免稀疏度的過(guò)估計(jì)，以及在不同階段根據(jù)測(cè)量值與估計(jì)信號(hào)的能量比值調(diào)整步長(zhǎng)，實(shí)現(xiàn)了未知稀疏度類(lèi)信號(hào)的精確重構(gòu)，但其稀疏度估計(jì)方法在約束等距常數(shù)增大時(shí)誤差也增大。Qiu S等人[12]提出基于SAMP的步長(zhǎng)優(yōu)化算法，該算法針對(duì)SAMP算法隨迭代次數(shù)的增加步長(zhǎng)也只能增加的缺點(diǎn)，根據(jù)當(dāng)前殘差與上一次迭代殘差的差值改變步長(zhǎng)，若該差值滿(mǎn)足設(shè)定的條件則計(jì)數(shù)，當(dāng)達(dá)到3次則減少步長(zhǎng)，否則繼續(xù)計(jì)數(shù)直到滿(mǎn)足迭代停止條件，該算法雖然能減少重構(gòu)時(shí)間，但在重構(gòu)成功率上改善并不明顯。

研究發(fā)現(xiàn)現(xiàn)有的SAMP改進(jìn)算法重構(gòu)成功率還有提高空間，因此從原子選取方式出發(fā)，提出了變比例的稀疏度自適應(yīng)匹配追蹤（Sparsity Adaptive Matching Pursuit with Variable Proportion，VP-SAMP）算法。該算法對(duì)SAMP算法的原子預(yù)選方法進(jìn)行改進(jìn)，以?xún)?nèi)積累加比例準(zhǔn)則篩選原子，并采用變比例策略在大稀疏度時(shí)提高重構(gòu)成功率。

1 壓縮感知理論

CS理論表明，若信號(hào)是稀疏的或可壓縮的，則可通過(guò)測(cè)量矩陣與該信號(hào)相乘得到少量觀(guān)測(cè)值，實(shí)現(xiàn)信號(hào)的降維處理，最后再利用相關(guān)算法求解最優(yōu)化的非線(xiàn)性問(wèn)題從樣點(diǎn)中恢復(fù)原始信號(hào)。

設(shè)x是RN空間中一個(gè)長(zhǎng)度為N的離散信號(hào)，可看作是一個(gè)列向量，現(xiàn)假設(shè)有一組維度同為N×1的基函數(shù)ψi(i=1,2,…,N)，則可用ψi的線(xiàn)性組合來(lái)表示x，令Ψ=[ψ1,ψ2,…,ψN]，則x可以表示為：

式（1）中Ψ為N×N的正交基矩陣，稱(chēng)為變換基（稀疏基），α稱(chēng)為加權(quán)系數(shù)向量，且可表示為α=Ψ-1x，因此加權(quán)系數(shù)在Ψ域（即以Ψ為基的變換域，簡(jiǎn)稱(chēng)Ψ域）的表示等同于信號(hào)在時(shí)域的表示，是同一個(gè)信號(hào)的等價(jià)表示。如果α中僅存在K(K<

在信號(hào)經(jīng)過(guò)稀疏表示后，即可設(shè)計(jì)一個(gè)測(cè)量矩陣Φ(M×N,M

式（2）中，D=Φ·Ψ為M×N維的傳感矩陣。由于N遠(yuǎn)大于M，所以求解式（2）就是一個(gè)NP難題[13]。然而式（2）中α只有K個(gè)非零值，滿(mǎn)足K

2 變比例的稀疏度自適應(yīng)匹配追蹤算法

SAMP算法在稀疏度未知的情況下也能重構(gòu)原始信號(hào)，是貪婪類(lèi)算法的重要突破。SAMP的基本思想是：在迭代開(kāi)始時(shí)，初始化步長(zhǎng)為一個(gè)較小的值，采用分階段思想逐步擴(kuò)大步長(zhǎng)，隨著迭代次數(shù)的增加，當(dāng)殘差的值比上一次殘差為非遞減時(shí)增加步長(zhǎng)，逐步向信號(hào)的真實(shí)稀疏度逼近。SAMP在原子預(yù)選時(shí)，每次選擇當(dāng)前步長(zhǎng)大小的原子個(gè)數(shù)。隨著階段的增加步長(zhǎng)也會(huì)變大，當(dāng)稀疏度較大時(shí)，在迭代后期每次從內(nèi)積中選取的原子數(shù)很多，可能導(dǎo)致大量的誤選，使得重構(gòu)成功率下降較多甚至重構(gòu)失敗。

針對(duì)上述SAMP原子選取的問(wèn)題，提出了變比例的稀疏度自適應(yīng)匹配追蹤（VP-SAMP）算法。該算法預(yù)選集選取的原子個(gè)數(shù)不再依賴(lài)于當(dāng)前步長(zhǎng)，而是通過(guò)一個(gè)變化閾值β進(jìn)行控制。在每次迭代時(shí)，將占內(nèi)積總和比例較大的部分對(duì)應(yīng)原子選出，這個(gè)比例就是閾值β，同時(shí)當(dāng)匹配追蹤的稀疏度增大時(shí)，β也進(jìn)行增大。預(yù)選集選取原子的個(gè)數(shù)由當(dāng)前內(nèi)積數(shù)值的分布情況確定，內(nèi)積中存在較大的值時(shí)，選取的原子個(gè)數(shù)較少；內(nèi)積中的值分布較平均時(shí)，選取的原子個(gè)數(shù)變多，所以β不變時(shí)，每次選取的原子個(gè)數(shù)也是自適應(yīng)變化的。下面通過(guò)內(nèi)積累加比例選取準(zhǔn)則和變比例策略?xún)煞矫鎭?lái)對(duì)VP-SAMP算法進(jìn)行描述。

2.1 內(nèi)積累加比例選取準(zhǔn)則

對(duì)殘差與測(cè)量矩陣的內(nèi)積的絕對(duì)值分布進(jìn)行了研究，發(fā)現(xiàn)內(nèi)積中只有少數(shù)值比較大，這些值包含了內(nèi)積中較大比例的能量，使用這些原子便能夠大概率重構(gòu)信號(hào)。輸入信號(hào)為長(zhǎng)度N=256的隨機(jī)信號(hào)，其稀疏度K=20，測(cè)量矩陣為64×256的高斯矩陣，以上述實(shí)驗(yàn)條件進(jìn)行重構(gòu)中的內(nèi)積計(jì)算，得到第二次迭代時(shí)內(nèi)積的絕對(duì)值大小分布情況如圖1所示。

圖1 信號(hào)測(cè)量降序排列結(jié)果

由圖1可見(jiàn)，將第二次迭代得到的測(cè)量矩陣與殘差的內(nèi)積的絕對(duì)值降序排列后，只有小部分的值較大，其余的大部分值較小。根據(jù)降序排列得到的結(jié)果，對(duì)前n個(gè)值進(jìn)行累加，當(dāng)累加的和占內(nèi)積的總和比例超過(guò)β時(shí)，由這n個(gè)原子組成該次迭代預(yù)選集中的原子。如式（4）所示。

式（4）中，u為當(dāng)前迭代計(jì)算的內(nèi)積，rt-1表示第t次迭代的殘差，Φ是測(cè)量矩陣，sort(·)表示按照從大到小的順序進(jìn)行排序，sum·)表示求和。通過(guò)式（4）即可進(jìn)行初次原子篩選，稱(chēng)之為VP-SAMP算法的內(nèi)積累加比例選取準(zhǔn)則。利用該原子選取準(zhǔn)則選擇的原子數(shù)根據(jù)內(nèi)積值的大小分布自適應(yīng)變化，不會(huì)因?yàn)椴介L(zhǎng)隨階段數(shù)的增加而增加導(dǎo)致預(yù)選時(shí)選擇的原子數(shù)越來(lái)越多，從而導(dǎo)致預(yù)選浪費(fèi)甚至原子誤選，降低信號(hào)重構(gòu)成功率。

2.2 變比例策略

基于內(nèi)積累加比例準(zhǔn)則的閾值法篩選原子時(shí)，閾值β取值是固定的。在重構(gòu)某個(gè)原始信號(hào)的過(guò)程中，每次迭代時(shí)將占內(nèi)積總和固定比例的值較大的部分對(duì)應(yīng)原子選出，雖然每次選取的原子個(gè)數(shù)是自適應(yīng)變化的，但在迭代開(kāi)始階段，估計(jì)稀疏度與真實(shí)的稀疏度相差較大，因此應(yīng)在開(kāi)始階段選擇較少的原子，可以減少回溯的時(shí)間；在迭代后期，支撐集中的原子越來(lái)越多，接近真實(shí)支撐集大小，此時(shí)應(yīng)在時(shí)間允許的范圍內(nèi)，增加閾值β，使得滿(mǎn)足式（4）的原子更多，從而可以選出更多的原子參與重構(gòu)，以此提高大稀疏度條件下的重構(gòu)成功率。在迭代開(kāi)始前，設(shè)置閾值β的初始值和最大值分別為β0和βmax，當(dāng)滿(mǎn)足設(shè)定的閾值改變條件時(shí)，按照式（5）增加β：

通過(guò)上述閾值調(diào)整策略，選取原子的方式更加合理，在前期迭代階段，估計(jì)稀疏度較小時(shí)可以減少重構(gòu)時(shí)間，在稀疏度較大時(shí)可以提高重構(gòu)成功率，可在不同稀疏度下達(dá)到重構(gòu)成功率和重構(gòu)時(shí)間兩種性能的平衡。

2.3 VP-SAMP算法步驟

VP-SAMP算法的主要思想是：設(shè)置閾值β的初始值和最大值，通過(guò)基于內(nèi)積累加比例的閾值法選取預(yù)選集，同時(shí)在迭代過(guò)程中，根據(jù)設(shè)定的閾值改變條件增加閾值，以此提高大稀疏度條件下的信號(hào)重構(gòu)成功率性能。VP-SAMP算法的具體步驟如下。

輸入：測(cè)量矩陣Φ，測(cè)量值y，初始步長(zhǎng)s；

初始化：殘差r0=y，支撐集初始支撐集大小L=s，迭代次數(shù)t=1；

（1）計(jì)算u=〈rt-1,Φ〉，選擇滿(mǎn)足式（4）的所有原子，并將對(duì)應(yīng)的索引值放入預(yù)選集J1中；

（2）得到候選集：C=F∪J1；

（5）如果||r||2≤10-6，則停止迭代，得到最后的結(jié)果否則轉(zhuǎn)步驟（6）；

（6）如果||r||2≥||rt-1||2，更新支撐集長(zhǎng)度為L(zhǎng)=L+s，若β<βmax，則β=β+β0，轉(zhuǎn)步驟（1）；否則更新支撐集Ft=F，更新殘差rt=r，更新迭代次數(shù)t=t+1轉(zhuǎn)步驟（1）進(jìn)入下一階段；

輸出：信號(hào)的稀疏近似x^。

3 實(shí)驗(yàn)結(jié)果

以下實(shí)驗(yàn)均在Windows 10系統(tǒng)，MATLAB R2014a環(huán)境中進(jìn)行的。實(shí)驗(yàn)時(shí)針對(duì)單種算法單個(gè)參數(shù)重復(fù)實(shí)驗(yàn)500次，當(dāng)重構(gòu)誤差小于10-6即認(rèn)為重構(gòu)成功，統(tǒng)計(jì)其中的重構(gòu)成功次數(shù)即為重構(gòu)成功率，統(tǒng)計(jì)其中重構(gòu)成功的平均誤差即為重構(gòu)誤差，統(tǒng)計(jì)其中重構(gòu)成功的平均時(shí)間即為重構(gòu)時(shí)間。

3.1 內(nèi)積累加比例選取準(zhǔn)則的有效性

式（4）中參數(shù)β的取值范圍是[0,1]，為了研究β取值對(duì)性能的影響，先設(shè)定β0=0，βmax=1進(jìn)行不同β下的實(shí)驗(yàn)分析，得到VP-SAMP算法中β對(duì)性能影響實(shí)驗(yàn)結(jié)果。實(shí)驗(yàn)時(shí)選擇高斯信號(hào)作為原始信號(hào)，長(zhǎng)度為N=256，測(cè)量矩陣為128×256的高斯隨機(jī)矩陣，稀疏度K取值為42～60，每隔3取一次值，步長(zhǎng)s取值為3。β取值為0.1～0.6，每隔0.1取一次值，得出不同β值下重構(gòu)成功率和重構(gòu)時(shí)間隨稀疏度的變化情況，如圖2所示。

圖2 不同β值對(duì)VP-SAMP算法性能影響

由圖2可知，在同一稀疏度下，β值越大，重構(gòu)成功率越高，但所用的重構(gòu)時(shí)間也越多。當(dāng)稀疏度較小時(shí)，基于小β值進(jìn)行原子預(yù)選便能得到較好的重構(gòu)效果，同時(shí)重構(gòu)時(shí)間也較少；當(dāng)稀疏度較大時(shí)，需要更多的原子參與重構(gòu)，在時(shí)間允許的情況下，應(yīng)選取大的β值進(jìn)行原子預(yù)選才能得到較好的重構(gòu)效果。這表明理論分析與實(shí)驗(yàn)結(jié)果相一致。按照?qǐng)D2的實(shí)驗(yàn)結(jié)果，綜合考慮重構(gòu)成功率和重構(gòu)時(shí)間兩方面的性能，選定VP-SAMP算法中β0=0.1，βmax=0.6，按照此參數(shù)進(jìn)行VP-SAMP與SAMP算法的性能分析實(shí)驗(yàn)。

3.2 VP-SAMP與SAMP重構(gòu)效果比較

實(shí)驗(yàn)比較SAMP和所提VP-SAMP算法的性能，分別從重構(gòu)成功率、重構(gòu)誤差和重構(gòu)時(shí)間三方面進(jìn)行對(duì)比。實(shí)驗(yàn)時(shí)兩種算法步長(zhǎng)s取值均為2，3，4，可得不同步長(zhǎng)下的VP-SAMP算法和SAMP算法的重構(gòu)成功率、重構(gòu)誤差和重構(gòu)時(shí)間隨稀疏度的變化曲線(xiàn)如圖3所示。

圖3 VP-SAMP算法與SAMP性能對(duì)比

由圖3可得，VP-SAMP算法與SAMP算法相比，重構(gòu)成功率明顯更高。在稀疏度超過(guò)65之后，SAMP算法的成功率三種步長(zhǎng)下均為0，因此在重構(gòu)誤差和重構(gòu)時(shí)間圖中，SAMP算法在稀疏度超過(guò)65之后沒(méi)有數(shù)據(jù)；而VP-SAMP則成功率在20%到70%之間，并且重構(gòu)誤差和重構(gòu)時(shí)間較更小稀疏度情況下沒(méi)有劇烈增加，依然保持在同個(gè)數(shù)量級(jí)水平，充分說(shuō)明了VP-SAMP算法在大稀疏度下的重構(gòu)成功率優(yōu)于SAMP算法?？紤]到稀疏度大于65之后SAMP算法重構(gòu)成功率為0，因此只統(tǒng)計(jì)稀疏度為56到62之間的兩種算法各步長(zhǎng)下的平均重構(gòu)成功率統(tǒng)計(jì)如表1所示。

表1 稀疏度為56到62之間的平均重構(gòu)成功率

從表1明顯可見(jiàn)VP-SAMP算法的平均重構(gòu)成功率高于SAMP算法，且圖3表明稀疏度繼續(xù)增加時(shí)，SAMP算法成功率迅速降低為0，而VP-SAMP下降速度更慢，依然保持一定成功率。

重構(gòu)誤差方面，當(dāng)K<65時(shí)兩種算法基本相當(dāng)，當(dāng)K＞65時(shí)，SAMP成功率為零，重構(gòu)誤差非常大，VP-SAMP算法雖然重構(gòu)誤差增大，但是依然保持在10-13數(shù)量級(jí)。因此認(rèn)為兩種算法在重構(gòu)誤差方面性能基本一致。

從表1可見(jiàn)SAMP算法s=2時(shí)的重構(gòu)成功率低于VP-SAMP算法在s=4時(shí)的重構(gòu)成功率，而結(jié)合重構(gòu)時(shí)間性能來(lái)看，同等初始步長(zhǎng)下，VP-SAMP算法重構(gòu)時(shí)間高于SAMP算法，但是從圖3的重構(gòu)時(shí)間曲線(xiàn)中可以看出，VP-SAMP算法s=3時(shí)的重構(gòu)時(shí)間和SAMP算法s=2時(shí)的重構(gòu)時(shí)間基本一致，因此可以結(jié)合表1和圖3比較兩種算法在時(shí)間一致情況下的重構(gòu)成功率。從表1可知，SAMP算法s=2時(shí)的重構(gòu)成功率為84.88%，而VP-SAMP算法s=3時(shí)的重構(gòu)成功率為90.72%，提升5.84%。說(shuō)明在重構(gòu)時(shí)間和重構(gòu)誤差一致的情況下，VP-SAMP算法有著比SAMP更高的重構(gòu)成功率，充分說(shuō)明了本文所提VP-SAMP算法在大稀疏度下的重構(gòu)成功率方面具有較大性能提升。

4 結(jié) 語(yǔ)

針對(duì)SAMP算法每次選擇當(dāng)前步長(zhǎng)值個(gè)原子加入預(yù)選集會(huì)導(dǎo)致預(yù)選浪費(fèi)甚至誤選的問(wèn)題，提出變比例的稀疏度自適應(yīng)匹配追蹤（VP-SAMP）算法，該算法以?xún)?nèi)積累加比例準(zhǔn)則選擇預(yù)選集，并采用變閾值策略來(lái)控制不同迭代階段預(yù)選集選取原子的數(shù)量，保證大稀疏度情況下的較高重構(gòu)成功率同時(shí)減少小稀疏度情況下的運(yùn)行時(shí)間。仿真實(shí)驗(yàn)表明，VP-SAMP算法在重構(gòu)成功率和重構(gòu)誤差兩方面與SAMP算法相比一致的情況下，在大稀疏度時(shí)重構(gòu)成功率可平均提高5.84%。