多量测向量模型下基于贝叶斯检验的快速OMP算法研究

李少东 陈文峰 杨 军 马晓岩



多量测向量模型下基于贝叶斯检验的快速OMP算法研究

李少东*陈文峰 杨 军 马晓岩

(空军预警学院三系 武汉 430019)

目前多量测向量(Multiple Measurement Vectors, MMV)模型的稀疏重构算法存在两个问题：计算复杂度高和当重构的支撑集存在冗余时无法有效剔除。为同时提高MMV模型的重构效率和重构精度，该文提出一种MMV模型下基于贝叶斯检验的快速正交匹配追踪(Fast Orthogonal Matching Pursuit based on Bayesian Testing, FOMP-BT)算法。首先，通过新原子组选和warm start求逆的思想来减少算法总的迭代次数以及每次迭代的运算量，以提高算法的重构效率；其次，利用贝叶斯检验的思想剔除冗余支撑集以提高重构精度；最后对所研究的算法从参数选择以及计算复杂度等方面进行了理论分析。仿真结果表明，所提算法具有重构精度高、速度快以及对噪声有较好的鲁棒性等优势。

多量测向量模型；快速正交匹配追踪算法；迭代次数；贝叶斯检验

1 引言

作为一种信息获取的新思路，压缩感知(Compressive Sensing, CS)[1]自提出至今，理论日趋完善[2]。由于CS将采样端的压力“转移”到解码端，因此压缩量测条件下的稀疏重构是CS的关键研究问题之一。多量测向量(Multiple Measurement Vector, MMV)问题作为CS的一个延伸发展方向，也引起了众多学者的关注[3,4]。MMV模型是指不同矢量之间具有相同支撑集结构(对稀疏值的幅度不加约束)的模型，而对这种联合稀疏特征的利用可提高重构精度、缩短重构时间[5]。因此，在生物特征识别[6]、图像处理[7]、到达角估计[8]、空时自适应处理[9]以及雷达成像[10,11]等领域，众多学者找到并构建了共享支撑集的MMV模型，取得了比单量测向量(Single Measurement Vector, SMV)模型更好的稀疏重构效果和抗噪性能。文献[12]从信息论的角度揭示了MMV问题中支撑集恢复性能的边界条件，奠定了使用MMV模型可改善重构性能的理论基础。因此研究压缩量测数据条件下对MMV问题的稀疏重构具有重要意义。

文献[13]对较早时期MMV问题的重构算法进行了综述与分析，并指出了每种算法的优缺点，给出了CS-MMV模型的发展趋势。而近几年求解MMV问题的稀疏重构算法主要分为两大类：一是基于贪婪思想的重构方法，文献[14]将DOA估计建模为MMV模型，基于导向矢量构成的冗余字典高度相关这一事实，对OMPMMV算法[4]进行了改进，使新算法可在冗余字典相关的条件下重构，但是并未考虑算法的快速实现问题；文献[15]将5种典型重构SMV问题的算法拓展为求解MMV问题的算法，利用渐近RIP性质，推导了5种算法最优稀疏表示的充分条件，但是该文并未讨论噪声影响时的重构精度问题。总结此类算法可知，将贪婪算法思想拓展到求解MMV问题后，虽然在重构性能上比SMV条件下有所改善，但是贪婪算法固有的低信噪比下重构精度低、求逆运算量大的问题并未得到有效解决；二是基于稀疏贝叶斯学习(Sparse Bayesian Learning, SBL)理论的重构算法研究，文献[16]利用子空间罚函数对MSBL进行改进，精度得到了提高；文献[17]在进行DOA估计时，考虑了网格失配的问题，将联合稀疏模型转换为块稀疏表示后，提出了OGBSBL算法，可在网格失配时获得更好的DOA估计精度。但是此类算法受SBL的计算量影响，计算效率一直是值得进一步研究的问题。总结目前的研究成果可知，虽然有很多针对MMV问题的重构算法，但如何更好地利用联合稀疏这一结构先验信息，并从CS获得的压缩量测数据中快速鲁棒地重构MMV问题依然值得进一步研究。

