李 佳

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

10.3969/j.issn.1003-3114.2018.01.12

李佳.一種迭代加權(quán)感知詞典構(gòu)造權(quán)值初始化方法[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.]

一種迭代加權(quán)感知詞典構(gòu)造權(quán)值初始化方法

李 佳

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

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

壓縮感知；迭代加權(quán)；感知詞典；貪婪算法

TN391.41

A

1003-3114(2018)01-60-5

2017-09-25

河北省重大科技成果轉(zhuǎn)化專項項目(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]?；粉櫵惴▽⑾∈鑶栴}轉(zhuǎn)化為線性規(guī)劃問題，然后用線性規(guī)劃方法得到問題的解?；粉櫵惴ㄓ蟹浅?yōu)秀的信號恢復性能，但其復雜度巨大成為應用的一大瓶頸[3]。貪婪算法相對而言雖不如前者，但由于其相對小的計算量而得到廣泛應用。貪婪算法中最典型算法是OMP(Orthogonal Matching Pursuit)算法[4]，諸多文獻也對OMP算法進行了細致分析。改進的貪婪算法如SP(Subspace Pursuit)算法等提高了貪婪算法的性能，甚至優(yōu)于線性規(guī)劃算法[5]。

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

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

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

本文首先簡單回顧了下壓縮感知基本理論以及OMP算法和感知詞典的概念，然后分析了迭代加權(quán)感知詞典構(gòu)造算法[13]權(quán)值初始化標準，繼而給出一種新的權(quán)值初始化方法并說明此方法的優(yōu)點。最后通過仿真說明采用新的權(quán)值初始化方法的迭代加權(quán)感知詞典構(gòu)造算法所構(gòu)造的感知詞典可提高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為零范數(shù)，即向量中非零元素個數(shù)。l0最小問題是一個數(shù)學上的組合難題，直接求解計算量巨大。文獻[6]和文獻[9]指出，當量測詞典滿足一定要求時，l0最小問題在一定條件下與l1最小問題等價。貪婪算法為解l0最小問題次優(yōu)算法，盡管其性能不及基于求解l1最小問題線性規(guī)劃算法，但由于其計算量小而得到廣泛應用。

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

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

(2)

(3)

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

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

(4)

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

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

(5)

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

(6)

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

2 迭代加權(quán)感知詞典初始化方法

2.1 迭代加權(quán)感知詞典構(gòu)造

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

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

(7)

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

(8)

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

(9)

式中，γ為一非零正數(shù)。然而稀疏信號為未知的，故如何利用稀疏信號進行加權(quán)矩陣構(gòu)造成為難題。

由文獻[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非?！跋瘛?，因此將識別向量代替稀疏信號進行初始化加權(quán)矩陣是一個很好的方法。文獻[13]基于上述思想提出一種迭代加權(quán)感知詞典構(gòu)造方法，其迭代地構(gòu)造加權(quán)矩陣和感知詞典，在每一步迭代中減小感知詞典與量測詞典的局部積累相關系數(shù)，其計算步驟為：

① 初始化：令加權(quán)矩陣W=diag{|ΦTy|};

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

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

⑤ 更新權(quán)值矩陣W：W=diag{|ΨTy|}。

2.2 迭代加權(quán)感知詞典初始化

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

(13)

(14)

結(jié)合感知詞典的加權(quán)矩陣初始化方法，提出新的權(quán)值初始化方法的迭代加權(quán)感知詞典構(gòu)造算法如下所示。

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

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

⑤ 更新權(quán)值矩陣W：W=diag{|ΨTy|}。

3 仿真分析

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

圖4比較了IRSDC算法和本文算法構(gòu)造感知詞典與量測詞典的局部積累相關系數(shù)?？梢钥闯霎斚∈栊盘栂∈瓒缺容^小時，兩種算法所構(gòu)造的感知詞典與量測詞典局部積累相關系數(shù)都比較小，幾乎為0，即支撐集對應的原子與其他所有原子幾乎正交。當信號稀疏度比較大時，兩種算法對應的局部積累相關系數(shù)都迅速增大，但采用權(quán)值初始化方法的IRSDC算法的局部積累相關系數(shù)始終小于IRSDC算法。

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

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

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

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

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

4 結(jié)束語

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

[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―)，男，工程師，主要研究方向：數(shù)字信號處理、認知無線電、稀疏優(yōu)化算法。

法國開發(fā)目前世界上唯一安全環(huán)境下艦載多媒體動中通系統(tǒng)

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

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

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

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

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