一种迭代加权感知词典构造权值初始化方法

李 佳

(中国电子科技集团公司第五十四研究所，河北 石家庄 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是目前市场上唯一为海军人员提供移动服务的产品,海军人员可用它与家人和朋友保持联系，改善海上生活质量。