针对上述问题，本文提出了一种MMV模型下基于贝叶斯检验的快速正交匹配追踪(Fast Orthogonal Matching Pursuit based on Bayesian Testing, FOMP-BT)算法。该算法主要的创新体现在两个方面：重构效率和估计精度。首先，在提高算法的重构效率方面采用了两种策略，一是减少算法总的迭代次数，即在每次迭代选择新原子时，采用选择一组原子(原子是指感知矩阵的某一列)代替原OMPMMV算法[4]每次只选择一个原子的选择机制以减少总的迭代次数；二是降低每次迭代的计算量，由于重构矩阵(由各次迭代获得的原子合成的矩阵)每次迭代只增加一少部分的新原子，因此可采用“warm start”[18]的方式，充分利用前一次迭代获得的重构原子信息，通过递归方法实现重构矩阵的求逆运算，从而降低求逆运算量；其次，在提高估计精度方面主要通过提高支撑集估计精度来实现，即利用贝叶斯检验的思想剔除冗余支撑集。最后，对所研究的算法从参数选择、计算复杂性等方面进行了理论分析。此外，本文还构建了基于贪婪类算法的多向量重构算法的统一框架。将本文算法应用到图像处理以及到达角估计等场合，具有较广泛的应用前景。

2 MMV压缩量测信号模型

首先对MMV问题进行建模，噪声条件下MMV模型可表示为

文献[3]对MMV模型的稀疏结构进行了详细的说明，本文引用其假设条件，描述如下：

上述构建的模型又称之为联合稀疏模型。MMV模型对稀疏点的约束是其支撑集位置不随列发生变化。为使模型更加合理，假设每一列的非零稀疏点幅度服从常用的伯努利高斯(Bernoulli Gauss, BG)模型。这里对MMV BG模型进行简单介绍，为下文的支撑集贝叶斯检验奠定基础。

在对模型稀疏点取非零值的概率和大小约束之后，下一步就是对其进行位置约束，为体现随机性，本文假设信号非零行的位置是随机的。至此，完成了压缩MMV模型构建，下面针对此模型进行重构算法介绍。

3 FOMP-BT算法

>3.1 算法基本思想

由文献[15]可知，求解MMV问题的贪婪类算法可由SMV的算法拓展得到，因此求解MMV问题的算法基本迭代格式是与SMV条件下一致的[15]。本文所提的FOMP-BT算法则是在OMPMMV算法[4]的基础上，对重构效率和估计精度两个方面进行改进，其算法流程如表1所示。

表1 FOMP-BT算法

从表1可以看出FOMP-BT算法的基本思想包括多原子识别、递归投影以及残差更新3个步骤，其中迭代项为主要的计算量来源。而FOMP-BT算法对运算量的改进体现在前两个步骤上，即多原子识别减少总的迭代次数，递归投影降低每次迭代求逆的运算量。此外FOMP-BT算法通过贝叶斯检验剔除冗余支撑集来减小误差。下面重点对FOMP- BT的具体实现进行详细分析。

3.2 算法实现步骤

首先分析如何降低算法的运算量，以第次迭代为例说明问题。

完成新重构原子组选后，便需要进行投影计算。令第次迭代得到的重构矩阵为，那么有，其中为第次迭代得到的重构矩阵，重构矩阵包含两部分：一是前次迭代得到的；二是本次迭代时得到的新重构原子组。进行投影计算时，有

利用分块求逆引理[18]，将式(5)的计算等价转换为

相同的递归策略可以一直延续到算法迭代结束。至此，完成了对算法降低运算量部分的介绍，下面分析如何提高新算法的噪声鲁棒性。

同理依据贝叶斯公式以及式(10)，式(12)，可求得

得到参数的估计值后，需要进一步推导MMV模型下的非零行贝叶斯检验模型。

MMV条件下，当非零行数有冗余时，为正确识别真实的非零行数(剔除虚假冗余项)，本文采取贝叶斯模型对非零行进行检验。实际上，假设的其他非零行是已知，而检验的第行时，即对的检验对应式(16)所示事件：

令

那么有

那么有

对式(22)取对数并化简，可得到：

至此即完成对支撑集的检验。依次对所有的粗支撑集进行检验后可得到最终的检验结果。

从FOMP-BT算法的推导过程中可以看出，该算法在沿袭贪婪类算法的基本迭代框架(新原子识别、投影和残差更新)基础上，从降低运算量和提高精度的角度进行了创新。

3.3 参数设置

FOMP-BT算法待确定的参数主要有两个：迭代停止条件与稀疏度预置值。下面对其选择原则进行分析。

