一種迭代加權感知詞典構造權值初始化方法

李 佳

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

10.3969/j.issn.1003-3114.2018.01.12

李佳.一種迭代加權感知詞典構造權值初始化方法[J].無線電通信技術,2018,44(1):60-64.

[LI Jia.A Novel Method for Weight Initialization in Iterative Reweighted Sensing Dictionary Construction Algorithm [J].Radio Communications Technology,2018,44(1): 60-64.]

一種迭代加權感知詞典構造權值初始化方法

李 佳

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

迭代加權詞典構造算法可構造具有小局部積累相關系數的感知詞典，可有效地提高壓縮感知中貪婪算法的信號恢復性能。提出一種加權迭代詞典構造算法權值初始化方法。根據量測詞典構造小相關系數感知詞典，由感知詞典和量測信號得到識別向量，將識別向量用于權值矩陣的構造。分析和仿真了此權值初始化方法的性能。結果表明，在相同迭代次數條件下，利用提出的權值初始化方法所構造詞典具有小的局部相關系數，提高壓縮感知中OMP算法信號恢復性能。

壓縮感知；迭代加權；感知詞典；貪婪算法

TN391.41

A

1003-3114(2018)01-60-5

2017-09-25

河北省重大科技成果轉化專項項目(14040322Z)

ANovelMethodforWeightInitializationinIterativeReweightedSensingDictionaryConstructionAlgorithm

LI Jia

(The 54th Research Institute of CETC,Shijiazhuang 050081,China)

Iterative reweighted sensing dictionary construction (IRSDC) algorithm can construct sensing dictionary with small local cumulative coherence which will improves the performance of greedy algorithm.This paper presents a novel weight matrix initialization method for IRSDC algorithm.The sensing dictionary is calculated according to the measurement dictionary.The identification vector is obtained using the sensing dictionary and the measurement signal.The identification vector is utilized in the initialization of weighting matrix.The effectiveness of the weight initialization method is tested by both analysis and simulation.Results indicate that with the same number of iteration,the IRSDC algorithm with the novel weight initialization method can construct sensing dictionary with smaller local cumulative coherence which improves the performance of OMP algorithm.

compressive sensing; iterative reweight; sensing dictionary; greedy algorithm

0 引言

壓縮感知理論表明稀疏信號可以通過其非自適應線性投影恢復[1]。一般用矩陣表示非自適應線性投影，此矩陣被稱為量測詞典，投影信號稱為量測信號。除了非自適應線性投影之外，壓縮感知的另一個核心問題是信號恢復，即如何利用量測信號和量測詞典恢復原稀疏信號。

自從壓縮感知理論誕生以來，各種信號恢復算法層出不窮。最廣泛使用方法有兩大類：基追蹤算法和貪婪算法[2]。基追蹤算法將稀疏問題轉化為線性規劃問題，然后用線性規劃方法得到問題的解。基追蹤算法有非常優秀的信號恢復性能，但其復雜度巨大成為應用的一大瓶頸[3]。貪婪算法相對而言雖不如前者，但由于其相對小的計算量而得到廣泛應用。貪婪算法中最典型算法是OMP(Orthogonal Matching Pursuit)算法[4]，諸多文獻也對OMP算法進行了細致分析。改進的貪婪算法如SP(Subspace Pursuit)算法等提高了貪婪算法的性能，甚至優于線性規劃算法[5]。

實質上，量測詞典的性質與信號恢復成功與否有重大聯系。一方面，詞典的性質決定了是否可利用量測信號和量測詞典恢復原稀疏信號，即壓縮感知問題解的存在性或唯一性[6]；另一方面，詞典的性質也決定了常用信號恢復方法如OMP算法是否可成功恢復原稀疏信號[7-8]。因此，量測詞典設計問題成為壓縮感知一大研究熱點。

研究者通常用兩個參數來描述量測詞典性質：相關系數和有限等距特性(Restricted Isometry Property,RIP)常數[9]。對于一量測詞典，相關系數相比于RIP常數易于計算，小的相關系數常常成為量測詞典構造的標準。

文獻[10]給出一種基于交互投影算法構造等角度緊框架，對于部分維數可以得到相關系數達到Welch界的矩陣，但對于大部分維數無法得到小的相關系數矩陣。文獻[11]給出了感知詞典概念及其構造算法，分析及仿真證明了應用感知詞典可提高OMP算法性能。文獻[12]利用交互投影算法同時構造感知詞典與量測詞典，利用此詞典可進一步提高OMP算法性能，但每一步解決優化問題增加了計算量。文獻[13]給出一種迭代加權方法構造感知詞典，此方法降低了局部相關系數，可大大提高OMP性能。但此算法權值初始值選取過于簡單且沒給出權值選取標準分析。

