压缩感知的重构算法

1、压缩感知的重构算法算法的重构是压缩感知中重要的一步，是压缩感知的关键之处。因为重构算法关系着信号能否精确重建，国内外的研究学者致力于压缩感知的信号重建，并且取得了很大的进展，提出了很多的重构算法，每种算法都各有自己的优缺点，使用者可以根据自己的情况，选择适合自己的重构算法，大大增加了使用的灵活性，也为我们以后的研究提供了很大的方便。压缩感知的重构算法主要分为三大类：1.组合算法2.贪婪算法3.凸松弛算法每种算法之中又包含几种算法，下面就把三类重构算法列举出来。组合算法：先是对信号进行结构采样，然后再通过对采样的数据进行分组测试，最后完成信号的重构。(1)傅里叶采样(FourierReprese

2、ntaior)(2)链式追踪算法(ChainingPursuit)(3)HHS追踪算法(HeavyHittersOnSteroidS)贪婪算法：通过贪婪迭代的方式逐步逼近信号。(1) 匹配追踪算法(MatchingPursuitMP)(2) 正交匹配追踪算法(OrthogonalMatchingPursuitOMP)(3)分段正交匹配追踪算法(StagewiseOrthogonalMatchingPursuitStOMP)正则化正交匹配追踪算法(RegularizedOrthogonalMatchingPursuitROMP)(5)稀疏自适应匹配追踪算法(SparistyAdaptiveMat

3、chingPursuitSAMP)凸松弛算法：(1)基追踪算法(BasisPursuitBP)(2) 最小全变差算法(TotalVariationTV)(3)内点法(Interior-pointMethod)(4) 梯度投影算法(GradientProjection)(5) 凸集交替投影算法(ProjectionsOntoConvexSetsPOCS)算法较多，但是并不是每一种算法都能够得到很好的应用，三类算法各有优缺点，组合算法需要观测的样本数目比较多但运算的效率最高，凸松弛算法计算量大但是需要观测的数量少重构的时候精度高，贪婪迭代算法对计算量和精度的要求居中，也是三种重构算法中应用最大的一

4、种。下面分别就贪婪算法中的MP,OMP算法以及凸松弛算法中的BP算法进行详细的介绍。三种重建算法本节主要是介绍一些基本的重建算法，比如贪婪迭代算法中的匹配追踪算法，正交匹配追踪算法，以及凸松弛算法中的基追踪算法，对其原理进行了介绍，并用matlab代码重构出来一维和二维的图形，进而比较这几种算法的性能。1 .匹配追踪算法(MatchingPursuitMP)匹配追踪算法是Mallat和ZHANG在小波分析的基础上提出的，是贪婪迭代算法中的比较基本的算法，有其显著的特点，是学习研究贪婪算法的基础。1.1 MP算法的原理y=x,其中测量矩阵中又称为过完备字典，每一列被称为一个原子，则测量矩阵中有n

5、个原子，而y的长度为m,原子的个数远远大于信号的长度，即m<<n,因此测量矩阵又称为过完备字典。信号y在测量矩阵上进行分解，可以用中中n来表示，单位向量长度为1,要对过完备字典的原子进行归一化处理。MP算法的基本思想：从观测矩阵(过完备字典)中选择一个与信号y相关性最大(最匹配)的原子，也就是观测矩阵中的一列，构建信号的稀疏逼近，求出信号的残差，重复上面的操作，继续选择与信号残差最匹配的一个原子，如此反复迭代直到达到迭代次数，最后信号y就可以表示为这些原子的线性组合。MP进行稀疏分解的步骤12：从观测矩阵中选择一个与信号y最匹配的原子，也就是内积最大的一个原子，即：|<y，&

6、gt;|=sup|<y，产|(1)-0i.(1,.n)其中，。表示字典矩阵的列索引。先将信号y投影到向量中产上，信号y也可以表示为:厂y。R(2)式等号右边的第一项为观测矩阵中最匹配原子中的垂直投影分-0量，等式右边的第二项R1是y通过中0分解后的残差，且与y正交。(2)式可以写为：222Ilyl-o+lRII对残差Rl进行上面同样的分解，在第n次迭代过程中：FTR'D+Ri因为Rn和中r正交，则(4)式可以表示为：n2,.,22IlRnHT<Rnrn>|+|lRn+lII最后，信号y可以表示为：ny=£<yF7>卬+R由(6)1 =0i-i因为