(1)迭代停止条件的选择：目前关于贪婪类算法的迭代停止条件主要有两种类型，一是在稀疏度已知条件下，迭代次。由于稀疏度先验在实际情况中不易获得，因而产生了稀疏度预估的思想，即利用量测长度、信号维度、稀疏度的关系预置稀疏度。文献[21]提出了自适应稀疏度估计的思想，但其将稀疏度的先验转换为RIC常数的先验，实际中RIC常数往往也是未知的。所以本文认为稀疏度自适应的重点应落脚于怎么将一个不合理的甚至是冗余的稀疏度经过算法处理之后逼近真实稀疏度。

第2种典型是利用残差作为迭代停止条件。即在估计过程当中，残差是逐步变小的，当残差变大时，说明估计已经充分，剩余的为噪声估计，因而出现变大的情况。此时需要噪声的方差作为先验，但是由于方差估计一般会存在误差，因此也会造成最终的支撑集出现冗余。

4 算法性能分析

本文降低运算量和提高精度的思想适用于贪婪类的大部分算法，图1为MMV模型下贪婪类算法的统一框架。从图1可以看出，本文思想适用于识别和投影处理，具有较强的可移植性。

图1 基于贪婪类算法的MMV算法统一描述框图

此外，通过定量分析FOMP-BT算法的计算量来体现其优势，下面分别从识别步和投影步出发，计算第次循环时算法的运算量。以一次乘法或者是加法的运算量为一个运算量单位，重点对比FOMP-BT算法与OMPMMV算法的计算量。首先计算FOMP-BT计算量。

在FOMP-BT算法中，主要计算量集中于新原子识别步和投影步。而一次迭代中新原子识别步的计算量为。在投影步时计算量主要集中于的计算。的维度是，因此对其求逆的计算量为。维度是，其计算量为，假设经过次迭代，那么算法总运算量约为

其次计算OMPMMV算法的计算量。

OMPMMV算法的主要计算量同样是集中于新原子识别步和投影步。由于不存在快速操作，假设一共迭代0次，其总的计算量约为

5 仿真与分析

首先对噪声添加方式和重构质量指标进行说明。信噪比定义为

其次，本文使用相对重构误差来衡量重构质量，其定义为

仿真1 冗余稀疏度对重构结果的影响 为比较冗余稀疏度对重构结果的影响，仿真参数设置如下：测量值=300，信号维度为=500，真实稀疏度=12(即MMV模型有12个非零行)，向量数为10，每一列向量非零值的幅度服从方差为1的高斯分布。蒙特卡罗次数为100，信噪比为3 dB。冗余稀疏度从15增加到42，步长为3。分别与OMPMMV[4]以及SCoSaMP[15]算法作对比，图2为仿真结果。

夫妻之间关系非常糟糕，因为妻子长期积怨而常年争吵不休。起因是结婚前，妻子听说她丈夫有十亩地和一份收入颇丰的工作。丈夫因妻子生了女儿而不是儿子十分生气，所以他照顾妻子时态度恶劣。

图2 不同算法重构误差对比

从图2对比可以看出，随着冗余稀疏度变大，3种算法的误差都相应增大，CoSaMP算法由于每次迭代时都选择稀疏度的2倍个支撑集原子，因此当稀疏度存在冗余时，其错误重构的概率大于OMPMMV，性能劣于OMPMMV算法；而本文算法采用了贝叶斯检验剔除冗余支撑集，因此在相同的稀疏度条件下，重构误差最小。从真实稀疏度为6和为12时算法误差对比可以看出，当余稀疏度越大，本文剔除虚假支撑的能力越强。仿真验证了本文算法对冗余稀疏度剔除的有效性。

仿真2 抗噪性能对比 为考察噪声对算法精度的影响，将算法停止条件变为，仿真时取输入信噪比为3~18 dB，其他条件与仿真1相同，仿真时分别与MFOCUSS[3], OMPMMV[4]以及CoSaMP[15]算法进行对比，结果如图3所示。

图3 不同信噪比条件下的重构精度对比

从图3中可以看出，随着信噪比的提高，各类算法的重构误差呈现递减趋势。从总体趋势看，本文算法受噪声影响与MFOCUSS基本相同。说明本文算法在经过支撑集剔除步骤之后，用于重构的支撑集最接近于信号的真实支撑集，参与最终重构的支撑集中包含的虚假成分最少，因而精度较高；而其他算法在重构时受到噪声的影响，会存在冗余的稀疏度，因此影响了算法在噪声条件下重构的精度。仿真验证了本文算法在低信噪比条件下依然具有较好的重构能力。

