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

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

0　引言

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

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

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

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

1　壓縮感知理論

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

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

(1)

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

定義1：原始信號(hào)支撐集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)信號(hào)提供了一系列的理論保證，證明算法成功運(yùn)用較少的測(cè)量向量逼近原始信號(hào)，其迭代過程如下：假設(shè)x0=0，迭代

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

(3)

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

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

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

(4)

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

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

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

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

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

(5)

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

(6)

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

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

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

K?MIHT算法輸入值：測(cè)量值y，測(cè)量矩陣Φ，稀疏度K；初始化：x1=0，n=1，r1=y，步長(zhǎng)=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)稀疏信號(hào)x＾。

4　仿真實(shí)驗(yàn)

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

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

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

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

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

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

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

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

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

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

5　結(jié)束語

隨著壓縮感知中貪婪類稀疏重構(gòu)算法研究的深入，在算法迭代過程中加入回溯操作成為非常受關(guān)注的方向。本文基于IHT算法提出了一種與BIHT算法不同的回溯操作，該操作通過保證重構(gòu)誤差逐漸減小能夠提供非常優(yōu)秀的重構(gòu)性能。從一維稀疏信號(hào)重構(gòu)實(shí)驗(yàn)來看，相比IHT、NIHT和BIHT算法，本文所提算法重構(gòu)性能是最優(yōu)的。然而，如何在Adaptive-MIHT算法的每次回溯過程中快速準(zhǔn)確地選擇最優(yōu)數(shù)量的原子來擴(kuò)展估計(jì)支撐集仍然是值得后續(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)，李佳，沈毅.壓縮感知中確定性測(cè)量矩陣構(gòu)造算法綜述[J].電子學(xué)報(bào)，2013，41(10):2014-2050.

[5]李佳，王強(qiáng)，沈毅，等.壓縮感知中測(cè)量矩陣與重建算法的協(xié)同構(gòu)造[J].電子學(xué)報(bào),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]何國(guó)棟,謝小娟,楊凌云,等.基于壓縮感知的信號(hào)重構(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ì)[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].自動(dòng)化學(xué)報(bào),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.