7、最后的残差R十正交于上次迭代产生的残差Rn，则最后的表达式为：2 n22IlylLFy，片IlRdli=o由(7)式可知，当残差Rn力为零时，可以得到信号的精确分解。定理13存在儿>0,使得一切对于n20时，有一'nIRil卜2llyli成立。这样(7)式中，llR1li按照指数衰减的形式趋于零，也就是2n2|y|Jy,i|成立。参考文献：1曹离然.面向压缩感知的稀疏信号重建算法研究.D.哈尔滨工业大学，2011.2Y.C.PATI.OrthogonalMatchingPursuit:RecursiveFunctionApproximationwithApplicationsto

8、WaveletDecomposition.IEEE.1993:40-443韩红平.压缩感知中信号重构算法的研究.D.南京邮电大学，2012.1.2 MP算法的理论框图根据上面的MP算法的原理，得出MP算法的理论图1,这样更容易理解图1:MP算法框图参考文献：1韩红平.压缩感知中信号重构算法的研究D,南京邮电大学，20121.3 MP算法的算法流程根据1.2中介绍的MP算法的理论框图，现在写出MP算法的算法流程12,这样让我们对MP算法有一个更加清晰的理解。输入：测量矩阵中(MMN),测量向量y(N>1),稀疏度k输出：重构信号x(1):初始化余量0=y,迭代次数n=01;(2):计算余量

9、与测量矩阵的每一列的内积gn=Tn；共有N个内积数值。(3):找出N个gn中的绝对值最大的元素gn(k),k为对应的最大内积的列号。(4):计算信号的近似解xnk=xn/k+gnk；xx(5)：更新余量rn=rn.gnk%；(6):若满足迭代条件，则n=n+1,x'=xn,若不满足迭代条件则x返回步骤(2);迭代次数为稀疏度的2倍。参考文献：1 LinfengDu,RuiWang.AnalysisonGreedyReconstructionAlgorithmsBasedonCompressedSensing.J.IEEE2012:783-7892文首先.压缩感知匹配追踪算法的研究.D.

10、20131.4MP算法的信号重构本节分别通过对一维离散信号，二维Lena为例，进行MP算法的信号重构。(1) 一维离散信号的MP算法仿真本次仿真使用matlab随机生成的一维离散信号，稀疏度k=23，信号长度N=256,观测向量的长度M=80,那么采样率M/N=0.3,其中的观测矩阵中是高斯随机矩阵。采用MP算法对一维信号进行重构，重构图如1:origin图1:MP算法重构一维信号通过上面的重构可以得出，MP算法对一维信号有很好的重构效果。(2)二维lena图像的MP算法重构我们上面的研究知道MP算法对一维信号有很好的重构作用，但是算法不只是要在一维信号中有好的重构功能，还要能很好的重构二维信

11、号才可以，这样应用的范围才会更大。我们知道压缩感知重构的是可压缩的稀疏信号，二维信号是不稀疏的，这就要在进行算法重构的时候进行一些处理，我们可以先采用离散余弦变换（dot）使数据稀疏，算法重构结束之后再进行离散反余弦变换（idct）,这样就转化为了我们所需要的。本次在matlab中的仿真，我们采用的是256M256的Lena的二维图像，M=180,N=256,稀疏度k=40,M/N=0.7,观测矩阵是高斯随机矩阵，采用MP算法对二维图像进行重构，重构效果如图2（b）:（a）原始图片（b）MP算法重构（M/N=0.7）通过上面的（a）图和（b）图可知，采样率为0.7的时候，MP算法也能对二维图像

12、进行精确重构。2.正交匹配追踪算法（OMP）2.1OMP算法的原理OMP算法是在MP算法的基础上进行改进的，沿用了MP算法的重构的思想，但是又对MP算法进行了改进，使得算法的效率更高,应用更加的广泛。MP算法的信号分解中步骤中介绍：y=<y,中>中+R1,这说-0-0明信号在已经选择的原子上的投影(等是右边第一项)是非正交的，还存在着残差，也就是说每次迭代的过程是次最优的，不是最优解，要想最终的迭代收敛，需要的迭代次数较多。OMP算法就是根据MP算法的不足之处加以改进，把所选择的原子首先通过Schimidt正交化处理，使得在达到迭代条件的时候需要的迭代次数较MP算法少，但是正交化的

