《多量测向量模型下基于贝叶斯检验的快速omp算法研究-李少东.pdf》由会员分享，可在线阅读，更多相关《多量测向量模型下基于贝叶斯检验的快速omp算法研究-李少东.pdf（7页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第38卷第7期 电子与信息学报 V0138No72016年7月 Journal of Electronics&Information Technology Jul2016；=jEI-_|=-=日=jEl日_lI=jtI=_，_l；l=EazId_l一一l一多量测向量模型下基于贝叶斯检验的快速OMP算法研究李少东4 陈文峰 杨军 马晓岩(空军预警学院三系 武汉430019)摘要：目前多量测：量(Multiple Measurement Vectors，MMV)模型的稀疏重构算法存在两个问题：计算复杂度高和当重构的支撑集存在冗余时无法有效剔除。为同时提高MMV模型的重构效率和重构精度，该文提出一种
2、MMV模型下基于贝叶斯检验的快速正交匹配追踪(Fast Orthogonal Matching Pursuit based on Bayesian Testing，FOMPBT)算法。首先，通过新原子组选和warm start求逆的思想来减少算法总的迭代次数以及每次迭代的运算量，以提高算法的重构效率；其次，利用贝叶斯检验的思想剔除冗余支撑集以提高重构精度；最后对所研究的算法从参数选择以及计算复杂度等方面进行了理论分析。仿真结果表明，所提算法具有重构精度高、速度快以及对噪声有较好的鲁棒性等优势。关键词：多量测向量模型；快速正交匹配追踪算法；迭代次数；贝叶斯检验中图分类号：TN95752 文献标识
3、码：A 文章编号：1009-5896(2016)07-173107DOI：1011999JEITl51131Fast OMP Algorithm Based Oil Bayesian Test forMIlltiple Measurement Vectors ModelLI Shaodong CHEN Wenfeng YANG Jun MA Xiaoyan(The Third Department of Air Force Early Warning Academy，Wuhan 430019，China)Abstract：There are two issues in the Sparse R
4、econstruction(SR)algorithm of Multiple Measurement Vectors(MMV)One is the high computation complexity and the other is that redundant support set can not be effectivelyremovedIn order to improve the efficiency and accuracy of SR algorithm simultaneously for MMV model，a FastOrthogonal Matching Pursui
5、t algorithm based on Bayesian Test(FOMP-BT)is presented in this paperFirstly，the total number of iterations and the computation of each iteration are reduced through the new atomic groupselection and warm start matrix inversion，thus the efficiency of the algorithm is improvedSecondly，using theidea o
6、f the Bayesian test to eliminate redundant support set，the accuracy of reconstruction is improvedFinally，the theoretical analysis of the algorithm is carried out from the aspects of parameter selection and computationcomplexityThe simulation results show that the proposed algorithm has the advantage
7、s of high accuracy,fastspeed and good robustness to noiseKey words：Multiple measurement vectors model；Fast Orthogonal Matching Pursmt(FOMP)algorithm；Numberof iterations；Bayesian test1引言作为一种信息获取的新思路，压缩感知fCompressive Sensing，CS)1】自提出至今，理论日趋完善f2】o由于cs将采样端的压力“转移”到解码端，因此压缩量测条件下的稀疏重构是cs的关键研究问题之一。多量测向量(Mul
8、tiple MeasurementVector，MMV)问题作为CS的一个延伸发展方向，也引起了众多学者的关注13，到。MMV模型是指不同矢量之间具有相同支撑集结构(对稀疏值的幅度不加约束)的模型，而对这种联合稀疏特征的利用可提收稿日期：2015-10-10：改回日期：2016-0225i网络出版：2016-04-07+通信作者：李少东liyin9198798126corn高重构精度、缩短重构时间51。因此，在生物特征识别【61、图像处理【7】、到达角估计【8】、空时自适应处理【9以及雷达成像10,11】等领域，众多学者找到并构建了共享支撑集的MMV模型，取得了比单量测向量(Single Me
9、asurement Vector，SMV)模型更好的稀疏重构效果和抗噪性能。文献f12I从信息论的角度揭示了MMV问题中支撑集恢复性能的边界条件，奠定了使用MMV模型可改善重构性能的理论基础。因此研究压缩量测数据条件下对MMV问题的稀疏重构具有重要意义。文献f13对较早时期MMV问题的重构算法进行了综述与分析，并指出了每种算法的优缺点，给出了CSMMV模型的发展趋势。而近几年求解MMV万方数据电子与信息学报 第38卷问题的稀疏重构算法主要分为两大类：一是基于贪婪思想的重构方法，文献14将DOA估计建模为MMV模型，基于导向矢量构成的冗余字典高度相关这一事实，对OMPMMV算法4】进行了改进，使
10、新算法可在冗余字典相关的条件下重构，但是并未考虑算法的快速实现问题；文献15】将5种典型重构SMV问题的算法拓展为求解MMV问题的算法，利用渐近RIP性质，推导了5种算法最优稀疏表示的充分条件，但是该文并未讨论噪声影响时的重构精度问题。总结此类算法可知，将贪婪算法思想拓展到求解MMV问题后，虽然在重构性能上比SMV条件下有所改善，但是贪婪算法固有的低信噪比下重构精度低、求逆运算量大的问题并未得到有效解决；二是基于稀疏贝叶斯学习fSparse Bayesian Learning，SBL)理论的重构算法研究，文献161利用子空间罚函数对MSBL进行改进，精度得到了提高；文献f1 71在进行DOA估
11、计时，考虑了网格失配的问题，将联合稀疏模型转换为块稀疏表示后，提出了OGBSBL算法，可在网格失配时获得更好的DOA估计精度。但是此类算法受SBL的计算量影响，计算效率一直是值得进一步研究的问题。总结目前的研究成果可知，虽然有很多针对MMV问题的重构算法，但如何更好地利用联合稀疏这一结构先验信息，并从CS获得的压缩量测数据中快速鲁棒地重构MMV问题依然值得迸一步研究。针对上述问题，本文提出了一种MMV模型下基于贝叶斯检验的快速正交匹配追踪fFastOrthogonal Matching Pursuit based on BayesianTesting，FOMPBT)算法。该算法主要的创新体现在
12、两个方面：重构效率和估计精度。首先，在提高算法的重构效率方面采用了两种策略，一是减少算法总的迭代次数，即在每次迭代选择新原子时，采用选择一组原子(原子是指感知矩阵的某一列)代替原OMPMMV算法14】每次只选择一个原子的选择机制以减少总的迭代次数；二是降低每次迭代的计算量，由于重构矩阵(由各次迭代获得的原子合成的矩阵)每次迭代只增加一少部分的新原子，因此可采用“warm start”is】的方式，充分利用前一次迭代获得的重构原子信息，通过递归方法实现重构矩阵的求逆运算，从而降低求逆运算量；其次，在提高估计精度方面主要通过提高支撑集估计精度来实现，即利用贝叶斯检验的思想剔除冗余支撑集。最后，对所
13、研究的算法从参数选择、计算复杂性等方面进行了理论分析。此外，本文还构建了基于贪婪类算法的多向量重构算法的统一框架。将本文算法应用到图像处理以及到达角估计等场合，具有较广泛的应用前景。2 MMV压缩量测信号模型首先对MMV问题进行建模，噪声条件下MMV模型可表示为s=雪x+E (1)其中s为多量测向量构成的矩阵，x=，茁(2)，z(D1为待重构的多稀疏向量构成的矩阵，雪C胍。为字典。对式(1)的稀疏表示模型进行压缩量测有Y=AS=x+E (2)其中Y=秒(，可(引，!，(D为压缩的多量测向量矩阵，Ac搬为量测矩阵(Mp(Ho Iz，)。由贝叶斯公式可知：p(马。c p(z，IHl)p(H1) (
14、20)那么有p(zJ I甄)p(日1)p(z，I-o)p(Ho) (21)由式(13)可知，P(H1)=1一a，P(Ho)=a。因此只需要计算出p(zjl日i)(i=o，1)的概率分布即可求得式(21)的检验门限。观察式(19)可知，都包含6，。6i由两部分组成，其中V为高斯噪声，其方差为N Oa：甓；对于竺。剐(五。一戈zn)，由于殳。是五。的近似估计值，因此可认为x：。一戈。的误差较小，设置为子袅。那么有盯2以=厶。N：，ai2nbij+0，忙子i。代入式(21)，有万方数据第7期 李少东等：多量测向量模型下基于贝叶斯检验的快速OMP算法研究 1735南唧掣 ，对式(22)取对数并化简，可
15、得到：(乃一)2Th， (23)鼽氇=掣nf击至此即完成对支撑集的检验。依次对所有的粗支撑集进行检验后可得到最终的检验结果。从FOMPBT算法的推导过程中可以看出，该算法在沿袭贪婪类算法的基本迭代框架f新原子识别、投影和残差更新)基础上，从降低运算量和提高精度的角度进行了创新。33参数设置FOMPBT算法待确定的参数主要有两个：迭代停止条件与稀疏度预置值。下面对其选择原则进行分析。f11迭代停止条件的选择：目前关于贪婪类算法的迭代停止条件主要有两种类型，一是在稀疏度K已知条件下，迭代K次。由于稀疏度先验在实际情况中不易获得，因而产生了稀疏度预估的思想，即利用量测长度M、信号维度、稀疏度K的关系
16、预置稀疏度。文献211提出了自适应稀疏度估计的思想，但其将稀疏度的先验转换为mC常数的先验，实际中RIC常数往往也是未知的。所以本文认为稀疏度自适应的重点应落脚于怎么将一个不合理的甚至是冗余的稀疏度经过算法处理之后逼近真实稀疏度。第2种典型是利用残差作为迭代停止条件。即在估计过程当中，残差是逐步变小的，当残差变大时，说明估计已经充分，剩余的为噪声估计，因而出现变大的情况。此时需要噪声的方差作为先验，但是由于方差估计一般会存在误差，因此也会造成最终的支撑集出现冗余。f2)支撑集组选步长8的选择：算法采用了支撑集组选的模式，因而无需迭代砾次。由于e(，)=o(J-1)o(J1，为保证(，)是行满秩
17、的，那么必须满足：8LM，即8ML，同时sko，那么迭代次数L=min(ko，Ms)，此即为步长s与迭代次数的关系。可见当s=1时即为OMPMMV算法。4算法性能分析本文降低运算量和提高精度的思想适用于贪婪类的大部分算法，图l为MMV模型下贪婪类算法的统一框架。从图1可以看出，本文思想适用于识别和投影处理，具有较强的可移植性。此外，通过定量分析FOMPBT算法的计算量来体现其优势，下面分别从识别步和投影步出发，计算第J次循环时算法的运算量。以一次乘法或者是加法的运算量为一个运算量单位，重点对比FOMPBT算法与OMPMMV算法的计算量。首先计算FOMPBT计算量。在FOMPBT算法中，主要计算
18、量集中于新原子识别步和投影步。而一次迭代中新原子识别步的计算量为DN(2M一1)+(D1)=2MNDN。在投影步时计算量主要集中于西(，)的计算。fi的维度是8 X s，因此对其求逆的计算量为82(2M一1)+s(J一1)(2M一1)+s2。d，维度是(J一1)s，其计算量为M(2j一3)(歹一1)+s(j一1)(2M一1)，假设经过三次迭代，那么算法总运算量约为工CFoMP-BT=D(岣2+Mjs+2MNDN)J=1D(F+胁r+MNLD) (24)其次计算OMPMMV算法的计算量。OMPMMV算法的主要计算量同样是集中于新原子识别步和投影步。由于不存在快速操作，假设一共迭代次，其总的计算量
19、约为koCoMPMMv=o(J3+Mj2+2MNDN)j=lo(k4+朋端+MNkoD) (25)图1基于贪婪类算法的MMV算法统一描述框图引盟驴一一+盘慨一眩万方数据电子与信息学报 第38卷同时，由于Lk0，因此必有C,FoMPBTCoMPMMv，可见新算法在运算量上有很大的提高。5仿真与分析首先对噪声添加方式和重构质量指标进行说明。信噪比定义为SNR=1019Po-2 (26)其中P=IIAXII；(MD)为无噪信号的平均功率，盯2为噪声方差。其次，本文使用相对重构误差来衡量重构质量，其定义为err=10lg X一铫ux,l；1 (27)L ”1 J其中，戈为重构的信号，x为原始信号。仿真
20、1 冗余稀疏度对重构结果的影响为比较冗余稀疏度对重构结果的影响，仿真参数设置如下：测量值M-300，信号维度为N=500，真实稀疏度胎12(即MMV模型有12个非零行)，向量数为10，每一列向量非零值的幅度服从方差为l的高斯分布。蒙特卡罗次数为100，信噪比为3 dB。冗余稀疏度从15增加到42，步长为3。分别与OMPMMVf4I以及SCoSaMP15算法作对比，图2为仿真结果。从图2对比可以看出，随着冗余稀疏度变大，3种算法的误差都相应增大，CoSaMP算法由于每次迭代时都选择稀疏度的2倍个支撑集原子，因此当稀疏度存在冗余时，其错误重构的概率大于OMPMMV，性能劣于OMPMMV算法；而本文
21、算法采用了贝叶斯检验剔除冗余支撑集，因此在相同的稀疏度条件下，重构误差最小。从真实稀疏度为6和为12时算法误差对比可以看出，当余稀疏度越大，本文剔除虚假支撑的能力越强。仿真验证了本文算法对冗余稀疏度剔除的有效性。仿真2抗噪性能对比为考察噪声对算法精度的影响，将算法停止条4牛-变为l YA贾忙(ML)cr2，仿真时取输入信噪比为3-18 dB，其他条件与仿真1冗余稀疏度一+一FOMPBTK=12 一母一FOMPBTK-6一OMPMMK-12p OMPMMV(-6pSCoSa、IPK-12 一一SCoSaMPK-6相同，仿真时分别与MFOCUSSf引，OMPMMV4】以及SCoSaMP15】算法进
22、行对比，结果如图3所示。从图3中可以看出，随着信噪比的提高，各类算法的重构误差呈现递减趋势。从总体趋势看，本文算法受噪声影响与MFOCUSS基本相同。说明本文算法在经过支撑集剔除步骤之后，用于重构的支撑集最接近于信号的真实支撑集，参与最终重构的支撑集中包含的虚假成分最少，因而精度较高；而其他算法在重构时受到噪声的影响，会存在冗余的稀疏度，因此影响了算法在噪声条件下重构的精度。仿真验证了本文算法在低信噪比条件下依然具有较好的重构能力。仿真3不同算法重构效率对比本仿真主要用于对比不同算法的运行效率。仿真参数设置如下：取信号维度为变量，范围是500-900，步长为50，量测值个数取为信号维度的06倍
23、，即M=Io6Nl，信噪比为3 dB，蒙特卡洛次数为100，分别计算FOMPBT，OMPMMV，SCoSaMP与MFOCUSS算法的运行时问，结果如图4所示。从图4可以看出，由于MFOCUSS算法存在大矩阵求逆运算，随着信号维度的增加其运行时间增加的最快；SCoSaMP算法由于每次迭代时都需要对2K个原子的重构矩阵进行求逆运算，因此其计算量高于OMPMMV和FOMPBT：本文算法由于采取了减少迭代次数和优化每次迭代时逆矩阵的运算量，因此运算时间最短。仿真验证了本文算法的高重构效率优势。6结束语MMV模型能够提供更多的先验信息，对此信息的利用可用于提高重构概率。本文针对目前求解MMV问题的算法复
24、杂度高以及低信噪比条件下存在冗余支撑集的问题，提出了FOMPBT算法，该算法的主要优势在于两个方面：(1)通过减少算法总的迭代次数和降低每次迭代的运算量的方式，使信噪比(dB)一FOMPBT +SCoSaMP-o-OMPMMV一MFOC LSS信号维度一FOMPBT卜SCoSaMP一()、IP、I、1V一、IFOC LSS图2不同算法重构误差对比 图3不同信噪比条件下的重构精度对比 图4不同算法的运行时间比较万方数据第7期 李少东等：多量测向量模型下基于贝叶斯检验的快速OMP算法研究 1737得算法的重构效率有了较大的提高；(2)利用贝叶斯检验的思想，可剔除冗余支撑集，由于剔冗的支撑集更加接近
25、真实支撑集结构，因此可提高重构精度。在实际应用时，需要结合背景，寻找恰当的MMV模型场合。将本文算法应用到ISARSAR的距离向联合成像是课题组下一步工作的研究重点。参考文献1】4568】9【1011】DONOHO D LCompressed sensingJIEEE Transactionson Information Theory，2006，52(4)：12891306ELDAR Y CSampling Theory Beyond Band LimitedSystemsMCambridge University Press2015：18doi：http：dxdoiorg101017cB09
26、780511762321SHANE F C，BHASKAR D R，KJERSTI E，et a1Sparsesolutions to linear inverse problems with multiplemeasurement vectorsJIEEE Transactions on SignalProcessing，2005，53(7)：24772488CHEN Jie and HUO XiaomingTheoretical results on sparserepresentations of multiple-measurement vectorsJIEEETransaction
27、on Signal Processing，2006，54(12)：46344643陈一畅，张群，陈校平，等多重测量矢量模型下的稀疏步进频率SAR成像算法J电子与信息学报，2014，36(12)：29872993doi：103724SPJ1146201301831CHEN Yichang，zHANG Qun，CHEN Xiaoping，et a1Imaging algorithm of sparse stepped fequency SAR based onmultiple measurement vectors modelJ Journal ofElectuonics&Information
28、Technology，2014，36(12)：29872993doi：103724SPJ1146201301831HEKHAR S，PATEL V M，NASRABADI N M，et a1Jointsparse representation for robust multimodal biometricsrecognitionJIEEE Transactions on Pattern Analysis andMachine Intelligence，2014，36(1)：113126李志林，陈后金，李居朋，等一种有效的压缩感知图像重建算法J】电子学报，2011，39(12)：27962800
29、LI Zhilin，CHEN Houjin，LI Jupeng，et a1An eficientalgorithm for compressed sensing image reconstructionJActa Electronica Sinica，2011，39(12)：27962800ZHAO Tan and NEHORAI ASparse direction of arrivalestimation using co-prime arrays with off-grid targetsJIEEE Signal Processing Letters，2014，21(1)：2629王泽涛，
30、段克清，谢文冲，等基于SAMUSIC理论的联合稀疏恢复STAP算法J电子学报，2015，43(5)：846853WANG Zetao，DUAN Keqing，XIE Wenchong，et a1A jointsparse recovery STAP method based on SAMUSICJActaElectronica Sinica，2015，43(5)：846853FANG Jian，XU Zongben， ZHANG Bingchen， et a1Compressed sensing SAR imaging with multilook processingOLhttp：arxiv
31、orgabs13107217vl，2013TA0 YuZHANG Gongand ZHANG JindongGuaranteedstability of sparse recovery in distributed compressive sensingMIMO RadarJInternational Journal of Antennas andPropagation2015Article ID 421740：110JIN Yuzhe and RAO B DSupport recovery of sparse signalsin the presence of multiple measur
32、ement vectorsJIEEETransaction on Information Theory，2013，59(5)：31393156王法松，张林让，周宇压缩感知的多重测量向量模型与算法分析(J信号处理，2012，28(6)：785792WANG Fasong，ZHANG Linrang，and ZHOU YuMultiplemeasurement vectors for compressed sensing：model andalgorithms analysisJJournal of Signal Processing，2012，28(6)：785792GUAN Gui，WAN Q
33、un，and ADACHI FDirection of arrivalestimation using modified orthogonal matching pursuitalgorithmJInternational Journal of the Physical Sciences，2011，6(22)：52305234BLANCHARD J D，CERMAK M，HANLE D，et a1Greedyalgorithms for joint sparse recoveryJIEEE Transactions onSignal Processing，2014，62(7)：16941704
34、YE J C，KIM J M，and BRESLER YImproving MSBL forjoint sparse recovery using a subspace penaltyOLhttp：arxiv：150306679vl，2015ZHANG Y，YE Z F，XU X，et以Off-grid DOA estimationusing array covariance matrix and blocksparse BayesianlearningJSignal Processing，2014，98：97201张贤达矩阵分析与应用(第2版)M】北京：清华大学出版社，2013：5464ZH
35、ANG XiandaMatrix Analysis and Applications fSecondEdition)MBeijing：Tsinghua University Press，2013：5464ZHANG Jingxiong and YANG KeInformational analysis forcompressive sampling in radar imagingJSensors 2015，15(4)：71367155doi：103390s150407136甘伟，许录平，苏哲，等基于贝叶斯假设检验的压缩感知重构【J】电子与信息学报，2011，33(11)：26402646do
36、i：103727SPJ1146201100151GAN Wei，XU Luping，SU Zhe，et a1Bayesian hypothesistesting based recovery for compressed sensingJJournal olElectronics & Information Technology， 2011，33(11)：26402646doi：103727SPJ1146201100151杨成，冯巍，冯辉，等一种压缩采样中的稀疏度自适应子空间追踪算法J电子学报，2010，38(8)：19141917YANG Cheng，FENG Wei，FENG Hui，et a1A sparsityadaptive subspace pursuit algorithm for compressivesamplingJActa Electronica Sinica，2010，38(8)：19141917李少东： 男，1987年生，博士，研究方向为压缩感知理论在雷达成像中的应用陈文峰： 男，1989年生，博士，研究方向为雷达目标检测与识别杨军： 男，1973年生，副教授，硕士生导师，研究方向为雷达目标检测、现代信号处理马晓岩： 男，1962年生，教授，博士生导师，研究方向为雷达目标检测与识别阻呻M万方数据