本文首先簡單回顧了下壓縮感知基本理論以及OMP算法和感知詞典的概念，然后分析了迭代加權感知詞典構造算法[13]權值初始化標準，繼而給出一種新的權值初始化方法并說明此方法的優點。最后通過仿真說明采用新的權值初始化方法的迭代加權感知詞典構造算法所構造的感知詞典可提高OMP算法稀疏信號恢復性能，甚至超過LP算法性能。

1 壓縮感知基本理論

信號x∈Rn×1為k稀疏信號，即|sup(x)|≤k，支撐集sup(x)表示x中非零元素位置組成的集合，k常被稱為稀疏度。Φ∈Rm×n為量測詞典，其中每一列向量稱為原子且具有單位長度。量測信號為y=Φx∈Rm×1，m?n。壓縮感知核心問題為如何利用量測信號y和量測詞典Φ恢復稀疏信號x，即求解欠定線性方程組：

min‖x‖0s.t.y=Φx，

(1)

式中，‖·‖0為零范數，即向量中非零元素個數。l0最小問題是一個數學上的組合難題，直接求解計算量巨大。文獻[6]和文獻[9]指出，當量測詞典滿足一定要求時，l0最小問題在一定條件下與l1最小問題等價。貪婪算法為解l0最小問題次優算法，盡管其性能不及基于求解l1最小問題線性規劃算法，但由于其計算量小而得到廣泛應用。

相關系數和RIP常數常被用來衡量量測詞典性質。定義1、2給出這2個概念的定義。

定義1[7]：對量測詞典Φ∈Rm×n，相關系數和積累相關系數定義為：

(2)

(3)

式中，φi和φj分別為詞典Φ的第i列和第j列。

定義2[9]：量測詞典Φ∈Rm×n，對于任意k系數信號x，如：

(4)

若成立則稱量測矩陣滿足k階有限等距特性(Restricted Isometry Property)，稱δk為RIP常數。

基于相關性思想，文獻[11]提出感知詞典概念，即在OMP算法中，Ψ∈Rm×n取代量測詞典，此詞典被稱為感知詞典性質如式(5)所示。

(5)

其中ψi和φj分別為感知詞典Ψ的第i列和量測詞典Φ的第j列。感知詞典構造可以寫成：

(6)

類似于量測詞典相關系數，把感知詞典與量測詞典不同列原子內積絕對值的最大值定義為交叉相關系數，文獻[11]證明了小的交叉相關系數可提高OMP信號恢復性能。

2 迭代加權感知詞典初始化方法

2.1 迭代加權感知詞典構造

根據量測信號的定義可知，量測信號僅是量測詞典有限個原子的線性組合，線性組合原子的選取和線性組合系數都由稀疏信號決定。在構造感知詞典時，僅需關心參與量測信號組合原子與所有原子的相關性。局部積累相關系數即描述了量測信號組合原子與所有原子的相關性。

定義3[13]：感知詞典Ψ∈Rm×n，量測詞典Φ∈Rm×n，量測信號為y=Φx，Λ為稀疏信號x支撐集，則局部積累相關系數定義為：

(7)

可以看出，構造感知詞典使其與量測詞典有小的局部積累相關系數對OMP算法有重要意義。因此，在感知詞典構造過程中，應該對不同位置的相關系數給予不同的加權，這種思想可以寫為：

(8)

式中，W為一對角線加權矩陣。根據局部積累相關系數定義可知，加權矩陣W的選取應根據稀疏信號x構造，即在信號支撐集部分權值非零而在其他位置權值為零，或者更進一步，加權矩陣應滿足：

(9)

式中，γ為一非零正數。然而稀疏信號為未知的，故如何利用稀疏信號進行加權矩陣構造成為難題。

由文獻[8]可知，識別向量h=ΦTy與稀疏信號x有：

|h(i)-x(i)|≤δk+1‖x‖2，

(10)

(1-δk)‖x‖2≤‖h‖2≤(1+δk)‖x‖2。

(11)

即識別向量h與稀疏信號x非常“像”，因此將識別向量代替稀疏信號進行初始化加權矩陣是一個很好的方法。文獻[13]基于上述思想提出一種迭代加權感知詞典構造方法，其迭代地構造加權矩陣和感知詞典，在每一步迭代中減小感知詞典與量測詞典的局部積累相關系數，其計算步驟為：

