基于渐进添边的准循环压缩感知时延估计算法-冷雪冬.pdf

《基于渐进添边的准循环压缩感知时延估计算法-冷雪冬.pdf》由会员分享，可在线阅读，更多相关《基于渐进添边的准循环压缩感知时延估计算法-冷雪冬.pdf（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、基于渐进添边的准循环压缩感知时延估计算法冷雪冬王大鸣巴斌王建辉A quasi-cyclic compressed sensing delay estimation algorithm based on progressive edge-growthLeng Xue-Dong Wang Da-Ming Ba Bin Wang Jian-Hui引用信息Citation: Acta Physica Sinica , 66, 090703 (2017) DOI: 10.7498/aps.66.090703在线阅读View online: http:/dx.doi.org/10.7498/aps.66.

2、090703当期内容View table of contents: http:/ you may be interested in基于回溯筛选的稀疏重构时延估计算法Sparse reconstruction time delay estimation algorithm based on backtracking filter物理学报.2016, 65(21): 210701 http:/dx.doi.org/10.7498/aps.65.210701基于高速移动通信的虚拟天线阵列理论研究Virtual antenna array theory based on high speed mobi

3、le communications物理学报.2016, 65(7): 070701 http:/dx.doi.org/10.7498/aps.65.070701交替寻优生成元素幅值结合混沌随机相位构造循环测量矩阵Constructingcirculantmeasurementmatrixthroughalternatingoptimizingamplitudestogetherwithchaoticstochastic phases of the matrix generating elements物理学报.2015, 64(13): 130702 http:/dx.doi.org/10.74

4、98/aps.64.130702一种基于选择性测量的自适应压缩感知方法An adaptive compressed sensing method based on selective measure物理学报.2014, 63(20): 200701 http:/dx.doi.org/10.7498/aps.63.200701基于马尔科夫链蒙特卡罗的时延估计算法Time delay estimation using Markov Chain Monte Carlo method物理学报.2014, 63(13): 130701 http:/dx.doi.org/10.7498/aps.63.13

5、0701万方数据物理学报Acta Phys. Sin. Vol. 66, No. 9 (2017) 090703基于渐进添边的准循环压缩感知时延估计算法 冷雪冬y王大鸣巴斌王建辉(解放军信息工程大学信息系统工程学院,郑州450001)(2016年12月15日收到; 2017年2月3日收到修改稿)针对时延估计问题中压缩感知类算法现有测量矩阵需要大量数据存储量的问题,提出了一种基于渐进添边的准循环压缩感知时延估计算法,实现了稀疏测量矩阵条件下接收信号时延的准确估计.该算法首先建立压缩感知与最大似然译码之间的理论桥梁,然后推导基于低密度奇偶校验码的测量矩阵的设计准则,引入渐进添边的思想构造具有准循环

6、结构的稀疏测量矩阵,最后利用正交匹配追踪算法正确估计出时延.对本文算法的计算复杂度与测量矩阵的数据存储量进行理论分析.仿真结果表明,所提算法在测量矩阵维数相同的条件下正确重构概率高于高斯随机矩阵和随机奇偶校验测量矩阵,相比于随机奇偶校验矩阵,在数据存储量相等的条件下,以较少的计算复杂度代价得到了重构概率的较大提高.关键词:时延估计,压缩感知,测量矩阵,渐进添边PACS: 07.50.Qx, 07.05.Kf, 84.40.Ua, 89.70.Eg DOI: 10.7498/aps.66.0907031引言时延估计1问题是无线定位技术2中备受关注的研究热点,压缩感知(compressed sen

7、sing,CS)理论3在2004年提出后被广泛应用于图像还原4、角度估计5中.在时延估计问题中,同样可以将信号到达时间稀疏化来构造信号的时域稀疏模型6,从而利用CS理论对接收信号进行重构.CS理论的核心问题是信号的重构问题,针对重构算法的研究和改进一直是CS理论的研究重点,然而要提高信号的正确重构概率,仅仅研究鲁棒性强、普适性高的重构算法是不够的.由于测量矩阵在重构信号的过程中具有至关重要的作用,针对测量矩阵的研究在近两年成为该领域的研究热点.现有的测量矩阵主要分为两类,即随机测量矩阵和确定性测量矩阵.随机测量矩阵7包括高斯随机矩阵、托普利兹矩阵、随机伯努利矩阵、局部哈达码矩阵和局部傅里叶矩阵

