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

报告人：汪琪组员：汪琪王心遥黄若思唐松柏徐露露通过正交匹配追踪算法从随机测量值中恢复信号通过正交匹配追踪算法从随机测量值中恢复信号共18页，您现在浏览的是第1页!原文标题：SignalRecoveryFromRandomMeasurementsViaOrthogonalMatchingPursuit作者：JoelA.Tropp,Member,IEEE,andAnnaC.Gilbert期刊号：IEEETRANSACTIONSONINFORMATIONTHEORY,VOL.53,NO.12,DECEMBER2007通过正交匹配追踪算法从随机测量值中恢复信号共18页，您现在浏览的是第2页!摘要： 本文从理论和实践上展示了一种名为正交匹配追踪（OMP）的贪婪算法可以在给定O(mlnd)个随机线性测量值下有效地恢复有m个非零元素的d维信号。相比以前需要O(m2）个测量值，这是一个很大的进步。OMP的新结果可以和另一种被称为基追踪（BP）的方法相比。在某些条件下OMP算法更快速且更容易实现，所以对信号恢复问题是除BP外另一种具有吸引力的选择。关键词： 算法，近似，基追踪，压缩感知，群组测试，正交匹配追踪，信号恢复，稀疏近似。通过正交匹配追踪算法从随机测量值中恢复信号共18页，您现在浏览的是第3页!对测量矩阵Φ的要求：

1)独立性:Φ的各列线性无关；2)归一化:对Φ的各列φj，j=1,2，…,d.||φj||22=1;3)独立相关性:{ut}为l2范数不超过1的m个向量组成的向量组,φ为Φ中与该向量组线性无关的一列,有4)最小奇异值:对于从Φ从取出的N×m维子矩阵Z,奇异值σm(Z)满足

通过正交匹配追踪算法从随机测量值中恢复信号共18页，您现在浏览的是第4页!OMP算法:输入:N×d维测量矩阵Φ;N维观测值v;理想信号稀疏度m.输出:理想信号的d维恢复信号s*

从{1,…,d}中选取的含有m个元素的指标集Λm 对v的n维近似向量am

n维残差向量rm=v-am通过正交匹配追踪算法从随机测量值中恢复信号共18页，您现在浏览的是第5页!判断算法成败:

从Rd中任意选取稀疏度为m的信号s,Φ为N×d维高斯矩阵,执行OMP算法v=Φs,若残差rm

在迭代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)通过正交匹配追踪算法从随机测量值中恢复信号共18页，您现在浏览的是第6页!d=256时成功复原出的信号百分比和测量数N的关系图通过正交匹配追踪算法从随机测量值中恢复信号共18页，您现在浏览的是第7页!d=256时成功复原95%的信号下测量数N和稀疏度m的关系图通过正交匹配追踪算法从随机测量值中恢复信号共18页，您现在浏览的是第8页! d=256时采用伯努利测量矩阵时成功复原出的信号百分比和测量数N的关系图通过正交匹配追踪算法从随机测量值中恢复信号共18页，您现在浏览的是第9页!OMP算法与传统的基追踪（BP）算法比较分析

1)一些情况下BP算法比OMP算法更强力,例如采取高斯或伯努利测量矩阵时,BP算法能以很高概率复原出所有稀疏信号,在同样条件下,OMP算法可以以很高概率复原出单个稀疏信号,但有很高概率不能复原出所有信号. 2)考虑计算成本贪婪追踪算法更有优势,一定条件下,OMP算法比BP算法速度更快,对高度稀疏的信号OMP算法尤为有效.3)贪婪算法,例如OMP,在程序上更易于实现.通过正交匹配追踪算法从随机测量值中恢复信号共18页，您现在浏览的是第10页!问题描述：

s为长度为d的真实信号，它的稀疏度为m，即含有m个非零元素。Φ为N×d的测量矩阵，v=Φs为长度为N的测量值。我们的问题即已知测量值v和测量矩阵Φ，恢复出真实信号s。由于测量值维数N小于真实信号维数d，故该方程组没有确定解，我们需要利用s的稀疏特性寻找出最优解。该算法即正交匹配追踪法（OMP）。算法思想:

贪婪迭代贪婪算法： 在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。

通过正交匹配追踪算法从随机测量值中恢复信号共18页，您现在浏览的是第11页!常用测量矩阵:1)高斯矩阵

Φ中的每个元素独立满足(0，1/N)的正态分布，概率密度函数p为

2)伯努利矩阵等概率独立选取Φ中的各元素为通过正交匹配追踪算法从随机测量值中恢复信号共18页，您现在浏览的是第12页!OMP算法:

1)初始化残差r0=v,指标集Λ0=ø,迭代计数t=1;2)找到满足下述最优化问题的指标λt

λt=argmaxj=1,…,d|<rt-1,φj>|3)扩充指标集和矩阵Λt=Λt-1∪{λt}及Φt=[Φt-1φλt],Φ0为空矩阵

4)解如下最小二乘问题

xt=argminx||v-Φtx||25)计算新的信号估计和残差:at=Φtxtrt=v-at6)t=t+1，若t<m返回步骤27)恢复信号x*的非零值指标为Λm中的元素,s*中第λj个元素的值等于xt的第j个元素

通过正交匹配追踪算法从随机测量值中恢复信号共18页，您现在浏览的是第13页!实验仿真:实验信号s为长度为d的一维信号,将其中随机m个值赋1,其余为0.

复原成功复原失败通过正交匹配追踪算法从随机测量值中恢复信号共18页，您现在浏览的是第14页!d=256时成功复原出的信号百分比和稀疏度m的关系图通过正交匹配追踪算法从随机测量值中恢复信号共18页，您现在浏览的是第15页! d=1024时实验和理论预测中成功复原出的信号百分比和测量数N的关系对比图通过正交匹配追踪算法从随机测量值中恢复信号共18页，您现在浏览的是第16页!采用伯努利测量矩阵时的计算消耗时间和稀疏度m的关系图通过正交匹配追踪算法从随机测量值中恢复信号共18页，您现在浏览的是第17页!结论:

本文的理论和实验工作展示了相比于BP算法