压缩感知的重构算法.docx

《压缩感知的重构算法.docx》由会员分享，可在线阅读，更多相关《压缩感知的重构算法.docx（43页珍藏版）》请在三一文库上搜索。

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

2、Fourier Representaion)(2) 链式追踪算法(Chaining Pursuit)(3) HHS 追踪算法( Heavy Hitters On Steroids)贪婪算法：通过贪婪迭代的方式逐步逼近信号。(1) 匹配追踪算法( Matching Pursuit MP )(2) 正交匹配追踪算法( Orthogonal Matching Pursuit OMP )(3) 分段正交匹配追踪算法( Stagewise Orthogonal MatchingPursuit StOMP)(4) 正则化正交匹配追踪算法( Regularized Orthogonal MatchingPu

3、rsuit ROMP)(5) 稀疏自适应匹配追踪算法 ( Sparisty Adaptive Matching PursuitSAMP)凸松弛算法：(1) 基追踪算法( Basis Pursuit BP)(2) 最小全变差算法( Total Variation TV )(3) 内点法( Interior-point Method )(4) 梯度投影算法(Gradient Projection)(5) 凸集交替投影算法( Projections Onto Convex Sets POCS)算法较多， 但是并不是每一种算法都能够得到很好的应用， 三类算法各有优缺点，组合算法需要观测的样本数目比较多

4、但运算的效率最高，凸松弛算法计算量大但是需要观测的数量少重构的时候精度高，贪婪迭代算法对计算量和精度的要求居中， 也是三种重构算法中应用最大的一种。 下面分别就贪婪算法中的 MP， OMP 算法以及凸松弛算法中的 BP 算法进行详细的介绍。三种重建算法本节主要是介绍一些基本的重建算法，比如贪婪迭代算法中的匹配追踪算法，正交匹配追踪算法，以及凸松弛算法中的基追踪算法，对其原理进行了介绍，并用 matlab代码重构出来一维和二维的图形，进而比较这几种算法的性能。1 .匹配追踪算法(Matching Pursuit MP)匹配追踪算法是Mallat和ZHANG在小波分析的基础上提出的， 是贪婪迭代算

5、法中的比较基本的算法，有其显著的特点，是学习研究贪婪算法的基础。1.1 MP算法的原理y =x ,其中测量矩阵中又称为过完备字典，每一列被称 为一个原子，则测量矩阵中有n个原子，而y的长度为m,原子的个 数远远大于信号的长度，即mn,因此测量矩阵又称为过完备字典。 信号y在测量矩阵上进行分解，可以用中1.中n来表示，单位向 量长度为1,要对过完备字典的原子进行归一化处理。MP算法的基本思想：从观测矩阵(过完备字典)中选择一个与信号 y相关性最大(最 匹配)的原子，也就是观测矩阵中的一列，构建信号的稀疏逼近，求 出信号的残差，重复上面的操作，继续选择与信号残差最匹配的一个 原子，如此反复迭代直到

6、达到迭代次数，最后信号y就可以表示为这 些原子的线性组合。MP进行稀疏分解的步骤12：从观测矩阵中选择一个与信号 y最匹配的原子，也就是内积最大 的一个原子，即：|=sup|(1)- 0 i.(1,.n)其中，。表示字典矩阵的列索引。先将信号 y投影到向量中/上，信号y也可以表示为:广 y，。，。R（2）式等号右边的第一项为观测矩阵中最匹配原子中的垂直投影分-0量，等式右边的第二项 R1是y通过中0分解后的残差，且与y正交。（2）式可以写为：222一|=卜乂、0+|同对残差R1进行上面同样的分解，在第n次迭代过程中：RXR、+乩-n- n因为Rn和中r正交，则（4）式可以表示为： n2 ,.,