8、等.这一类测量矩阵的性能存在瓶颈:首先,由于测量矩阵的数据往往是冗余的,因此随机数的生成与存储对硬件提出了很高的要求;其次,随机矩阵只能在统计意义上以高概率满足约束等距性(restricted isometry property, RIP)准则8,即不能确保任意一个随机矩阵都满足正确重构的必要条件.为了解决随机测量矩阵的数据存储量冗余问题并对其性能进行确定性分析,很多新的方法被应用于确定性测量矩阵的研究之中.文献9中的测量矩阵从有限域出发,根据多项式的系数构造测量矩阵,在二维图像的重构过程中性能优于高斯随机矩阵.但该方法构造的测量矩阵复杂度受维度影响较大.文献10定义了测量矩阵的Welch界,

9、并据此构建了最大Welch界等式矩阵,取得了较好的重构效果.但该矩阵只能在特定条件下构造,应用的普适性不高. 2012年,文献11将测量矩阵与信道编码(channel coding, CC)理论有机地结合到一起,提出了基于低密度奇偶校验(low density paritycheck, LDPC)码的确定性测量矩阵,实现了稀疏测量矩阵条件下对图像的正确恢复.但在生成LDPC码测量矩阵时所采用的随机选择非零元素位置的*国家自然科学基金(批准号: 61401513)资助的课题.通信作者. E-mail: 2017中国物理学会Chinese Physical Society http:/09070

10、3-1万方数据物理学报Acta Phys. Sin. Vol. 66, No. 9 (2017) 090703方法,有一定概率产生具有短环结构的测量矩阵,增加迭代次数导致重构性能的鲁棒性差.文献12,13基于有限域生成两类LDPC测量矩阵,在图像的恢复中得到了较好的效果.但是该方法并没有考虑到LDPC码所具有的特定结构,导致构造复杂度较高.本文提出了一种基于渐进添边(progressiveedge-growth, PEG)的准循环CS时延估计算法,基于PEG思想所构造的LDPC测量矩阵不仅具有准循环结构,且对应的因子(Tanner)图中具有最大的环数.在稀疏重构的过程中利用正交匹配追踪(ort

11、hogonal matching pursuit, OMP)算法14得到多径时延的无偏估计.通过仿真实验将本文算法与高斯随机测量矩阵、随机LDPC测量矩阵进行对比,并对这三种测量矩阵的存储数据量以及计算复杂度进行分析,实验结果体现了本文所提出算法的优越性.2数学模型2.1 CS理论模型在利用CS理论对时延进行估计的过程中,设X是长度为N的时域稀疏信号,通过线性测量后得到长度为M的观测信号Y 2 RM, W表示测量误差.信号的观测向量模型为Y = HCSX +W; (1)其中HCS是测量矩阵,矩阵维度为M N,对信号的时延进行估计的过程就是通过Y对X进行重构的过程.当W = 0时,该问题是精确信

12、号重构问题;当W = 0时,该问题为信号估计问题.由于X是稀疏信号,重构的数学表达式为minX0;Y = HCSX +W:(2)对(2)式进行求解得到接收信号的时延估计.由于(2)式的求解是一个NP-Hard15问题,可以将其转化为1范数的线性规划问题,minX1;Y = HCSX +W:(3)在解决(3)式的1范数问题时,常用的算法为OMP算法、基追踪(basic pursuit, BP)算法等.这类算法通过迭代来估计向量X. OMP算法的核心步骤为:在第k次迭代中,将Y正交地投影到HCS的每一列(原子)上,Yk = (HTCSHCS) 1HTCSY; (4)挑选出Yk最大值所对应的原子存入

13、 HCS.并根据(5)式计算残差rk,如果jrkj 8时,本文算法与随机LDPC测量矩阵的正确重构概率高于高斯随机测量矩阵.本文算法由于引入PEG算法的思想,相比于随机LDPC测量矩阵减少了Tanner图中短环的数量,因此在Lp较大时,具有更胜一筹的性能.0 2 4 6 8 10 12 14 16 1800.20.40.60.81.0多径数目/条正确重构概率高斯随机测量矩阵随机LDPC测量矩阵本文算法图4不同算法正确重构概率随多径数目变化对比图Fig. 4. The variation of the probability of correct re-construction with the

14、 number of multipath contrast ofdierent algorithms.仿真三在不同测量矩阵维度, SNR = 10 dB的条件下进行仿真,分别绘制本文算法在维度为64 512, 64 1024, 128 1024时正确重构概率随多径数目变化的曲线,仿真结果如图5所示.可以看出在仿真条件一定的条件下, 128 1024维的测量矩阵有着最好的重构效果.因此正确重构概率的下降过程随测量矩阵维度的增加而滞后.0 5 10 15 20 2500.20.40.60.81.0多径数目/条正确重构概率64x512维64x1024维128x1024维图5不同矩阵维度条件下本文算法

