壓縮感知中一種改進的迭代硬閾值算法

李　佳，劉獻杰，智世鵬

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

0　引言

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

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

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

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

1　壓縮感知理論

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

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

(1)

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

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

(2)

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

2　迭代硬閾值算法

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

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

(3)

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

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

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

(4)

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

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

3　改進的迭代硬閾值算法

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

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

(5)

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

(6)

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

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

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

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)輸出值：重構稀疏信號x＾。

4　仿真實驗

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

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

表1不同算法重構時間比較

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

“—”表示運行時間超過10 min。

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

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

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

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

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

5　結束語

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

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

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

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

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

[9]劉曉彤.基于DCS的無線傳感網(wǎng)絡數(shù)據(jù)壓縮算法研究[J].無線電通信技術，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].自動化學報,2010,37(3): 276-282.

[18] 史榮昌,魏豐.矩陣分析[M].北京:北京理工大學出版社,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.