仿真3 不同算法重构效率对比 本仿真主要用于对比不同算法的运行效率。仿真参数设置如下：取信号维度为变量，范围是500~900，步长为50，量测值个数取为信号维度的0.6倍，即，信噪比为3 dB，蒙特卡洛次数为100，分别计算FOMP-BT, OMPMMV, SCoSaMP与MFOCUSS算法的运行时间，结果如图4所示。

图4 不同算法的运行时间比较

从图4可以看出，由于MFOCUSS算法存在大矩阵求逆运算，随着信号维度的增加其运行时间增加的最快；SCoSaMP算法由于每次迭代时都需要对个原子的重构矩阵进行求逆运算，因此其计算量高于OMPMMV和FOMP-BT；本文算法由于采取了减少迭代次数和优化每次迭代时逆矩阵的运算量，因此运算时间最短。仿真验证了本文算法的高重构效率优势。

6 结束语

MMV模型能够提供更多的先验信息，对此信息的利用可用于提高重构概率。本文针对目前求解MMV问题的算法复杂度高以及低信噪比条件下存在冗余支撑集的问题，提出了FOMP-BT算法，该算法的主要优势在于两个方面：(1)通过减少算法总的迭代次数和降低每次迭代的运算量的方式，使得算法的重构效率有了较大的提高；(2)利用贝叶斯检验的思想，可剔除冗余支撑集，由于剔冗的支撑集更加接近真实支撑集结构，因此可提高重构精度。在实际应用时，需要结合背景，寻找恰当的MMV模型场合。将本文算法应用到ISAR/SAR的距离向联合成像是课题组下一步工作的研究重点。

[1] DONOHO D L. Compressed sensing[J]., 2006, 52(4): 1289-1306.

[2] ELDAR Y C. Sampling Theory Beyond Band Limited Systems[M]. Cambridge University Press, 2015: 1-8. doi: http: //dx.doi.org/10.1017/CBO9780511762321.

[3] SHANE F C, BHASKAR D R, KJERSTI E,Sparse solutions to linear inverse problems with multiple measurement vectors[J]., 2005, 53(7): 2477-2488.

[4] CHEN Jie and HUO Xiaoming. Theoretical results on sparse representations of multiple-measurement vectors[J]., 2006, 54(12): 4634-4643.

[5] 陈一畅, 张群, 陈校平, 等. 多重测量矢量模型下的稀疏步进频率SAR成像算法[J]. 电子与信息学报, 2014, 36(12): 2987-2993. doi: 10.3724/SP.J.1146.2013.01831.

CHEN Yichang, ZHANG Qun, CHEN Xiaoping,Imaging algorithm of sparse stepped fequency SAR based on multiple measurement vectors model[J].&, 2014, 36(12): 2987-2993. doi: 10.3724/SP.J.1146.2013.01831.

[6] HEKHAR S, PATEL V M, NASRABADI N M ,. Joint sparse representation for robust multimodal biometrics recognition[J]., 2014, 36(1): 113-126.

[7] 李志林, 陈后金, 李居朋, 等. 一种有效的压缩感知图像重建算法[J]. 电子学报, 2011, 39(12): 2796-2800.

LI Zhilin, CHEN Houjin, LI Jupeng,. An eficient algorithm for compressed sensing image reconstruction[J]., 2011, 39(12): 2796-2800.

[8] ZHAO Tan and NEHORAI A. Sparse direction of arrival estimation using co-prime arrays with off-grid targets[J]., 2014, 21(1): 26-29.

[9] 王泽涛, 段克清, 谢文冲, 等. 基于SA-MUSIC 理论的联合稀疏恢复STAP算法[J]. 电子学报, 2015, 43(5): 846-853.

WANG Zetao, DUAN Keqing, XIE Wenchong,. A joint sparse recovery STAP method based on SA-MUSIC[J]., 2015, 43(5): 846-853.

[10] FANG Jian, XU Zongben, ZHANG Bingchen,. Compressed sensing SAR imaging with multilook processing [OL]. http://arxiv.org/abs/1310.7217v1, 2013.

[11] TAO Yu, ZHANG Gong, and ZHANG Jindong. Guaranteed stability of sparse recovery in distributed compressive sensing MIMO Radar[J]., 2015, Article ID 421740: 1-10.

