李　佳，劉獻(xiàn)杰，智世鵬

(中國電子科技集團(tuán)公司第五十四研究所，河北 石家莊 050081)

0　引言

壓縮感知(Compressive Sensing,CS)指出，只要信號本身或在某個變換域上是稀疏的，就可以用一個與變換矩陣不相關(guān)的測量矩陣將變換域的高維信號投影到一個低維空間上，并通過求解一個優(yōu)化問題把原信號以高的概率重構(gòu)出來[1-3]。壓縮感知理論的主要內(nèi)容包括信號稀疏表示、測量矩陣構(gòu)造[4-7]以及重構(gòu)算法設(shè)計[8]，其應(yīng)用已擴(kuò)展到無線傳感網(wǎng)絡(luò)[9]、信道估計[10]等眾多應(yīng)用領(lǐng)域。

自CS理論提出以來，涌現(xiàn)了大量重構(gòu)算法，這些算法主要分為兩類:一類是基于最小化l1范數(shù)的線性規(guī)劃方法，包括BP算法[11]、內(nèi)點法等；另一類是基于最小化l0范數(shù)的貪婪算法，包括OMP算法[12]、ROMP算法[13]、SP算法[14]以及有良好重構(gòu)性能的IHT算法[15]、NIHT算法[16]、BIHT算法[17]等。雖然線性規(guī)劃方法能夠得到較高的重構(gòu)精度，但是其高計算復(fù)雜度極大地限制了應(yīng)用。貪婪迭代算法以其迭代快速而獲得廣泛應(yīng)用,但是其重構(gòu)的性能有待提高。

在原始IHT算法的基礎(chǔ)上，BIHT算法在每次迭代過程中加入了回溯過程，并采用基于最小二乘法的偽逆運(yùn)算來獲取原始稀疏信號的估計值。上述兩個改進(jìn)方式大大地提高了重構(gòu)性能，尤其是傳承了貪婪算法精髓的偽逆運(yùn)算。然而，BIHT算法在每次迭代過程中的回溯操作相對簡單，僅僅是將前一次迭代過程中的支撐集合并。

基于最小二乘法的稀疏信號重構(gòu)中重構(gòu)誤差為理論基礎(chǔ)，通過理論分析重構(gòu)誤差的顯示表示，并將保證重構(gòu)誤差隨算法迭代逐步較小的理念融入到回溯過程，設(shè)計一類改進(jìn)的迭代硬閾值算法。該算法在每次迭代過程中基于重構(gòu)誤差的差值選擇合并的指標(biāo)，并利用基于最小二乘法的偽逆運(yùn)算來獲取原始稀疏信號的估計值。通過高斯稀疏信號和0-1稀疏信號的重構(gòu)仿真實驗驗證了本文所提算法在重構(gòu)效率和重構(gòu)性能方面的優(yōu)勢。

1　壓縮感知理論

對于任意N維信號x={x1,...,xN}∈RN，支撐集supp(x)表示x的非零坐標(biāo)。當(dāng)|supp(x)|=K<

min‖x‖0使得y=Φx。

(1)

求解上述優(yōu)化問題是一個NP問題。為保證稀疏信號的精確重構(gòu)，測量矩陣Φ應(yīng)滿足下述有限緊致特性(RIP)[2]。

定義1：原始信號支撐集supp(x)=T?{1,...,N},矩陣ΦT由列數(shù)i∈T的列向量構(gòu)成,任意矢量q∈R|T|,K

(2)

則稱Φ滿足參數(shù)(K,δ)的有限緊支特性(RIP),其中0≤δ≤1,?|T|≤K,?q∈R|T|。

2　迭代硬閾值算法

文獻(xiàn)[15]為迭代硬閾值(IHT)算法用于壓縮感知重構(gòu)信號提供了一系列的理論保證，證明算法成功運(yùn)用較少的測量向量逼近原始信號，其迭代過程如下：假設(shè)x0=0，迭代

xn+1=HK(xn+ΦT(y-Φxn)),

(3)

式中，HK(α)是一個非線性算子，保留向量α中絕對值最大的K個分量，其他分量均設(shè)為零。如果按這樣的機(jī)制獲得非零支撐集合不唯一，則可隨機(jī)選擇其中一個集合或者預(yù)設(shè)要選擇分量的支撐集合。