① 初始化：令加權矩陣W=diag{|ΦTy|};

② 重復以下步驟直至終止條件滿足;

③ 計算矩陣R：R=ΦW2ΦT;

⑤ 更新權值矩陣W：W=diag{|ΨTy|}。

2.2 迭代加權感知詞典初始化

根據2.1節中介紹的理論分析和文獻[13]提出的方法，可以通過迭代加權構造感知詞典，并改善OMP算法的性能。然而，當量測詞典的相關性約束較差時，利用量測詞典得到的識別向量進行并非為最好的識別向量，也無法保證OMP算法能夠精準的識別出原始系數信號的支撐集。

(13)

(14)

結合感知詞典的加權矩陣初始化方法，提出新的權值初始化方法的迭代加權感知詞典構造算法如下所示。

② 重復以下步驟直至終止條件滿足；

③ 計算矩陣R：R=ΦW2ΦT；

⑤ 更新權值矩陣W：W=diag{|ΨTy|}。

3 仿真分析

仿真分析中，構造維數為128×256的量測詞典，其中每一個元素為N(0,1)(均值為0方差為1的高斯分布)隨機數，詞典的每一列都歸一化。稀疏信號長度為256，非零元素值為1和N(0,1)隨機數。分別用迭代加權感知詞典構造算法和本文所提的采用權值初始化方法的算法構造感知詞典。為了敘述方便，以下將迭代加權感知詞典構造算法簡稱為IRSDC算法。

圖4比較了IRSDC算法和本文算法構造感知詞典與量測詞典的局部積累相關系數。可以看出當稀疏信號稀疏度比較小時，兩種算法所構造的感知詞典與量測詞典局部積累相關系數都比較小，幾乎為0，即支撐集對應的原子與其他所有原子幾乎正交。當信號稀疏度比較大時，兩種算法對應的局部積累相關系數都迅速增大，但采用權值初始化方法的IRSDC算法的局部積累相關系數始終小于IRSDC算法。

圖1 IRSDC算法和本文算法對應局部積累相關系數.

圖2和圖3比較了兩種算法所構造的感知詞典提高OMP算法恢復稀疏信號的程度，其中詞典構造算法迭代次數為10。圖2中稀疏信號非零元素值為1(簡稱0-1稀疏信號)，可以看出在相同的迭代次數下，利用權值初始化方法構造的感知詞典可顯著提高OMP算法恢復稀疏信號性能，且明顯優于LP算法。圖3中稀疏信號非零元素值為N(0,1)隨機數(簡稱高斯稀疏信號)時，利用權值初始化方法的IRSDC算法與LP算法相當，明顯的優于利用IRSDC算法的恢復結果。

圖2 OMP算法恢復0-1稀疏信號性能比較

圖3 OMP算法恢復高斯稀疏信號性能比較

由以上仿真可知采用新的權值初始化方法IRSDC算法有非常好的性能。在壓縮感知領域，由于LP算法性能優異而成為其他諸多信號恢復算法性能評價標準，但LP算法計算量巨大而限制了其應用。恢復非零元素值為1的稀疏信號是基于OMP等算法的難題。基于OMP算法的改進算法如SP算法，其恢復非零元素值為N(0,1)分布稀疏信號時，其性能優于LP算法；但恢復非零元素值為1稀疏信號其性能遠低于LP算法。從圖2和圖3可看出采用權值初始化方法IRSDC算法所構造的感知詞典，使OMP算法性能優于LP算法。而使用IRSDC算法所構造的感知詞典，OMP算法恢復非零元素值為1的稀疏信號性能仍低于LP算法。

4 結束語

在壓縮感知中，以LP算法為代表的基追蹤算法比以OMP算法為代表的貪婪算法具有更高的稀疏信號回復性能，但是其應用受到高計算復雜度嚴重的制約。針對構造并利用感知詞典提高OMP算法性能的研究，本文以構造與稀疏信號盡可能“像”的識別向量為突破口，通過理論分析得出利用感知詞典構造的識別向量能夠提供更高的稀疏信號支撐集識別精度，在此基礎上提出一種迭代加權感知詞典構造算法權值初始化方法。使用新的權值初始化方法，在相同的迭代次數下，迭代加權感知詞典構造算法可構造小的局部積累相關系數感知詞典。同時，利用該方法構造的感知詞典，OMP算法恢復稀疏信號的性能得到了極大的提高，在稀疏度較大時OMP算法恢復稀疏信號百分比高于LP算法。由上述仿真結果可知，以OMP算法為代表的貪婪算法恢復稀疏信號的準確性受量測詞典和感知詞典制約。因此，可通過構造更優的詞典來保證信號恢復的精度。

