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

文档介绍：通过正交匹配追踪算法从随机测量值中恢复信号
原文标题:
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个非零元素。Φ为N×d的测量矩阵,v= Φs为长度为N的测量值。我们的问题即已知测量值v和测量矩阵Φ,恢复出真实信号s。由于测量值维数N小于真实信号维数d,故该方程组没有确定解,我们需要利用s的稀疏特性寻找出最优解。该算法即正交匹配追踪法(OMP)。
算法思想:
贪婪迭代
贪婪算法:
在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。
对测量矩阵Φ的要求:
1) 独立性: Φ的各列线性无关;
2) 归一化: 对Φ的各列φj,j=1,2,…,d. || φj||22=1;
3) 独立相关性: {ut}为l2范数不超过1的m个向量组成的向量组, φ为Φ中与该向量组线性无关的一列,有
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维近似向量am
n维残差向量rm=v-am
OMP算法:
1) 初始化残差r0=v,指标集Λ0=ø,迭代计数t=1;
2) 找到满足下述最优化问题的指标λt
λt=arg max j=1,…,d|<rt-1, φj>|
3) 扩充指标集和矩阵Λt=Λt-1∪{λt}及Φt=[Φt-1 φλt], Φ0为空矩阵
4) 解如下最小二乘问题
xt=arg min x||v- Φtx||2
5) 计算新的信号估计和残差: at=Φtxt rt=v-at
6) t=t+1,若t<m返回步骤2
7) 恢复信号x*的非零值指标为Λm中的元素,s*中第λj个元素的值等于xt的第j个元素
判断算法成败:
从Rd中任意选取稀疏度为m的信号s, Φ为N×d维高斯矩阵,执行OMP算法v=Φs,若残差rm 在迭代m次后为0,则OMP完全复原了信号s,否则若残差在迭代m次后不为0则OMP失败了.
OMP算法成功率:
取δ为(0,)中一定值,取N≥Kmlog(d/ δ),, Φ维N×d维测量矩阵,已知测量值v=Φs, OMP算法能成功恢复信号的概率为1- δ.
时间复杂度:
O(mNd)
实验仿真:
实验信号s为长度为d的一维信号,将其中随机m个值赋1,其余为0 .
复原成功
复原失败