上述算法更一般的形式是包含額外的步長μ>0，即

xn+1=HK(xn+μΦT(y-Φxn))。

(4)

運(yùn)用式(4)進(jìn)行迭代。Blumensath等人在文獻(xiàn)[16]中對上述迭代過程做了改進(jìn)，通過在迭代中加入一個自適應(yīng)決定的下降序列因子{μn}來保證算法的收斂及重構(gòu)的實現(xiàn)，使得算法保持尺度獨(dú)立。

文獻(xiàn)[17]提出了一種基于回溯的迭代硬閾值算法(BIHT)，該算法在每一次迭代過程中增加一步回溯的思想，前次迭代結(jié)果與非線性算法HK(α)產(chǎn)生的新向量支撐集合并，再通過偽逆過程與非線性算子HK(α)重新得到信號的逼近解。BIHT算法重構(gòu)信號僅僅需要很少的迭代次數(shù)即可高概率重構(gòu)原始稀疏信號。

3　改進(jìn)的迭代硬閾值算法

通過分析文獻(xiàn)[17]中的BIHT算法可知，利用估計支撐集Λn或者Γn得到的重構(gòu)效果沒有定量的評價，即無法保證支撐集Λn對應(yīng)的重構(gòu)誤差一定小于支撐集Λn-1對應(yīng)的重構(gòu)誤差，本文提出的改進(jìn)的迭代硬閾值算法就是針對上述不確定問題提出的，即可保證重構(gòu)誤差隨迭代的進(jìn)行而逐漸減小。

給定稀疏信號x，若估計支撐集為Λn，則重構(gòu)誤差可表示為：

(5)

其中，I=|Λn|=K。對任意i?Λn，若Γn=Λn∪{i},則重構(gòu)誤差的差值為[18-19]：

(6)

然而，當(dāng)并入的指標(biāo)多于1個時，無法得到上述理論保證。最理想的方式是初始化并入支撐集的原子數(shù)等于信號的稀疏度K，當(dāng)在某次迭代過程中無法保證RΓn-RΓn-1≤0成立時，放棄此次支撐集合并，改用K-1個指標(biāo)進(jìn)行支撐集更新，以此類推直到條件RΓn-RΓn-1≤0滿足成立。從理論上，此不同于BIHT和SP的回溯過程可保證稀疏信號的重構(gòu)誤差隨著迭代次數(shù)的增加而減小，即以稀疏優(yōu)化問題的全局最優(yōu)解為最終目標(biāo)。本文記基于上述支撐集更新的稀疏信號重建算法為Adaptive-MIHT算法。

由上述理論分析可知，此類稀疏重構(gòu)算法的計算復(fù)雜度集中于指標(biāo)的選擇以及基于最小二乘法的偽逆運(yùn)算這兩個過程。Adaptive-MIHT算法從理論上可以保證每次迭代過程中支撐集的選擇是最優(yōu)的，但是其自適應(yīng)選擇不同數(shù)據(jù)的支撐指標(biāo)過程給計算復(fù)雜度帶來了極大的不確定性，因為其會從K開始進(jìn)行遍歷選擇能夠保證重構(gòu)誤差單調(diào)減小的指標(biāo)數(shù)目。雖然上述過程能夠為迭代次數(shù)的減小帶來可觀的增量，但是其在算法重構(gòu)后期會因為數(shù)量較少的指標(biāo)導(dǎo)致在每次迭代過程中花費(fèi)較長的時間完成指標(biāo)自適應(yīng)選擇，這給稀疏信號重構(gòu)效率帶來了極大的挑戰(zhàn)。

為了驗證此類算法進(jìn)行稀疏信號重構(gòu)的統(tǒng)計性能，本文在仿真實驗部分采用基于蒙特卡洛的方法，以并入1個和K個原子為例，并分別命名2種算法為1-MIHT和K-MIHT算法。由上文可知，1-MIHT算法是K-MIHT算法中K=1的特殊情況。出于文章篇幅的考慮，本文僅以K-MIHT算法為例進(jìn)行算法的詳細(xì)介紹。