7、221喇1=卜心中*1+11仆+1|1最后，信号y可以表示为：ny = yFr r + R出（6）1 =0i- i因为最后的残差 R十正交于上次迭代产生的残差 Rn，则最后的表达式为：2 n22IMLWrjHlR+llli =o由（7）式可知，当残差 Rn十为零时，可以得到信号的精确分解。定理13 存在儿0,使得一切对于n20时，有一nIR1I卜 2 iiyii成立。这样（7）式中，IIR/I按照指数衰减的形式趋于零，也就是2 n2|y| 二1| y,1i | 成立。参考文献：1曹离然.面向压缩感知的稀疏信号重建算法研究.D.哈尔滨工业大学，2011.2 Y.C.PATI.Orthogonal

8、 Matching Pursuit: Recursive Function Approximation with Applications to Wavelet Decomposition.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算法有一个更

9、加清晰的理解。输入：测量矩阵中(MMN),测量向量y(N父1),稀疏度k输出：重构信号x(i)：初始化余量0 = y,迭代次数n=0 i；(2)：计算余量与测量矩阵的每一列的内积gn =Trn；共有N个内积数值。(3):找出N个gn中的绝对值最大的元素gn(k), k为对应的最大内 积的列号。(4)：计算信号的近似解xnk=xn/k+gnk; xx(5):更新余量rn = rn. gnk卬；I I k(6):若满足迭代条件，则 n=n+1, x= xn ,若不满足迭代条件则x返回步骤(2);迭代次数为稀疏度的2倍。参考文献：1 Linfeng Du,Rui Wang. Analysis on

10、Greedy Reconstruction Algorithms Based on Compressed Sensing.J.IEEE 2012:783-7892文首先.压缩感知匹配追踪算法的研究.D.20131.4 MP算法的信号重构本节分别通过对一维离散信号，二维Lena为例，进行MP算法的信号重构。(1) 一维离散信号的MP算法仿真本次仿真使用matlab随机生成的一维离散信号，稀疏度 k=23，信号 长度N=256,观测向量的长度 M=80,那么采样率M/N=0.3,其中的 观测矩阵中是高斯随机矩阵。采用MP算法对一维信号进行重构， 重构图如1:origin图1: MP算法重构一维信号

11、通过上面的重构可以得出，MP算法对一维信号有很好的重构效果。(2)二维lena图像的MP算法重构我们上面的研究知道 MP算法对一维信号有很好的重构作用，但是算法不只是要在一维信号中有好的重构功能， 还要能很好的 重构二维信号才可以，这样应用的范围才会更大。我们知道压缩感知 重构的是可压缩的稀疏信号，二维信号是不稀疏的，这就要在进行算法重构的时候进行一些处理，我们可以先采用离散余弦变换（dct）使数据稀疏，算法重构结束之后再进行离散反余弦变换（idct）,这样 就转化为了我们所需要的。本次在matlab中的仿真，我们采用的是256M 256 的 Lena 的二维图像， M=180, N=256,

12、稀疏度 k=40, M/N=0.7,观测矩阵是高斯随机矩阵，采用 MP算法对二维图像进行 重构，重构效果如图2 （b）:（a）原始图片（b） MP算法重构（M/N=0.7）通过上面的（a）图和（b）图可知，采样率为0.7的时候，MP算法也能对二维图像进行精确重构。2.正交匹配追踪算法（OMP）2.1OMP算法的原理OMP算法是在MP算法的基础上进行改进的，沿用了 MP算法的重构的思想，但是又对MP算法进行了改进，使得算法的效率更高， 应用更加的广泛。MP算法的信号分解中步骤中介绍：y =中+ Ri,这说 -0- 0明信号在已经选择的原子上的投影（等是右边第一项）是非正交的， 还存在着残差，也就

13、是说每次迭代的过程是次最优的，不是最优解， 要想最终的迭代收敛，需要的迭代次数较多。OMP算法就是根据MP 算法的不足之处加以改进，把所选择的原子首先通过Schimidt正交化 处理，使得在达到迭代条件的时候需要的迭代次数较 MP算法少，但 是正交化的过程中会增加计算量。在每一步中如何对选择的全部原子进行正交化处理呢？这是OMP算法和MP算法的不同之处。下面介绍OMP算法正交化原理1:信号y经k步分解:ky =n =1a：“* Rk 且 =0 , n=1,，k-n(1)（1）式和MP算法的不同在于，MP算法是残差和前面的一个分量正交，而OMP算法是残差和前面的每个分量都正交。k+1步分解为：k