15、正确重构概率随多径数目变化对比图Fig. 5. The variation of the probability of correct re-construction with the number of multipath contrast ofdierent matrix dimensions.仿真四在矩阵维度为64 512, SNR =10 dB的条件下,根据(19)式,计算本文算法中测量矩阵的相关值.(HCS) = max1i=jnjHCSi;HCSjjHCSi2HCSj2; (19)其中 2为向量的2范数.本文算法中测量矩阵的相关值随列重的变化如图6所示,可以看出相关值随列重的增加而

16、减小.根据文献19,可知测量矩阵相关值越小,重构精度越高.根据表1可知列重的增加会导致存储空间与计算复杂度的增加,因此为平衡重构精度与存储空间及计算复杂度之间的关系,本文算法中测量矩阵的列重取值设置为8.0 1 2 3 4 5 6 7 8 9 1000.20.40.60.81.0列重相关值图6本文算法测量矩阵相关值随列重变化示意图Fig. 6. The variation of the measurement matrix cor-relation value with the column weight of the algorithmin this paper.5存储空间与计算复杂度分析假

17、设测量矩阵的维度为M N,随机LDPC测量矩阵与本文测量矩阵的列重均为!j.由于高斯随机测量矩阵中的每个元素均为随机数,因此高斯随机测量矩阵的存储空间为M N, LDPC类测量矩阵的每行仅有!j个元素取值为1,其余元素为0,因此LDPC类测量矩阵的存储空间为N !j.在采用CS算法估计时延的过程中,计算复杂度分成两部分,即测量矩阵的生成与信号的重构.在采用OMP算法重构信号的过程中,计算复杂度主要包括两部分:计算相关值u,复杂度为O(MN);更新余量,复杂度为O(3M + 2),为正确重构全部时延,算法需经过Lp次迭代.高斯随机测量矩阵只需要生成维度为M N的随机数,因此算法复杂度为OMNLp

18、 + 2Lp + 3Lp(Lp + 1)2 M;090703-6万方数据物理学报Acta Phys. Sin. Vol. 66, No. 9 (2017) 090703由于随机LDPC测量矩阵在生成过程中,在每一列随机选取!j个非零元素,因此算法复杂度为O!jNLp + 2Lp + 3Lp(Lp + 1)2 !j;本文算法重构过程的复杂度为O!jNLp + 2Lp + 3Lp(Lp + 1)2 !j;生成测量矩阵的复杂度为O(2ct+ 2).表1列出了三种算法计算复杂度与存储空间的对比.本文算法相比于高斯随机测量矩阵降低了存储空间,与随机LDPC测量矩阵相比,在存储空间相同的条件下,以较小复杂

19、度的代价得到了性能的较大提升.表1算法计算复杂度与存储空间对比表Table 1. The comparison of the algorithm complexity and storage space.算法名称计算复杂度存储空间高斯随机测量矩阵O(MNLp + 2Lp + 3Lp(Lp + 1)2 M)M N随机LDPC测量矩阵O(!jNLp + 2Lp + 3Lp(Lp + 1)2 !j)!j N本文算法O(!jNLp + 2Lp + 3Lp(Lp + 1)2 !j + 2ct+ 2)!j N6结论在时延估计问题中,现有基于LDPC码的测量矩阵具有在少量数据存储量的条件下较好的估计性能,但

20、在测量矩阵的生成过程中,由于随机选择非零元素位置,导致Tanner图中短环的出现,影响重构效果.针对该问题,本文首先引入了PEG算法有效减少了Tanner图中短环的存在,然后基于准循环结构构造测量矩阵,实现了少量数据量条件下无偏时延估计.在相同多径数目的条件下比高斯随机测量矩阵和随机LDPC测量矩阵正确重构概率更高.同时给出了数据存储量与计算复杂度分析,仿真结果表明该算法性能优越、稳定可靠.参考文献1 Zhang Q F, Huang J G, Xie Y Q 1995 Acta Acust. 20211 (in Chinese) 张群飞,黄建国,谢一清1995声学学报20 2112 Li J

21、 2011 Electron. Meas. Technol. 34 73 (in Chinese)李剑2011电子测量技术34 733 Donoho D L 2006 IEEE Trans. Inform. Theory 52 12894 Ning F L, He B J, Wei J 2013 Acta Phys. Sin. 62 174212(in Chinese) 宁方立,何碧静,韦娟2013物理学报621742125 Shen Z B, Dong C X, Huang L, Zhao G Q 2014 J. Elec-tron. Inform. Technol. 36 2935 (in

22、 Chinese) 沈志博,董春曦,黄龙,赵国庆2014电子与信息学报36 29356 Leng X D, Ba B, Lu Z Y, Wang D M 2016 Acta Phys.Sin. 65 210701 (in Chinese) 冷雪冬,巴斌,逯志宇,王大鸣2016物理学报65 2107017 Wang Q, Li J, Shen Y 2013 Acta Electron. Sin. 41 2041(in Chinese) 王强,李佳,沈毅2013电子学报41 20418 Candes E J, Tao T 2005 IEEE Trans. Inform. Theory51 4203