[12] JIN Yuzhe and RAO B D. Support recovery of sparse signals in the presence of multiple measurement vectors[J]., 2013, 59(5): 3139-3156.

[13] 王法松, 张林让, 周宇. 压缩感知的多重测量向量模型与算法分析[J]. 信号处理, 2012, 28(6): 785-792.

WANG Fasong, ZHANG Linrang, and ZHOU Yu. Multiple measurement vectors for compressed sensing: model and algorithms analysis[J]., 2012, 28(6): 785-792.

[14] GUAN Gui, WAN Qun, and ADACHI F. Direction of arrival estimation using modified orthogonal matching pursuit algorithm[J]., 2011, 6(22): 5230-5234.

[15] BLANCHARD J D, CERMAK M, HANLE D,. Greedy algorithms for joint sparse recovery[J]., 2014, 62(7): 1694-1704.

[16] YE J C, KIM J M, and BRESLER Y. Improving M-SBL for joint sparse recovery using a subspace penalty[OL]. http:// arxiv:1503.06679v1, 2015.

[17] ZHANG Y, YE Z F, XU X,. Off-grid DOA estimation using array covariance matrix and block-sparse Bayesian learning[J]., 2014, 98: 97-201.

[18] 张贤达. 矩阵分析与应用(第2版)[M]. 北京: 清华大学出版社, 2013: 54-64.

ZHANG Xianda. Matrix Analysis and Applications (Second Edition)[M]. Beijing: Tsinghua University Press, 2013: 54-64.

[19] ZHANG Jingxiong and YANG Ke. Informational analysis for compressive sampling in radar imaging[J].2015, 15(4): 7136-7155. doi: 10.3390/s150407136.

[20] 甘伟, 许录平, 苏哲, 等. 基于贝叶斯假设检验的压缩感知重构[J]. 电子与信息学报, 2011, 33(11): 2640-2646. doi: 10. 3727/SP.J.1146.2011.00151.

GAN Wei, XU Luping, SU Zhe ,. Bayesian hypothesis testing based recovery for compressed sensing[J].&, 2011,33(11): 2640-2646. doi: 10.3727/SP.J.1146.2011.00151.

[21] 杨成, 冯巍, 冯辉, 等. 一种压缩采样中的稀疏度自适应子空间追踪算法[J]. 电子学报, 2010, 38(8): 1914-1917.

YANG Cheng, FENG Wei, FENG Hui,. A sparsity adaptive subspace pursuit algorithm for compressive sampling[J]., 2010, 38(8): 1914-1917.

Fast OMP Algorithm Based on Bayesian Test for Multiple Measurement Vectors Model

LI Shaodong CHEN Wenfeng YANG Jun MA Xiaoyan

(,430019,)

There are two issues in the Sparse Reconstruction (SR) algorithm of Multiple Measurement Vectors (MMV). One is the high computation complexity and the other is that redundant support set can not be effectively removed. In order to improve the efficiency and accuracy of SR algorithm simultaneously for MMV model, a Fast Orthogonal Matching Pursuit algorithm based on Bayesian Test (FOMP-BT) is presented in this paper. Firstly, the total number of iterations and the computation of each iteration are reduced through the new atomic group selection and warm start matrix inversion, thus the efficiency of the algorithm is improved. Secondly, using the idea of the Bayesian test to eliminate redundant support set, the accuracy of reconstruction is improved. Finally, the theoretical analysis of the algorithm is carried out from the aspects of parameter selection and computation complexity. The simulation results show that the proposed algorithm has the advantages of high accuracy, fast speed and good robustness to noise.

Multiple measurement vectors model; Fast Orthogonal Matching Pursuit (FOMP) algorithm; Number of iterations; Bayesian test

TN957.52

A

1009-5896(2016)07-1731-07

10.11999/JEIT151131

2015-10-10；改回日期：2016-02-25；网络出版：2016-04-07

李少东 liying198798@126.com

李少东： 男，1987年生，博士，研究方向为压缩感知理论在雷达成像中的应用.

陈文峰： 男，1989年生，博士，研究方向为雷达目标检测与识别.

杨 军： 男，1973年生，副教授，硕士生导师，研究方向为雷达目标检测、现代信号处理.

马晓岩： 男，1962年生，教授，博士生导师，研究方向为雷达目标检测与识别.