K?MIHT算法輸入值：測量值y，測量矩陣Φ，稀疏度K；初始化：x1=0，n=1，r1=y，步長=K；迭代：在第n次迭代中執(zhí)行下述步驟，直到滿足終止條件1：αn=HK(xn+ΦT(y-Φxn))，Λn=supp(αn)；2：ζ=ΦTy，Ψ=ΦTΦ；3：χ[Λn，：]=(ΦΛnTΦΛn)-1ΦΛnTΦ，Γn=Λn；4：forj=1：Ki＾=argmaxi∈{1，．．．，N}Γn(ζi{}-ζΓnTχ[Γn，i])2Ψ[i，i]-Ψ[Γn，i]Tχ[Γn，i]w=χ[Γn，i＾TΦΓnT，v=wΦ-Ψ[i＾，：]Ψ[i＾，i＾]-Ψ[Γn，i＾]Tχ[Γn，i＾]χ[Γn，：]=χ[Γn，：]+χ[Γn，i＾]vχ[i＾，：]=-v，Γn=Γn∪{i＾}　end5：x～n+1=Φ?Γny，xn+1=HK(x～n+1)輸出值：重構(gòu)稀疏信號x＾。

4　仿真實驗

本節(jié)以重構(gòu)一維高斯稀疏信號和0-1稀疏信號為例，詳細(xì)驗證本文所提的Adaptive-MIHT、1-MIHT和K-MIHT算法在稀疏信號重構(gòu)方面的性能。

首先進(jìn)行稀疏信號重構(gòu)時間的比較，仿真實驗運(yùn)用在CPU 為Intel E7500(雙核2.93 GHz),內(nèi)存為4 GBd的聯(lián)想機(jī)上。選取長度為N=256的0-1稀疏信號，其非零元素值為1，稀疏度K分別取15、30、50。測量矩陣選取128×256高斯隨機(jī)矩陣。每個算法分別運(yùn)行10次和100次迭代，且重復(fù)運(yùn)行100次稀疏信號重構(gòu)，得到下述平均重構(gòu)時間，如表1所示。由表1可知，當(dāng)?shù)螖?shù)為10且稀疏度K較小時，3種算法的重構(gòu)時間相當(dāng)，且隨著稀疏度增大，Adaptive-MIHT算法變得越來越慢。特別的，當(dāng)?shù)螖?shù)為100時，Adaptive-MIHT的重構(gòu)時間超過10 min，表現(xiàn)出極不理想的重構(gòu)效率。

表1不同算法重構(gòu)時間比較

K1?MIHTK?MIHTAdapt?MIHT150．05010．53730．49375．40830．8752—300．05520．60191．056611．58843．4509—500．06180．66121．941420．58167．4012—

“—”表示運(yùn)行時間超過10 min。

其次，采用蒙特卡洛方法進(jìn)行算法重構(gòu)性能的比較。考慮到Adaptive-MIHT算法在重構(gòu)效率方面的劣勢，本實驗僅驗證K-MIHT算法和1-MIHT算法，并選取IHT算法、NIHT算法以及BIHT算法為參考算法。選取長度為N=256的高斯隨機(jī)稀疏信號和0-1稀疏信號，其中高斯隨機(jī)稀疏信號的非零元素值滿足N(0,1)分布，而0-1稀疏信號的非零元素值為1。測量矩陣選取128×256高斯隨機(jī)矩陣。

圖1　重構(gòu)算法性能比較圖(高斯稀疏信號)

從圖1可以看出1-MIHT和K-MIHT算法重構(gòu)一維高斯稀疏信號性能明顯高于IHT算法、NIHT算法以及BIHT算法。特別的，當(dāng)稀疏度<53時，K-MIHT算法的精確重構(gòu)概率接近1，但是當(dāng)稀疏度繼續(xù)增大時精確重構(gòu)概率急劇降低。經(jīng)分析，導(dǎo)致上述重構(gòu)性能急劇下降的原因應(yīng)該是算法迭代過程中回溯步驟固定地選取了K個原子并入支撐集，并未得到局部最優(yōu)解。

圖2　重構(gòu)算法性能比較圖(0-1稀疏信號)

從圖2可以看出，1-MIHT和K-MIHT算法重構(gòu)0-1稀疏信號性能亦明顯高于IHT算法、NIHT算法以及BIHT算法。值得注意的是，K-MIHT表現(xiàn)出了非常好的性能，體現(xiàn)了IHT類算法中非線性算子HK(α)重構(gòu)0-1稀疏信號的高效性。