14、 1 k 1y 一 Z an r+ Rk+i 且 Ri 0 n=1,，k+1n =1 n- nk+1阶减去k阶：k（OTW）、+aXRYRnW n k 1要想对选择的全部原子进行正交化处理，要求（3）式等于零。测量矩阵的原子不正交，为了说明（3）式等于零，下面引入一个辅助模 型，模型表示的是中对前k个项中（n=1,，k）的依赖，数学 语言描述如下：kk邛=b*rk且 =0,n=1,- -,k-n 1nzi- n. n平在件1,.gk）上张成的正交投影，等式右边的第二项是残差，（4）-k 11k式代入（3）式中：k.（/-；$）1（aklrkRi-RkA。（5）n 1一 n如果（6）和（7）式成

15、立，则（5）式必然成立，k 1 k k 1 kan -an ak 书bn=（6）k 1ak I” RkiRk = （7）k 1令ak由=ak，有：k 1 kkan =aakbnn=1,k（8）arR书R=n=1,k（8）和（9）两式成立，以上就是 OMP算法进行正交化的过程。参考文献：1 Y.C.PATI.Orthogonal Matching Pursuit: Recursive FunctionApproximation with Applications to WaveletDecomposition.IEEE.1993:40-442.2 OMP算法的流程图和上面的MP算法一样，我们同样

16、画出 OMP算法的流程图，可以让我们更加清晰的理解算法图：OMP算法的流程图2.3 OMP算法的算法步骤和MP算法一样，我们也在给出OMP算法的流程图之后，再给出OMP算法的算法步骤12。输入：感知矩阵（M父N ）,测量向量y （ N父1）,稀疏度K八输出：重构信号X(1)初始化余量ro = y,迭代次数n=0,重建信号Xo=0,索引集r 0 =口 ；(2)计算余量和测量矩阵每一列的内积：gn = G T/；(3)找出gn中绝对值最大的元素；(4) 更新原子组合3中)和新索引集n = rnJk； _ n_ n _1k-(5 )利用最小二乘法计算信号的近似解：jXn = g 吊 rn) 中；ny

17、 ；(6)计算更新余量：rn=y一xn；(7)更新迭代次数n=n+1,若满足迭代条件，则X= Xn ；若不满足迭代的的条件则返回(2),继续进行迭代；参考文献1文首先.压缩感知匹配追踪算法的研究.D.20132 Y.C.PATI.Orthogonal Matching Pursuit: Recursive FunctionApproximation with Applications to WaveletDecomposition.IEEE.1993:40-44上面提到最小二乘法，首先我们先较少一下什么杀死最小二乘法，然后再说明一下为什么OMP算法可以用最小二乘法就信号的解。名词解释：最小二乘

18、法最小二乘法(最小平方法)是一种数学优化技术，它通过使数据误差的平方和最小来寻找数据的最佳函数匹配。最小二乘准则：使全部样本观测值的残差平方和达到最小。即来确定未知的参数，未知的参数min “ o2 = min ”ei(YiYi)=(0 01,. k)， 未知参数的估计为/,下面我们来推导二阶估计量的公式:(0, 1,k)2Q(: 0, 1,., 二 J = ei设所有残差的平方和为：、=Qe (YiYi) e= VY-2 v Y Y X :I X X X XA其中，Yi是第i次的样本观测值，Yi为相应的第i次的样本估计值,e2A Ae=e mY.yt - x。，对上式进行求导，以便得到最小二

19、乘估计 .n值：AA.Q； A A 一=YY 2 X Y X X )= 2XY 2X X： =0白cc， A_1移项可得， X Xa = X Y，在这里我们假定 (xX)存在，用 (X X)左乘上式的；两边，得到。的最小二乘估计量， A,-4豆=(X X) XY,这个公式也就是 OMP算法步骤中的步骤(5), 以上就证明了最小二乘法估计 OMP算法的方法。2.4 OMP算法的信号重构本节对OMP算法进行重构，采用一维离散信号和二维 lena信号对其进行信号重构，来观察OMP算法的重构功能。(1) 一维离散信号的OMP算法仿真本次仿真使用matlab随机生成的一维离散信号，稀疏度 k=15，信号