13、过程中会增加计算量。在每一步中如何对选择的全部原子进行正交化处理呢？这是OMP算法和MP算法的不同之处。下面介绍OMP算法正交化原理1:ky="n=1信号y经k步分解:(1)*Rk且<Rk卅>=0,n=1,，k-n(1)式和MP算法的不同在于，MP算法是残差和前面的一个分量正交，而OMP算法是残差和前面的每个分量都正交。k+1步分解为：k1k1y-Zan'rRk中且，Rir>_0n=1,，k+1n=1'n-nk+1阶减去k阶：k工(an41-ah)tPr十式?rRYRnW'n'k1要想对选择的全部原子进行正交化处理，要求(3)式等于零

14、。测量矩阵的原子不正交，为了说明（3）式等于零，下面引入一个辅助模型，模型表示的是中对前k个项中（n=1,，k）的依赖，数学语言描述如下：kk邛=2bn''rk且kW>=0,n=1,kn1nz1-n-n平在件1,.gk）上张成的正交投影，等式右边的第二项是残差，（4）-k11k式代入（3）式中：kk1kk1kk1"（ananakibn）自nRk/R）=0（5）n1一n如果（6）和（7）式成立，则（5）式必然成立，k1kk1kan-anak书bn=0（6）k1ak1”RkRk=0（7）人k1令ak由=ak，有：k1kkan=a<akbnn=1,k（8）arR

15、书R=0n=1,k（8）和（9）两式成立，以上就是OMP算法进行正交化的过程。参考文献：1Y.C.PATI.OrthogonalMatchingPursuit:RecursiveFunctionApproximationwithApplicationstoWaveletDecomposition.IEEE.1993:40-442.2 OMP算法的流程图和上面的MP算法一样，我们同样画出OMP算法的流程图，可以让我们更加清晰的理解算法图：OMP算法的流程图2.3 OMP算法的算法步骤和MP算法一样，我们也在给出OMP算法的流程图之后，再给出OMP算法的算法步骤12。输入：感知矩阵(MmN),测量

16、向量y(N父1),稀疏度K八输出：重构信号X(1)初始化余量0=y,迭代次数n=0,重建信号X0=°，索引集r0=口；(2)计算余量和测量矩阵每一列的内积：g'G)心；(3)找出gn中绝对值最大的元素；(4) 更新原子组合G=63中J和新索引集n=rnJk；_n-n1k1(5)利用最小二乘法计算信号的近似解：T1tXn=(小品M)rny；(6)计算更新余量：rn=y"xn；(7)更新迭代次数n=n+1,若满足迭代条件，则X=Xn；若不满足迭代的的条件则返回(2),继续进行迭代；参考文献1文首先.压缩感知匹配追踪算法的研究.D.20132Y.C.PATI.Orthog

17、onalMatchingPursuit:RecursiveFunctionApproximationwithApplicationstoWaveletDecomposition.IEEE.1993:40-44上面提到最小二乘法，首先我们先较少一下什么杀死最小二乘法，然后再说明一下为什么OMP算法可以用最小二乘法就信号的解。名词解释：最小二乘法最小二乘法(最小平方法)是一种数学优化技术，它通过使数据误差的平方和最小来寻找数据的最佳函数匹配。最小二乘准则：使全部样本观测值的残差平方和达到最小。即min“q2=min”e(YiYi)来确定未知的参数，未知的参数=(01,k)，未知参数的估计为/,下面

