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

《通过正交匹配追踪算法从随机测量值中恢复信号.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、报告人：汪琪组员：汪琪王心遥黄若思唐松柏徐露露通过正交匹配追踪算法从随机测量值中恢复信号原文标题：SignalRecoveryFromRandomMeasurementsViaOrthogonalMatchingPursuit作者：JoelA.Tropp,Member,IEEE,andAnnaC.Gilbert期刊号：IEEETRANSACTIONSONINFORMATIONTHEORY,VOL.53,NO.12,DECEMBER2007摘要：本文从理论和实践上展示了一种名为正交匹配追踪（OMP）的贪婪

2、算法可以在给定O(mlnd)个随机线性测量值下有效地恢复有m个非零元素的d维信号。相比以前需要O(m2）个测量值，这是一个很大的进步。OMP的新结果可以和另一种被称为基追踪（BP）的方法相比。在某些条件下OMP算法更快速且更容易实现，所以对信号恢复问题是除BP外另一种具有吸引力的选择。关键词：算法，近似，基追踪，压缩感知，群组测试，正交匹配追踪，信号恢复，稀疏近似。问题描述：s为长度为d的真实信号，它的稀疏度为m，即含有m个非零元素。Φ为N×d的测量矩阵，v=Φs为长度为N的测量值。我们的问题即已知测量

3、值v和测量矩阵Φ，恢复出真实信号s。由于测量值维数N小于真实信号维数d，故该方程组没有确定解，我们需要利用s的稀疏特性寻找出最优解。该算法即正交匹配追踪法（OMP）。算法思想:贪婪迭代贪婪算法：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。对测量矩阵Φ的要求：1)独立性:Φ的各列线性无关；2)归一化:对Φ的各列φj，j=1,2，…,d.

4、

5、φj

6、

7、22=1;3)独立相关性:{ut}为l2范数不超过1的m个向量组成的向量组,φ为Φ

8、中与该向量组线性无关的一列,有4)最小奇异值:对于从Φ从取出的N×m维子矩阵Z,奇异值σm(Z)满足常用测量矩阵:1)高斯矩阵Φ中的每个元素独立满足(0，1/N)的正态分布，概率密度函数p为2)伯努利矩阵等概率独立选取Φ中的各元素为OMP算法:输入:N×d维测量矩阵Φ;N维观测值v;理想信号稀疏度m.输出:理想信号的d维恢复信号s*从{1,…,d}中选取的含有m个元素的指标集Λm对v的n维近似向量amn维残差向量rm=v-amOMP算法:1)初始化残差r0=v,指标集Λ0=ø,迭代计数t=1;2)找到满

9、足下述最优化问题的指标λtλt=argmaxj=1,…,d

10、

11、3)扩充指标集和矩阵Λt=Λt-1∪{λt}及Φt=[Φt-1φλt],Φ0为空矩阵4)解如下最小二乘问题xt=argminx

12、

13、v-Φtx

14、

15、25)计算新的信号估计和残差:at=Φtxtrt=v-at6)t=t+1，若t

16、在迭代m次后为0，则OMP完全复原了信号s,否则若残差在迭代m次后不为0则OMP失败了.OMP算法成功率:取δ为(0,0.36)中一定值,取N≥Kmlog(d/δ),其中K为绝对常数.s是从Rd中任意选取稀疏度为m的信号,Φ维N×d维测量矩阵,已知测量值v=Φs,OMP算法能成功恢复信号的概率为1-δ.时间复杂度:O(mNd)实验仿真:实验信号s为长度为d的一维信号,将其中随机m个值赋1,其余为0.复原成功复原失败d=256时成功复原出的信号百分比和测量数N的关系图d=256时成功复原出的信号百分比和稀

17、疏度m的关系图d=256时成功复原95%的信号下测量数N和稀疏度m的关系图d=1024时实验和理论预测中成功复原出的信号百分比和测量数N的关系对比图d=256时采用伯努利测量矩阵时成功复原出的信号百分比和测量数N的关系图采用伯努利测量矩阵时的计算消耗时间和稀疏度m的关系图OMP算法与传统的基追踪（BP）算法比较分析1)一些情况下BP算法比OMP算法更强力,例如采取高斯或伯努利测量矩阵时,BP算法能以很高概率复原出所有稀疏信号,在同样条件下,OMP算法可以以很高概率复原出单个稀疏信号,但有很高概率不能复原

18、出所有信号.2)考虑计算成本贪婪追踪算法更有优势,一定条件下,OMP算法比BP算法速度更快,对高度稀疏的信号OMP算法尤为有效.3)贪婪算法,例如OMP,在程序上更易于实现.结论:本文的理论和实验工作展示了相比于BP算法,OMP算法是从随机测量值中恢复信号的另一有效选择.我们的结果相对于以前的工作有很大的进步,同时还拉近了贪婪算法的理论计算和线性规划的距离.基于这些事实,OMP可能运行更快且更易于实现,提供了一种有吸引力的选择.或者说,贪婪