20、长度N=512,观测向量的长度 M=128,那么采样率M/N=0.25,其中的观测矩阵中 是高斯随机矩阵。采用 OMP算法对一维信号进行重通过上面的重构可以得出，OMP算法对一维信号有很好的重构作用。(2)二维lena图像的OMP算法重构OMP算法对二维信号进行重构，在这里我们采取和 MP算法二维信号重构的方法，也是先采取离散余弦变换(dct)使数据稀疏,算法重构结束之后再进行离散反余弦变换(idct),这样就转化为了我们所需要的。本次在 matlab中的仿真，我们采用的是 256乂 256的Lena 的二维图像,M=180, N=256,稀疏度 k=40, M/N=0.7 ,观测矩阵是高斯随

21、机矩阵，采用 OMP算法对二维图像进行重构，重构效果如图2 （b）:（a）原始图像（b） OMP算法重构图片（M/N=0.7）通过上面（a）图和（b）图的重构可知，采样率为0.7的时候, OMP算法也能对二维信号很好的重构。3基追踪算法（BP）压缩感知中很重要的一步就是重构算法，重构算法关系着重建信号的质量。基追踪算法是凸松弛法是很有代表性的一种算法。3.1凸松弛法介绍凸松弛法是信号在重构的过程中把重构问题由l0范数问题转化为了 l1范数的凸优化问题。下面首先介绍几个涉及到的概念凸优化：定义域是闭合的凸集；函数是定义域上的凸函数的最优化问 题，只有两个条件同时满足才是凸优化。凸集：数学定义，D