18、我们来推导二阶估计量的公式:(0,1,.k)2Q(：0,：-1,.,二J='ei设所有残差的平方和为：、=a'e(YiYi)e=VY-2vYvX:I、工X、EXA其中，Yi是第i次的样本观测值，Yi为相应的第i次的样本估计值,e2AAe=lemY-yt-xu,对上式进行求导，以便得到最小二乘估计.£n1值：''AA.Q；'A'A'''一)丫丫一2XyXX)=2XY2XX：=0白cc,A1移项可得，XXa=XY，在这里我们假定(x'X)存在，用(XX)左乘上式的；两边，得到。的最小二乘估计量，A,1,豆=(

19、XX)XY,这个公式也就是OMP算法步骤中的步骤(5),以上就证明了最小二乘法估计OMP算法的方法。2.4OMP算法的信号重构本节对OMP算法进行重构，采用一维离散信号和二维lena信号对其进行信号重构，来观察OMP算法的重构功能。(1)一维离散信号的OMP算法仿真本次仿真使用matlab随机生成的一维离散信号，稀疏度k=15，信号长度N=512,观测向量的长度M=128,那么采样率M/N=0.25,其中的观测矩阵中是高斯随机矩阵。采用OMP算法对一维信号进行重通过上面的重构可以得出，OMP算法对一维信号有很好的重构作用。(2)二维lena图像的OMP算法重构OMP算法对二维信号进行重构，在这

20、里我们采取和MP算法二维信号重构的方法，也是先采取离散余弦变换(dot)使数据稀疏,算法重构结束之后再进行离散反余弦变换(idct),这样就转化为了我们所需要的。本次在matlab中的仿真，我们采用的是256乂256的Lena的二维图像,M=180,N=256,稀疏度k=40,M/N=0.7,观测矩阵是高斯随机矩阵，采用OMP算法对二维图像进行重构，重构效果如图2（b）:（a）原始图像（b）OMP算法重构图片（M/N=0.7）通过上面（a）图和（b）图的重构可知，采样率为0.7的时候,OMP算法也能对二维信号很好的重构。3基追踪算法（BP）压缩感知中很重要的一步就是重构算法，重构算法关系着重建

21、信号的质量。基追踪算法是凸松弛法是很有代表性的一种算法。3.1凸松弛法介绍凸松弛法是信号在重构的过程中把重构问题由l0范数问题转化为了l1范数的凸优化问题。下面首先介绍几个涉及到的概念凸优化：定义域是闭合的凸集；函数是定义域上的凸函数的最优化问题，只有两个条件同时满足才是凸优化。凸集：数学定义，D为集合DwRNMXi，X2WD产WO,13QX"(1DxD凸集的几何意义：集合中的任意两点连线段都在集。凸函数：凸集上的g(x)函数和任意的实数«/0,1,Xi，XJD,使gQXl+(1-cc)X2)"叼"尸”必由成立,g(x)就是凸函数。下面介绍一下0范数为什

22、么可以用|1范数进行求解，可以用|2范数进行求解吗？首先给出这三个范数的统一的数学表达式：m叫卜TX|ps,t.丫=6型TXP=0,1,2将三种范数投影到二维空间中，直线丫=6空tx在二维空间中是一条直线，图1是三种范数在二维空间构成的图形和直线之间的直观图。图1:三种范数与直线的关系图其中(a)是|0范数与丫=中TX直线关系图，(b)是l1范数与Y=中中TX直线关系图，（c）是12范数与丫=中中TX直线关系图。由（a）图可知，1。范数在二维空间中是沿着坐标轴的两条垂直的线，直线向坐标原点逼近的时候首先是和坐标轴相交，这也就是我们所要求的稀疏的解；由（b）图可知，11范数在二维空间中的图形是一

23、个如（b）图的菱形，排除直线和菱形的一条边平行的情况，直线向菱形逼近的过程中，首先相交于菱形的四个点，也就是坐标轴上的点，这也就是我们所要求的稀疏的解；由（c）图可知，l2范数在二维空间中的图形是圆形，直线向圆形逼近的时候，直线和圆相交的点几乎都不在坐标轴上，只有直线和坐标轴平行的小概率的时候。通过上面的介绍可以知道，可以用范数来代替1。范数进行求解。3.2BP算法的原理上节提到的l。范数，由于我们所要求解的问题是方程的个数远远大于未知数的个数，用l。范数求解是很难求解出来的，这样就找到一种用11范数来代替1。范数求解的方法，BP（BasisPursuit）算法就是利用卜范数求解的一种很好的方

24、法。BP算法不是直接寻求信号的稀疏表示，只是表示的用于最小化的I1的系数1,通过等价信号的最小化的11范数表示2。下面介绍BP算法的原理。BP算法中1o范数的模型为：八X二min|x|。s.t.y=X（1）1o范数是稀疏变换中不为零的个数，（1）式的求解比较困难，通过上面的说明，1o范数可以用范数进行代替，则（1）式可以表示为：x=min|x|s.t,y=：'X式表示的是理想的一种情况，在实际的应用中，会混入噪声，也就是：y=6x+noise(3)那么(2)式可表示为：(4)X=min|x|s.t.|y-：x|2三；(4)式中名为噪声的能量。由于实际模型中会混入噪声，这就需要一种抑制噪

25、声的模型，也就是改进后的BP算法，改进后的BP算法对噪声有一定的抑制作用，那么改进后的模型为3:m>n(1/2)|y-:-X|2|X|1(5)其中，(5)式的第一项是信号经观测矩阵之后的观测值，式子的第二项是噪声产生的观测值，表示观测值中中非零元素的位置。BP算法中就把凸松弛算法转化为了线性规划问题求解，则(5)式可以转化为13:Ax+6p=bx-0,6=1(6)T、，12miipnCX2|p|s.t.(6)式中,c，1,1,.,1x':1”2，.，nmincTX等价于最小化的l1范数的系数，p表示噪声产生的观测值。参考文献:GreedyBasis1 PatrickS.Huggi

26、ns,StevenW.ZuckerPursuit.IEEE.2007,55(7):3760-37722 S.S.Chen；'BasisPursuit,Ph.D.dissertation,Dept.Statistic§StanfordUniversity,Stanford,CA,1995.3文首先.压缩感知匹配追踪算法的研究.D.20133.3BP算法的信号重构本节对BP算法进行重构，采用一维离散信号和二维lena信号对其进行信号重构，来观察BP算法的重构功能。(1) 一维离散信号的BP算法仿真本次仿真使用matlab随机生成的一维离散信号，稀疏度k=30，信号长度N=1000

27、,观测向量的长度M=200,那么采样率M/N=0.2,其中的观测矩阵9是高斯随机矩阵。采用BP算法对一维信号进行重构，重构图如图1:图1:BP算法一维信号重构图由图1可以得到，BP算法对一维信号有很好的重构功能。（2）二维lena图像的BP算法重构BP算法对二维信号进行重构，在这里我们采取和MP算法二维信号重构的方法，也是先采取离散余弦变换（dot）使数据稀疏，算法重构结束之后再进行离散反余弦变换（idct）,这样就转化为了我们所需要的。本次在matlab中的仿真，我们采用的是256乂256的Lena的二维图像，M=180,N=256,稀疏度k=40,M/N=0.7,观测矩阵是高斯随机矩阵，采

28、用BP算法对二维图像进行重构，重构效果如图2(b):（a）原始图像（b）BP算法重构图片（M/N=0.7）通过上面（a）图和（b）图的重构可知，采样率为0.7的时候,BP算法也能对二维信号很好的重构本章小结本章详细介绍了三种比较典型的重构算法，分别是MP,OMP,BP算法，介绍了三种算法的原理，还有三种算法对一维信号和二维lena信号的重建功能，得出结论是三种算法都有很好的信号重建的功能不同算法的比较上一章中只是对三种算法的原理进行了详细的说明，并用matlab验证三种算法可以对信号进行很好的重构，没有对算法进行分析，即采样率的不同对算法的影响和对lena信号重构的清晰度的影响。在这一章中，就

29、对三种重构算法进行分析。1采样率对三种算法的影响1.1 采样率对MP算法的影响我们先看一下采样率对一维信号的影响，首先用重构图来直观的区别一下，表1是MP算法中采样率对重构时间和误差的表格：采样率0203040.50.60.703MSE5.65782.2428L7904031250.22240.05330.04760.0279时间（S）0.07400.07500.08110.08320.08530.0802Q.O9850.0885表1:MP算法采样率对重构时间和误差的影响表1中测量了不同采样率对应的MP算法中重构的MSE和时间的值,从表格中可知，采样率越大，重构产生的MSE越小，重构的图形越接

30、近原始图形，但是时间也会增大，增加了计算的复杂度。下面我们再看一下采样率的不同对lena信号的影响，可以用采样率为0.30.50.8这三个采样率，对比一下采样率的不同重构出来的图片的清晰度。图3的（a）图是原始图片，（b）为采样率为0.3时的重构图，（c）图是采样率为0.5时的重构图，（d）图是采样率为0.8（c）MP重构图片（M/N=0.5）（d）MP重构图片（M/N=0.8）图3:MP重构的不同采样率的lena重构图形由图3中的四个图片可知，采样率越大，重构的图形效果越好，在应用的时候要想获得很好的重构图片就需要较高的采样率，但是所需要的时间也会越大。1.2 采样率对OMP算法的影响和MP

31、算法一样，也是先对一维信号重构进行分析，表2是OMP算法中采样率对重构的MSE和时间的对应表格：采样率0J020.3G.40.50.60,70金MSE13.5407625236.49814.88824.1499372232.938025875时间（s）0.13920.14730.14%0.15100,15530.16310.17050.1737表2:MP算法采样率对重构时间和误差的影响表2中测量了不同采样率对应的OMP算法中重构的MSE和时间的值，从表格中可知，OMP算法和MP算法一样，也是采样率越大，重构产生的MSE越小，重构的图形越接近原始图形，但是时间也会增大，同样增加了计算的复杂度。下

32、面我们再看一下采样率的不同对lena信号的影响，同MP算法一样，采用采样率为0.30.50.8这三个采样率，对比一下采样率的不同重构出来的图片的清晰度。图4的（a）图是原始图片，（b）为采样率为0.3时的重构图，（c）图是采样率为0.5时的重构图，（d）图是采样率为0.8时的重构图。（a）原始图片（b）OMP重构图片（M/N=0.3）(c)OMP重构图片(M/N=0.5)(d)OMP重构图片(M/N=0.8)图4：OMP重构的不同采样率的lena重构图形由图4中的四个图片可知，OMP算法和MP算法一样，采样率越大,重构的图形效果越好，在应用的时候要想获得很好的重构图片就需要较高的采样率，但是所

33、需要的时间也会越大。1.3 采样率对BP算法的影响研究采样率对BP算法的影响，研究方法和上面的MP,OMP算法一样，首先研究采样率大的不同多一位信号大的影响，表3是采样率对重构误差和重构时间的关系表格：果样率0.10.20.30.40.50.60.70.8MSI：474461,.7«X7).44761.4701.35731.28851.2337.0IS5时间（s）0.57960.67290.73K80.95041.22521.324215385表3:BP算法采样率对重构时间和误差的影响表3中测量了不同采样率对应的BP算法中重构的MSE和时间的值，从表格中可知，BP算法和MP,OMP算

34、法一样，也是采样率越大，重构产生的MSE越小，重构的图形越接近原始图形，但是时间也会增大，同样增加了计算的复杂度。下面我们再看一下采样率的不同对lena信号的影响，仍然采用采样率为0.30.50.8这三个采样率，对比一下采样率的不同重构出来的图片的清晰度。图5的（a）图是原始图片，（b）为采样率为0.3时的重构图，（c）图是采样率为0.5时的重构图，（d）图是采样率为0.8时的重构图(b)BP重构图片(M/N=0.3)(a)原始图片(c)BP重构图片(M/N=0.5)(d)BP重构图片(M/N=0.8)图5:BP重构的不同采样率的lena重构图形由图5中的四个图片可知，BP算法和MP,OMP算

35、法一样，采样率越大，重构的图形效果越好，在应用的时候要想获得很好的重构图片就需要较高的采样率，但是所需要的时间也就会会越长。从上面的三种算法中采样率对重构时间和误差的影响中，可以得出相同的结论，在一维信号中，采样率越大，重构的误差越小，重构所需要的时间越大。在二维图片中，采样率越大，重构的图片越清晰。2.信噪比对三种算法的影响在实际的应用中，会混入噪声，没有噪声那是理想的情况，这里就研究一下信噪比对重构信号产生的MSE的影响。2.1 信噪比对MP算法的影响首先研究信噪比对MP算法产生的影响，图6是信噪比和MSE的关系曲线图，在matlab的环境中，试验了100次产生的曲线。8765UJ54名3

36、21°%、XA"-S.%,-j、h7111015202530SNR(dB)图6:SNR和MSE关系曲线由图6可知，信噪比越大，MSE就越小。2.2 信噪比对OMP算法的影响研究信噪比对OMP算法的影响，研究方法和所用的环境和MP算法一样，图7是SNR和MSE的关系曲线:4J11111.21,1:08；：:!UJS;1;三11*I106<'*k1tH1;:VI11110.4、；:、：:;、；:1、*1：!7!0.2i-.“一:；J-J-.-_0life!&111151015202530SNR(dB)图7:SNR和MSE关系曲线由图7可知，随着信噪比的增大

37、，均方差减小。2.3 信噪比对BP算法的影响研究信噪比对BP算法的影响，研究方法和所用的环境和MP算法一样，图8是SNR和MSE的关系曲线：10.5109.59UJ岑8.587.57-*1/寸/XX/*L/X，iJ/J/*1V111/f/i1JJ,厂fffII11Jfir'51015202530SNR(dB)图8:SNR和MSE关系曲线由图8可以得出，BP算法和MP,OMP算法的SNR和MSE的关系曲线不同，是一个折线的形式。3三种算法之间的比较本章上面的分析中，分析的是采样率和信噪比对三种算法各自的一些影响，这里要分析的是三种算法之间的性能分析。图9表示的是采样率对三种算法重构时间的

38、影响图，图10表示的采样率对三种算法重构的均方差的影响图，图11表示的是信噪比对三种算法MSE的影像图：16回aQsB-TE*4*0JJJJ0.10.20.30.40506采样率图9:采样率对三种算法重构时间的影响图由图9可知，采样率相同的情况下，BP算法重构的时间最长，MP算法重构所需要的时间最短。MP和OMP算法的重构时间变化较小，而BP算法在采样率为0.3之后，变化较快。OMP算法中迭代次数较MP算法少，但是需要正交化处理，所以重构的时间会比MP算法长。I4!1fMl产rEADiijUmrI士108LJ5莅6nCQO口or>arJ1,1411i4-E4L4T*=1U01020304

39、050采样率60708图10:采样率对三种算法重构MSE的影响图由图10可知，随着采样率的增加，算法的误差都减小，MP算法的误差下降的更快。111111111111111JJ1tMP-OMP：X!OBP:-：1'Il!1ih;Jij._SNRfdBl图11:信噪比对三种算法重构MSE的影响图由图11可知，三种算法都是随着信噪比的增加，MSE下降。BP算法的均方差最大，OMP算法的均方差最小。由上面的图9,图10,图11中三种算法的对比图中可知，从重构时间，重构误差方面考虑的话，OMP算法是三种算法中性能最折中的算法。正则化正交匹配追踪算法（ROMP）本章介绍一种匹配追踪算法中的改进算法

40、，正则化正交匹配追踪算法（ROMP）,是在正交匹配追踪算法（OMP）的基础上改进的，是Needell和Vershynin1提出来的，是贪婪迭代算法中较成熟的一种算法。ROMP算法改进的地方是：OMP算法对每个原子做处理的时候都要做K次迭代，而ROMP算法是首先选出符合要求的K个原子，再从中进行筛选，减少了迭代的次数，同时也增加了算法重构的精度，但是ROMP算法也有自己的缺点，就是算法首先要知道信号的稀疏度K,这样才能精确的重构。在实际的应用中，信号可能的稀疏度很小，或者是经过变换才是稀疏的，还有一种情况是在不同的环境中，信号的稀疏度可能是不一样的，这几种情况下信号的重构误差大，需要进一步的研究来克服这个缺点。ROMP算法的步骤23:输入：观测值y,测量向量中，稀疏度K;输出：重构信号x；初始化：°=y，n=1,r0=4，a=4迭代：（1）gn=6Trn；（2）A=gn幅度的前K个最大值的索引;（3）利用正则化找到AUA,使得1g尸2|gJ对所有i,jwA成立；,nn4（4）1=1-上；(5)最小二乘法x；n=(；nGn)G；ny；(6)更新残差/=y-rnxn；A(7)若|A户2K,则停止迭代，贝U