[1] Donoho D.Compressed Sensing[J].IEEE Trans.Inf.Theory,2006,52(4): 1289-1306.

[2] 焦李成,楊淑媛.壓縮感知回顧與展望[J].電子學報,2011,39(7): 1651-1662.

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

[4] Tropp J A,Gilbert A C.Signal Recovery from Random Measurements via Orthogonal Matching Pursuit [J].IEEE Trans.Inf.Theory,2007,53(12): 4655-4666.

[5] Wei D, Milenkovic O.Subspace Pursuit for Compressive Sensing Signal Reconstruction [J].IEEE Trans.Inf.Theory,2009,55(5): 2230-2249.

[6] Candes E J.The Restricted Isometry Property and its Implications for Compressed Sensing [J].C.R.Acad.Sci.Pairs,2008,346(9-10):589-592.

[7] Tropp J A.Greed is Good: Algorithmic Results for Sparse Approximation [J].IEEE Trans.Inf.Theory,2004,50(10): 2231-2242.

[8] Davenport M A,Wakin M B.Analysis of Orthogonal Matching Pursuit Approach via Restricted Isometry Property [J].IEEE Trans.Inf.Theory,2010,56(9): 4395-4401.

[9] Candes E J,Tao T.Decoding by Linear Programming [J].IEEE Trans.Inf.Theory,2005,51(12):4203-4215.

[10] Tropp J A,Dhillon I S.Designing Structured Tight Frames via an Alternating Projection Method [J].IEEE Tans.Inf.Theory,2005,51(1): 188-209.

[11] Schnass K,Vandergheynst P.Dictionary Precondition for Greedy Algorithms [J].IEEE Trans.Signal Process,2008,56(5): 1994-2002.

[12] Bo L,Yi S,Jia L.Dictionaries Construction Using Alternating Projection Method in Compressive Sensing [J]. IEEE Signal Processing Letters.2011,18(11): 663-666.

[13] Huang A, Guan G.A Re-weighted Algorithm for Design data Dependent Sensing Dictionary [J].Int,J.Phys.Sci.,2011,6(3):386-390.

[14] Mo Q,Song L.New Bounds on the Restricted Isometry Constantδ2k[J].Applied and Computational Harmonic Analysis,2011,31(3): 460-468.

[15] Mo Q,Yi S.A Remark on the Restricted Isometry Property in Orthogonal Matching Pursuit [J].IEEE Trans.Inf.Theory.2012,58(6): 3654-3656.

[16] 黃安民.基于感知字典的稀疏重建算法研究[D].成都： 電子科技大學,2011.

李佳(1986―)，男，工程師，主要研究方向：數字信號處理、認知無線電、稀疏優化算法。

法國開發目前世界上唯一安全環境下艦載多媒體動中通系統

在當今移動互連時代下，法國泰雷茲公司開發了COMTICS系統，這是世界上首個艦載信息分發系統，可在高度安全環境中提供多種服務，使海軍人員在不損害安全性的情況下在海上使用智能電話。

COMTICS是一種類似于智能電話的多媒體通信設備，讓海軍人員可利用各類軍用電臺獲得穩定的艦載移動連接能力。該系統提供的服務包括視頻和數據傳輸、web瀏覽和社交媒體訪問，如果工作條件允許還可與同事聊天。

COMTICS的設計基于已經過海上驗證并在多國海軍中應用的NGIN(海軍VoIP)和FOCON IP(光纖通信網絡)解決方案。COMTICS提供最高級別的IT防護，能根據用戶的特定需求定制，并將網絡安全專業經驗和海軍環境實際情況相結合。為了確保在多種環境甚至戰損情況下的服務可用性，COMTICS采用冗余全IP體系結構，確保工作連續性。該系統可同時支持3 000個呼叫,其魯棒、獨立和穩固特性，支持在惡劣海軍環境下工作，且能適應多種艦船類型。

COMTICS采用便于學習和使用的直觀界面，可在數周內完成整個安裝。COMTICS可為海軍人員提供關鍵的新應用和服務，在艦船上實現更強大的移動性，改變了通信設備使用方式，提高了工作效率。

COMTICS是目前市場上唯一為海軍人員提供移動服務的產品,海軍人員可用它與家人和朋友保持聯系，改善海上生活質量。