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

李 佳

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

10.3969/j.issn.1003-3114.2018.01.12

李佳.一種迭代加權(quán)感知詞典構(gòu)造權(quán)值初始化方法[J].無(wú)線(xiàn)電通信技術(shù),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)值初始化方法

李 佳

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

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

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

TN391.41

A

1003-3114(2018)01-60-5

2017-09-25

河北省重大科技成果轉(zhuǎn)化專(zhuān)項(xiàng)項(xiàng)目(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 引言

壓縮感知理論表明稀疏信號(hào)可以通過(guò)其非自適應(yīng)線(xiàn)性投影恢復(fù)[1]。一般用矩陣表示非自適應(yīng)線(xiàn)性投影，此矩陣被稱(chēng)為量測(cè)詞典，投影信號(hào)稱(chēng)為量測(cè)信號(hào)。除了非自適應(yīng)線(xiàn)性投影之外，壓縮感知的另一個(gè)核心問(wèn)題是信號(hào)恢復(fù)，即如何利用量測(cè)信號(hào)和量測(cè)詞典恢復(fù)原稀疏信號(hào)。

自從壓縮感知理論誕生以來(lái)，各種信號(hào)恢復(fù)算法層出不窮。最廣泛使用方法有兩大類(lèi)：基追蹤算法和貪婪算法[2]?；粉櫵惴▽⑾∈鑶?wèn)題轉(zhuǎn)化為線(xiàn)性規(guī)劃問(wèn)題，然后用線(xiàn)性規(guī)劃方法得到問(wèn)題的解?；粉櫵惴ㄓ蟹浅?yōu)秀的信號(hào)恢復(fù)性能，但其復(fù)雜度巨大成為應(yīng)用的一大瓶頸[3]。貪婪算法相對(duì)而言雖不如前者，但由于其相對(duì)小的計(jì)算量而得到廣泛應(yīng)用。貪婪算法中最典型算法是OMP(Orthogonal Matching Pursuit)算法[4]，諸多文獻(xiàn)也對(duì)OMP算法進(jìn)行了細(xì)致分析。改進(jìn)的貪婪算法如SP(Subspace Pursuit)算法等提高了貪婪算法的性能，甚至優(yōu)于線(xiàn)性規(guī)劃算法[5]。

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

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

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

本文首先簡(jiǎn)單回顧了下壓縮感知基本理論以及OMP算法和感知詞典的概念，然后分析了迭代加權(quán)感知詞典構(gòu)造算法[13]權(quán)值初始化標(biāo)準(zhǔn)，繼而給出一種新的權(quán)值初始化方法并說(shuō)明此方法的優(yōu)點(diǎn)。最后通過(guò)仿真說(shuō)明采用新的權(quán)值初始化方法的迭代加權(quán)感知詞典構(gòu)造算法所構(gòu)造的感知詞典可提高OMP算法稀疏信號(hào)恢復(fù)性能，甚至超過(guò)LP算法性能。

1 壓縮感知基本理論

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

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

(1)

式中，‖·‖0為零范數(shù)，即向量中非零元素個(gè)數(shù)。l0最小問(wèn)題是一個(gè)數(shù)學(xué)上的組合難題，直接求解計(jì)算量巨大。文獻(xiàn)[6]和文獻(xiàn)[9]指出，當(dāng)量測(cè)詞典滿(mǎn)足一定要求時(shí)，l0最小問(wèn)題在一定條件下與l1最小問(wèn)題等價(jià)。貪婪算法為解l0最小問(wèn)題次優(yōu)算法，盡管其性能不及基于求解l1最小問(wèn)題線(xiàn)性規(guī)劃算法，但由于其計(jì)算量小而得到廣泛應(yīng)用。

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

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

(2)

(3)

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

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

(4)

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

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

(5)

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

(6)

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

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

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

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

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

(7)

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

(8)

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

(9)

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

由文獻(xiàn)[8]可知，識(shí)別向量h=ΦTy與稀疏信號(hào)x有：

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

(10)

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

(11)

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

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

② 重復(fù)以下步驟直至終止條件滿(mǎn)足;

③ 計(jì)算矩陣R：R=ΦW2ΦT;

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

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

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

(13)

(14)

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

② 重復(fù)以下步驟直至終止條件滿(mǎn)足；

③ 計(jì)算矩陣R：R=ΦW2ΦT；

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

3 仿真分析

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

圖4比較了IRSDC算法和本文算法構(gòu)造感知詞典與量測(cè)詞典的局部積累相關(guān)系數(shù)。可以看出當(dāng)稀疏信號(hào)稀疏度比較小時(shí)，兩種算法所構(gòu)造的感知詞典與量測(cè)詞典局部積累相關(guān)系數(shù)都比較小，幾乎為0，即支撐集對(duì)應(yīng)的原子與其他所有原子幾乎正交。當(dāng)信號(hào)稀疏度比較大時(shí)，兩種算法對(duì)應(yīng)的局部積累相關(guān)系數(shù)都迅速增大，但采用權(quán)值初始化方法的IRSDC算法的局部積累相關(guān)系數(shù)始終小于IRSDC算法。

圖1 IRSDC算法和本文算法對(duì)應(yīng)局部積累相關(guān)系數(shù).

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

圖2 OMP算法恢復(fù)0-1稀疏信號(hào)性能比較

圖3 OMP算法恢復(fù)高斯稀疏信號(hào)性能比較

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

4 結(jié)束語(yǔ)

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

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

[2] 焦李成,楊淑媛.壓縮感知回顧與展望[J].電子學(xué)報(bào),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].成都： 電子科技大學(xué),2011.

李佳(1986―)，男，工程師，主要研究方向：數(shù)字信號(hào)處理、認(rèn)知無(wú)線(xiàn)電、稀疏優(yōu)化算法。

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

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

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

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

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

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