22、为集合DERN，守XiN D产0，1，九xF1“乂亡 D凸集的几何意义：集合中的任意两点连线段都在集。凸函数：凸集上的g (x)函数和任意的实数 w0,1, X，X2W D, 使g( X(1-X2) “叼仅尸0一“必由成立,g (x)就是凸函数。 下面介绍一下0范数为什么可以用11范数进行求解，可以用12范数进 行求解吗？首先给出这三个范数的统一的数学表达式：m叫卜 TX11P st 丫 =里 TXP=0, 1, 2将三种范数投影到二维空间中，直线 丫 =6空TX在二维空间中是一 条直线，图1是三种范数在二维空间构成的图形和直线之间的直观 图。图1:三种范数与直线的关系图其中(a)是l0范数与

23、丫 =中TX直线关系图，(b)是l1范数与Y=中中TX直线关系图，（c）是l2范数与丫 =中中TX直线关系图。 由（a）图可知，代范数在二维空间中是沿着坐标轴的两条垂直的线， 直线向坐标原点逼近的时候首先是和坐标轴相交，这也就是我们所要求的稀疏的解；由（b）图可知，11范数在二维空间中的图形是一个 如（b）图的菱形，排除直线和菱形的一条边平行的情况，直线向菱 形逼近的过程中，首先相交于菱形的四个点，也就是坐标轴上的点， 这也就是我们所要求的稀疏的解；由（c）图可知，l2范数在二维空 间中的图形是圆形，直线向圆形逼近的时候，直线和圆相交的点几乎 都不在坐标轴上，只有直线和坐标轴平行的小概率的时候

24、。通过上面 的介绍可以知道，可以用11范数来代替八范数进行求解。3.2 BP算法的原理上节提到的l0范数，由于我们所要求解的问题是方程的个数远远 大于未知数的个数，用l 0范数求解是很难求解出来的，这样就找到一 种用11范数来代替10范数求解的方法，BP （Basis Pursuit ）算法就是 利用l1范数求解的一种很好的方法。BP算法不是直接寻求信号的稀 疏表示，只是表示的用于最小化的l1的系数1,通过等价信号的最小 化的11范数表示2。下面介绍BP算法的原理。BP算法中l0范数的模型为：八x = m叫|x|0s.t. y= ：X（1）l0范数是稀疏变换中不为零的个数，（1）式的求解比较困

25、难，通过上 面的说明，l0范数可以用范数进行代替，则（1）式可以表示为：x = min|x|1 s.t. yx式表示的是理想的一种情况，在实际的应用中，会混入噪声，也 就是：y =6 x + noise(3)那么(2)式可表示为：(4)x = m叫|x|1 s.t. |y- ：x|2；(4)式中名为噪声的能量。由于实际模型中会混入噪声，这就需要一种抑制噪声的模型，也就是改进后的 BP算法，改进后的BP算法对噪声有一定的抑制作用，那么改进后的模型为 3:mjn(1/2)|y- ：，x|2|刈(5)其中，(5)式的第一项是信号经观测矩阵之后的观测值，式子的第二项是噪声产生的观测值，表示观测值中中非

26、零元素的位置。BP算法中就把凸松弛算法转化为了线性规划问题求解，则(5)式可以Ax+ 6p = b x - 0 , 6 = 1(6)转化为13：T、，12mxipnC X2|p| s.t.(6)式中,c， 1,1，1x L 1” 2,.， nmin cTX等价于最小化的l1范数的系数，p表示噪声产生的观测值。Greedy Basis参考文献:1 Patrick S.Huggins , Steven W. ZuckerPursuit.IEEE.2007,55(7):3760-37722 S.S.Chen：Basis PursuitPh.D.dissertation , Dept.Statisti

27、cs StanfordUniversity,Stanford,CA,1995.3文首先.压缩感知匹配追踪算法的研究.D.20133.3 BP算法的信号重构本节对BP算法进行重构，采用一维离散信号和二维lena信号对其进行信号重构，来观察BP算法的重构功能。(1) 一维离散信号的BP算法仿真本次仿真使用matlab随机生成的一维离散信号，稀疏度 k=30，信号 长度N=1000,观测向量的长度 M=200,那么采样率M/N=0.2,其中 的观测矩阵9是高斯随机矩阵。采用BP算法对一维信号进行重构， 重构图如图1:图1: BP算法一维信号重构图由图1可以得到，BP算法对一维信号有很好的重构功能。（

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

29、重构本章小结本章详细介绍了三种比较典型的重构算法，分别是MP,OMP,BP算法，介绍了三种算法的原理，还有三种算法对一维信号和二维lena 信号的重建功能，得出结论是三种算法都有很好的信号重建的功能不同算法的比较上一章中只是对三种算法的原理进行了详细的说明，并用matlab验证三种算法可以对信号进行很好的重构，没有对算法进行分析，即采样率的不同对算法的影响和对 lena信号重构的清晰度的影响。在 这一章中，就对三种重构算法进行分析。1采样率对三种算法的影响1.1 采样率对MP算法的影响我们先看一下采样率对一维信号的影响，首先用重构图来直观的区别一下，表1是MP算法中采样率对重构时间和误差的表格

30、：采样率0203040.50.60.703MSE5.65782.2428L7904031250.22240.05330.04760.0279时间 （S）0.07400.07500.081 10.08320.08530.08020.09850.0885表1: MP算法采样率对重构时间和误差的影响表1中测量了不同采样率对应的 MP算法中重构的MSE和时间的值, 从表格中可知，采样率越大，重构产生的 MSE越小，重构的图形越 接近原始图形，但是时间也会增大，增加了计算的复杂度。下面我们再看一下采样率的不同对lena信号的影响，可以用采样率为0.3 0.5 0.8这三个采样率，对比一下采样率的不同重构

31、出来的图片的清晰度。图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算法一样，也是先对一维信号重构进行分析，表2是OMP算法中采样率对重构的 MSE和时间的对应表格：采样率0.10.2030.40.50.60.703MSE13.

32、54076.25236.49S14.88824.14993.72232.93802.7875时间 （s）0.33920,14730.14960,15100.15530.16310.17050.1737表2: MP算法采样率对重构时间和误差的影响表2中测量了不同采样率对应的 OMP算法中重构的MSE和时间的 值，从表格中可知，OMP算法和MP算法一样，也是采样率越大， 重构产生的MSE越小，重构的图形越接近原始图形，但是时间也会 增大，同样增加了计算的复杂度。下面我们再看一下采样率的不同对lena信号的影响，同MP算 法一样，采用采样率为0.3 0.5 0.8这三个采样率，对比一下采样率的 不同

33、重构出来的图片的清晰度。图 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算法一样，采样率越大, 重构的图形效果越好，在应用的时候要想获得很好的重构图片就需要 较高的采样率，但是所需要的时间也会越大。1.3 采样率对BP算法的影响研究采样率对BP算法的影响，研究方法和上面的MP,OMP算

34、法一样，首先研究采样率大的不同多一位信号大的影响，表3是采样率对重构误差和重构时间的关系表格：采样率0.10.20.30.40.50.60.7MSE4.7446L72871.44761,47011.35731.28R51.23371.0185时间 （s）0.57960.67290.80920.95041.22521.32421.53S5表3: BP算法采样率对重构时间和误差的影响表3中测量了不同采样率对应的 BP算法中重构的MSE和时间的值， 从表格中可知，BP算法和MP, OMP算法一样，也是采样率越大， 重构产生的MSE越小，重构的图形越接近原始图形，但是时间也会 增大，同样增加了计算的复

35、杂度。下面我们再看一下采样率的不同对 lena信号的影响，仍然采用 采样率为0.3 0.5 0.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算法一样，采样率越大， 重构的图形效果越好，在应用的时候要想获得很好的重构图片就需要 较

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

37、R(dB)图6: SNR和MSE关系曲线由图6可知，信噪比越大，MSE就越小。2.2 信噪比对OMP算法的影响研究信噪比对OMP算法的影响，研究方法和所用的环境和 MP算法一样，图7是SNR和MSE的关系曲线:4 J11111.21,1:08 ； ： : !UJS ; ; 1 ;三11*I10 6 arJ1,1 411 i4-E4L4T*=1U010203040 50采样率60708图10:采样率对三种算法重构MSE的影响图由图10可知，随着采样率的增加，算法的误差都减小，MP算法的误差下降的更快。111111111111111JJ1t MP- OMP：X !O BP :- ：1Il!1ih;

38、J ij._rHSNRfdBl图 11：信噪比对三种算法重构MSE 的影响图由图 11 可知，三种算法都是随着信噪比的增加， MSE 下降。 BP 算法的均方差最大， OMP 算法的均方差最小。由上面的图 9，图10，图 11 中三种算法的对比图中可知，从重构时间，重构误差方面考虑的话， OMP 算法是三种算法中性能最折中的算法。正则化正交匹配追踪算法（ROMP ）本章介绍一种匹配追踪算法中的改进算法， 正则化正交匹配追踪 算法（ROMP）,是在正交匹配追踪算法（OMP）的基础上改进的， 是Needell和Vershynin1提出来的，是贪婪迭代算法中较成熟的一 种算法。ROMP算法改进的地方

39、是：OMP算法对每个原子做处理的 时候都要做K次迭代，而ROMP算法是首先选出符合要求的 K个 原子，再从中进行筛选，减少了迭代的次数，同时也增加了算法重构 的精度，但是ROMP算法也有自己的缺点，就是算法首先要知道信 号的稀疏度K,这样才能精确的重构。在实际的应用中，信号可能的 稀疏度很小，或者是经过变换才是稀疏的，还有一种情况是在不同的 环境中，信号的稀疏度可能是不一样的，这几种情况下信号的重构误 差大，需要进一步的研究来克服这个缺点。ROMP算法的步骤23:输入：观测值V,测量向量中，稀疏度K； 八输出：重构信号x ;初始化： = y , n=1 , r0 =4，a =4迭代：（1） gn=6Trn；（2 ） A=gn幅度的前K个最大值的索引; （3）利用正则化找到AUA ,使得1g尸2|gjl,对所有i, j w A 成立； ,n n 4（4） r =r =a；(5)最小二乘法 x1=(GTnGrn) G；ny；(6)更新残差= y /xn；A(7)若|A户2K,则停止迭代，贝U x = x,否则令n=n+1, 并重复步骤(1);在介绍了 ROMP算法的流程之后，下面就要