5　結(jié)束語

隨著壓縮感知中貪婪類稀疏重構(gòu)算法研究的深入，在算法迭代過程中加入回溯操作成為非常受關(guān)注的方向。本文基于IHT算法提出了一種與BIHT算法不同的回溯操作，該操作通過保證重構(gòu)誤差逐漸減小能夠提供非常優(yōu)秀的重構(gòu)性能。從一維稀疏信號重構(gòu)實驗來看，相比IHT、NIHT和BIHT算法，本文所提算法重構(gòu)性能是最優(yōu)的。然而，如何在Adaptive-MIHT算法的每次回溯過程中快速準(zhǔn)確地選擇最優(yōu)數(shù)量的原子來擴(kuò)展估計支撐集仍然是值得后續(xù)研究的問題。

[1]Donoho D L.Compressed Sensing[J].IEEE Transaction on Information Theory,2006,52(4):5406-5425.

[2]Donoho D L，Tsaig Y.Extensions of Compressed Sensing [J].Signal Processing,2006,86(3):533-548.

[3]羅純哲，陳金杰，王蔚東.壓縮感知理論與非凸優(yōu)化方法研究[J].無線電工程，2014，44(5):20-29.

[4]王強(qiáng)，李佳，沈毅.壓縮感知中確定性測量矩陣構(gòu)造算法綜述[J].電子學(xué)報，2013，41(10):2014-2050.

[5]李佳，王強(qiáng)，沈毅，等.壓縮感知中測量矩陣與重建算法的協(xié)同構(gòu)造[J].電子學(xué)報,2013,41(1):29-34.

[6]王戈,王輝,王小強(qiáng),等.基于交替投影的多參數(shù)聯(lián)合解調(diào)算法[J].無線電工程，2016，46(9):37-40.

[7]張業(yè)，李佳.一種壓縮感知詞典快速構(gòu)造方法[J].無線電通信技術(shù)，2017，43(3):30-33.

[8]何國棟,謝小娟,楊凌云,等.基于壓縮感知的信號重構(gòu)研究[J].無線電通信技術(shù)，2014，40(3):26-28.

[9]劉曉彤.基于DCS的無線傳感網(wǎng)絡(luò)數(shù)據(jù)壓縮算法研究[J].無線電通信技術(shù)，2017，43(1):23-26.

[10] 楊劍，蔣挺，趙成林，等.基于CS-ROMP算法的超寬帶信道估計[J].無線電工程，2011，41(5):14-17.

[11] Chen S B,Donoho D L，Saunders M A.Atomic Decomposition by Basis Pursuit[J].SIAM Journal on Scientific Computing,1998,20(1):33-61.

[12] Davenport M A ，Wakin M B.Analysis of Orthogonal Matching Pursuit Using the Restricted Isometry Property [J].IEEE Transaction on Information Theory,2010,56(9),4395-4401.

[13] Needell D，Vershynin R.Signal Recovery From Incomplete and Inaccurate Measurement Via Regularized Orthogonal Matching Pursuit[J].IEEE Journal of Selected Topics in Signal Processing,2010,4(2)：310-316.

[14] Dai W，Milenkovic O.Subspace Pursuit for Compressive Sensing Signal [J].IEEE Transaction on Information Theory,2009,55(5): 325-330.

[15] Blumensath T，Davies M.Iterative Hard Thresholding for Compressed Sensing [J].Appl.Comput.Harmon.Anal,2009，27:265-274.

[16] Blumensath T,Davies M.Normalized Iterative Hard Thresholding:Guaranteed Stability and Performance[J].IEEE Journal of Selected Topics in Signal Processing,2010,4(2):298-308.

[17] 楊海蓉,方紅,張成,等.基于回溯的迭代硬閾值算法[J].自動化學(xué)報,2010,37(3): 276-282.

[18] 史榮昌,魏豐.矩陣分析[M].北京:北京理工大學(xué)出版社,2005.

[19] Varadarajan B,Khudanpur S，Tran T D.Stepwise Optimal Subspace Pursuit for Improving Sparse Recovery [J].IEEE Signal Processing Letter,2011,18(1): 27-30.