23、9 DeVore R A 2007 J. Complexity 23 91810 Xia P F, Zhou S L, Giannakis G B 2005 IEEE Trans.Inform. Theory 51 190011 Dimakis A G, Smarandache R, Vontobel P O 2012 IEEETrans. Inform. Theory 58 309312 Xia S T, Liu X J, Jiang Y 2015 IEEE Trans. SignalProcess. 63 101713 Mohades A, Tadaion A A 2016 IET Sig

24、nal Process 1016814 Elad M 2008 IEEE Trans. Signal Process. 55 569515 Hochba D S 1997 ACM Sigact News 28 4016 Tillmann A M, Pfetsch M E 2014 IEEE Trans. Inform.Theory 60 124817 Gao Y, Peng J G, Yue S G, Zhao Y 2015 J. FunctionSpaces 205 57985318 Sun J M 2016 Modern Radar 38 46 (in Chinese) 孙晶明2016现代

25、雷达38 4619 Dang K, Ma L H, Tian Y, Zhang H W, Ru L, Li X B2015 J. Xidian Univ. 42 186 (in Chinese) 党骙,马林华,田雨,张海威,茹乐,李小蓓2015西安电子科技大学学报(自然科学版) 42 186090703-7万方数据物理学报Acta Phys. Sin. Vol. 66, No. 9 (2017) 090703A quasi-cyclic compressed sensing delay estimationalgorithm based on progressive edge-growth L

26、eng Xue-Dong Wang Da-Ming Ba Bin Wang Jian-Hui(The PLA Information Engineering University, Zhengzhou 450001, China)( Received 15 December 2016; revised manuscript received 3 February 2017 )AbstractTime delay estimation (TDE) is a hot research topic in wireless location technology. Compressed sensing

27、 (CS)theory has been widely applied to image reconstruction and direction of arrival estimation since it was proposed in2004. The sparse model can be constructed in time domain for estimating the time delay by using the CS theory. Themeasurement matrix plays a crucial role in the processing of signa

28、l reconstruction which is the core problem of CS theory.Therefore the research in the measurement matrix has becomes a hotspot in recent years. The existing measurementmatrix is mainly divided into two categories, i.e., random measurement matrix and deterministic measurement matrix.The performance o

29、f random measurement matrix has bottlenecks. Firstly, because of the redundant measurement matrixdata, the generation and storage of the random number put forward a high requirement for hardware. Secondly therandom matrix can only satisfy the restricted isometry property in a statistical sense. The

30、research of the deterministicmeasurement matrix is of great value under this background. The parity check matrix of low density parity check(LDPC) code has good performance in CS theory. However, the method of randomly selecting non-zero element positionhas a certain probability to generate a measur

31、ement matrix with a short loop structure during generating LDPC codemeasurement matrix. The robustness of the reconstruction performance decreases with the increase of iteration times.A novel quasi-cyclic CS algorithm based on progressive edge-growth is constructed to estimate the time delay.The pur

32、pose of this article is to deal with the need to store a large number of data in existing measurement matrixduring time delay, by using the CS theory. The algorithm presented here can achieve TDE in a high precision. First,the theoretical bridge between CS and the maximum likelihood decoding is esta

33、blished. And the design criterion ofmeasurement matrix based on the LDPC code is derived. The sparse measurement matrix with quasi-cyclic structureis constructed by introducing the idea of progressive edge-growth. Finally, the orthogonal matching pursuit algorithmis used to estimate the time delay.

34、Furthermore, the computational complexity of the algorithm and the data storageof the measurement matrix are analyzed theoretically. Simulations show that the correct reconstruction probability ofthe proposed approach is higher than those of the Gauss random matrix and random LDPC matrix under the s

35、amedimension. Compared with the random LDPC matrix, the proposed method can improve performance at the expenseof less complexity under the condition of the same data storage.Keywords: time delay estimation, compressed sensing, measurement matrix, progressive edge-growthPACS: 07.50.Qx, 07.05.Kf, 84.40.Ua, 89.70.Eg DOI: 10.7498/aps.66.090703* Project supported by the National Natural Science Foundation of China (Grant No. 61401513). Corresponding author. E-mail: 090703-8万方数据