通过正交匹配追踪算法从随机测量值中恢复信号

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,报告人：汪琪,组员：汪琪 王心遥 黄若思 唐松柏 徐露露,通过正交匹配追踪算法从随机测量值中恢复信号,原文标题：,Signal Recovery From Random Measurements Via Orthogonal Matching Pursuit,作者：,Joel A.Tropp,Member,IEEE,and Anna C.Gilbert,期刊号：,IEEE TRANSACTIONS ON INFORMATION THEORY,VOL.53,NO.12,DECEMBER 2007,摘要：,本文从理论和实践上展示了一种名为正交匹配追踪（,OMP,）的贪婪算法可以在给定,O(mln d),个随机线性测量值下有效地恢复有,m,个非零元素的,d,维信号。相比以前需要,O(m2,）个测量值，这是一个很大的进步。,OMP,的新结果可以和另一种被称为基追踪（,BP,）的方法相比。在某些条件下,OMP,算法更快速且更容易实现，所以对信号恢复问题是除,BP,外另一种具有吸引力的选择。,关键词：,算法，近似，基追踪，压缩感知，群组测试，正交匹配追踪，信号恢复，稀疏近似。,问题描述：,s,为长度为,d,的真实信号，它的稀疏度为,m,，即含有,m,个非零元素。,为,Nd,的测量矩阵，,v=s,为长度为,N,的测量值。我们的问题即已知测量值,v,和测量矩阵,，恢复出真实信号,s,。由于测量值维数,N,小于真实信号维数,d,，故该方程组没有确定解，我们需要利用,s,的稀疏特性寻找出最优解。该算法即正交匹配追踪法（,OMP,）。,算法思想,:,贪婪迭代,贪婪算法：,在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。,对测量矩阵,的要求：,1),独立性,:,的各列线性无关；,2),归一化,:,对,的各列,j,，,j=1,2,，,d.|,j,|,2,2,=1;,3),独立相关性,:u,t,为,l,2,范数不超过,1,的,m,个向量组成的向量组,为,中与该向量组线性无关的一列,有,4),最小奇异值,:,对于从,从取出的,Nm,维子矩阵,Z,奇异值,m,(Z),满足,常用测量矩阵,:,1),高斯矩阵,中的每个元素独立满足,(0,，,1/N),的正态分布，概率密度函数,p,为,2),伯努利矩阵,等概率独立选取,中的各元素为,OMP,算法,:,输入,:Nd,维测量矩阵,;,N,维观测值,v;,理想信号稀疏度,m.,输出,:,理想信号的,d,维恢复信号,s*,从,1,d,中选取的含有,m,个元素的指标集,m,对,v,的,n,维近似向量,a,m,n,维残差向量,r,m,=v-a,m,OMP,算法,:,1),初始化残差,r,0,=v,指标集,0,=,迭代计数,t=1;,2),找到满足下述最优化问题的指标,t,t,=arg max,j=1,d,|,3),扩充指标集和矩阵,t,=,t-1,t,及,t,=,t-1,t,0,为空矩阵,4),解如下最小二乘问题,x,t,=arg min,x,|v-,t,x|,2,5),计算新的信号估计和残差,:a,t,=,t,x,t,r,t,=v-a,t,6)t=t+1,，若,tm,返回步骤,2,7),恢复信号,x*,的非零值指标为,m,中的元素,s*,中第,j,个元素的值等于,x,t,的第,j,个元素,判断算法成败,:,从,R,d,中任意选取稀疏度为,m,的信号,s,为,Nd,维高斯矩阵,执行,OMP,算法,v=s,若残差,r,m,在迭代,m,次后为,0,，则,OMP,完全复原了信号,s,否则若残差,在迭代,m,次后不为,0,则,OMP,失败了,.,OMP,算法成功率,:,取,为,(0,0.36),中一定值,取,NKmlog(d/),其中,K,为绝对常数,.s,是从,R,d,中任意选取稀疏度为,m,的信号,维,Nd,维测量矩阵,已知测量值,v=s,OMP,算法能成功恢复信号的概率为,1-.,时间复杂度,:,O(mNd),实验仿真,:,实验信号,s,为长度为,d,的一维信号,将其中随机,m,个值赋,1,其余为,0,.,复原成功,复原失败,d=256,时成功复原出的信号百分比和测量数,N,的关系图,d=256,时成功复原出的信号百分比和稀疏度,m,的关系图,d=256,时成功复原,95%,的信号下测量数,N,和稀疏度,m,的关系图,d=1024,时实验和理论预测中成功复原出的信号百分比和测量数,N,的关系对比图,d=256,时采用伯努利测量矩阵时成功复原出的信号百分比和测量数,N,的关系图,采用伯努利测量矩阵时的计算消耗时间和稀疏度,m,的关系图,OMP,算法与传统的基追踪（,BP,）算法比较分析,1),一些情况下,BP,算法比,OMP,算法更强力,例如采取高斯或伯努利测量矩阵时,BP,算法能以很高概率复原出所有稀疏信号,在同样条件下,OMP,算法可以以很高概率复原出单个稀疏信号,但有很高概率不能复原出所有信号,.,2),考虑计算成本贪婪追踪算法更有优势,一定条件下,OMP,算法比,BP,算法速度更快,对高度稀疏的信号,OMP,算法尤为有效,.,3),贪婪算法,例如,OMP,在程序上更易于实现,.,结论,:,本文的理论和实验工作展示了相比于,BP,算法,OMP,算法是从随机测量值中恢复信号的另一有效选择,.,我们的结果相对于以前的工作有很大的进步,同时还拉近了贪婪算法的理论计算和线性规划的距离,.,基于这些事实,OMP,可能运行更快且更易于实现,提供了一种有吸引力的选择,.,或者说,贪婪还是一件好事,.,