文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 工程科技 > 信息与通信 > 贪婪算法与压缩感知理论
侵权投诉

贪婪算法与压缩感知理论

1416自动化学报37卷

步)求出正交投影Pt,利用rt=y Pty的残差更新方式,克服了MP算法的次最优性.

算法2.

OMP算法

1)初始化冗余向量r0=y,索引集合Λ0=φ,迭代计数t=1;

度及重建精度,一次迭代选择多个原子的思想被采用到贪婪算法中.下面首先介绍ROMP和SP算法,分别见算法4和算法5.

算法4.

ROMP算法

1)初始化残差r0=y,指标集合I= ,迭代t=1,重复下面步骤m次或者直到|I|≥2m;

2)找到索引λt,使得:

λt=arg

j=1,2,···,N

max| rt 1,Φj |;

2)计算u= rt 1,Φj ;

3)原子选择准则:m个最大的非零坐标构成的集合或者它的所有非零坐标,选其中较小的坐标设为J;

3)令Λt=Λt 1∪{λt};

4)计算{Φλ:λ∈Λt}张成空间的正交投影Pt;5)计算新的近似a和冗余r:at=Pty,rt=y at;6)t=t+1,如果t<m,返回第2)步;

λ在索引Λm位置的元非零,且在该位置的7)获得的估计s

测量向量逼近为:am=

λ∈Λm

4)正则化:在所有具有可比较坐标的子集J0 J中:|u(i)|≤2|u(j)|,对所有的i,j∈J0,选择具有最大能量 u|J0 l2的集合J0;

5)更新:增加J0到指标集:I←I∪J0,更新残余:

x=argmin y Φz l2,r=y Φx

z∈RI

λΦλ.s

OMP与MP的共同缺点在于原子选择机制相

对于新的冗余误差的非最优性,也就是说待选原子一旦进入支撑候选中,则永久添加不会再被删除,缺少“回溯”的思想.这里“回溯”表示在当前迭代的步骤中,仍对上次迭代中所入选的原子进行同步检验,如果仍然满足当次最优意义则保留,否则剔除作为下次待选.其意义在于它可以最大程度保证重建的全局最优性,因为在某次迭代中达到贪婪条件的原子并不能保证在以后迭代步骤中仍能达到,所有原子都应做到“删除”和“添加”自由,这种思想在后续产生的多种贪婪算法中得到了广泛的应用.针对OMP中原子选择机制的缺点并引入简单的“回溯”思想,本文作者提出了IBOOMP算法[30],见算法3.

算法3.

IBOOMP算法

1)初始化冗余r0=y,记γj=Φj,j=1,2,···,N,取索

引λ1=argmax1≤j≤N| Φj,y |,索引集合Λ1={λ1},正交投影函数ψ1=Φλ1=β1和分解系数c1= Φλ1,y ,迭代计数t=1;

2)对j=1,2,···,N,分别计算:

γj=γj ψj ψt,Φt ,bj= γj,y ,dj=dj | ψt,Φj |2,ej=|bj|2/dj;

3)令t=t+1,寻找λt,使得λt=argmax1≤j≤Nej,记索引集合Λt=Λt 1∪{λt}.分别记:

γλγ

t

Rt 2= Rt 1 2 eλt,ψt=,βt=dλt;

λt

λt

算法5.SP算法

={相应于ΦTy的绝对值最大的m个指标}1)初始化:T

yr=resid(y,ΦT );

2)迭代:如果yr=0,迭代停止;否则继续;

∪{相应于ΦTyr的绝对值最大的m个指标}3)T =T

x p=ΦT y,T={相应于xp最大元的m个指标},

r=resid(y,ΦTy );

r l2> yr l2,迭代停止;否则,设4)更新:若 y

=T 以及yr= yr,继续迭代;T

{1,2,···,N} T 输出:满足x =0和xT =ΦT y的估计信号x.

4)对j=1,2,···,t 1计算新的投影和分解系数:

βj+1=βj βt Φλt,βj ,cj+1=cj Φλt,j ct;

5)重复2)~4)直到对于给定的小的正数δ,满足

Rt 2≤δ时,迭代停止,并得到系数估计向量c,且|c|=M>m;

6)归一化c并向后剔除多余M m元素.

模拟实验证明:IBOOMP算法在相对误差一定的条件下较大程度地减少了重建对测量次数的要求,但是它与MP及OMP具有相同的最优原子选择机制,每次迭代只选择一个原子,为进一步提高重建速

ROMP和SP具有相同的原子选择机制,每次迭代都以ΦTyr(yr表示当前冗余)中前m个绝对值最大的非零坐标所对应的原子作为候选;其中,ROMP利用正则化的方法找出候选原子集合中能量最大的原子集合J0,在所有支撑集为J0的稀疏信号中利用最小二乘法找出使得 y Φz l2最小的解x作为当前估计,并以y Φx作为残差更新公式,没有“回溯”的思想,每次迭代都在一个“可靠”候选集中选择出满足正则条件的原子添加到上次迭代中,并且这些原子一直保持到迭代停止.SP与ROMP在残差更新方式上则不同,它以相邻两次迭代冗余的差作为迭代停止条件,每次迭代中在当次迭代支撑和前次迭代支撑集合的并集(T )上利用

最小二乘求出当前估计xT =ΦT y,可见SP采用了“回溯”思想,与ROMP相比更好地保证了重建的最优性.

然而,SP算法也有其自身的缺点,尽管在每次迭代更新都能保证新的原子的增加(取并集),但是在当次支撑集合上,并没有对利用最小二乘所求出的解进行定量的评估(即增加或删除原子对误差冗余的影响),同时也不能给出当次迭代残差一定小于前次迭代残差的理论保证.针对这两个缺点,文献[39]中给出一种改进的SP算法—逐步最优的子空间追踪(StepwiseoptimalSP,SOSP).SOSP算法

上一页第4页

你可能喜欢

热门文档

相关文档

  • 贪婪算法与压缩感知理论

    37, No. 12 December, 2011 贪婪算法与压缩感知理论方 红1 杨海蓉 2 摘要 贪婪算法以其重建速度快、 重建方法实现简便的特点在压缩感知 (Compressed sensing, ...

  • 一种基于贪婪基追踪算法的压缩感知超宽带信道估计方法

    因此,如何设计出计算复 杂度低、稳定且所需观测数较少的重构算法已成为目 前压缩感知理论的一个热点问题 [8]。 Huggins和Zucker等人于2006提出的贪婪基追踪算 法...

  • 压缩感知算法

    和 Candes 等人[1,2]在稀疏表 示和优化理论的基础上提出的一种成像理论。...模型化压缩感知重构算法利用贪婪搜索的方法 寻找最优小波系数子树集,而这些最优...

  • 一种贪婪自适应压缩感知重构

    10.3969/j.issn.1001-2400.2012.03.008 一种贪婪自适应压缩感知重构甘 伟 ...针对 CoSaMP 算法关于信号稀疏度的非自适应性问题, 本文通过采用具有理论保证的...

  • 一种贪婪自适应压缩感知重构

    0.9 9ji n 1 0-4 0.0 2.3.0 s 一种贪婪自适应压缩感知重构甘 伟, ...算法该 采用了具有理论保证的模糊阈值预选方案以 避免预选时使用信号的先验信息,...

  • 压缩感知理论及其重构算法

    压缩感知理论及其重构算法_工学_高等教育_教育专区。压缩感知算法...东莞理 工学院学报 年 匹配跟踪 算法匹 配跟 踪算法是一种迭代贪婪算法 , ...

  • 压缩感知理论及其重构算法

    12压 缩感 知信号表示 . 为 了避 免上 述缺点 ,压缩感知理论不需要获取J ...生QQ 匹配 跟 踪算 法 是一 种迭代贪婪算法 ,它 是通 过对一系列 的单 ...

  • 压缩感知理论(Compressive)

    压缩感知理论(Compressive)_IT/计算机_专业资料。压缩感知理论(Compressive ...(2)贪婪匹配追踪(MP)算法 :从字典中一 个一个挑选向量,每一步都使得信号的...

  • 压缩感知理论综述(原创)

    K X K 如何找到信号最佳的稀疏域?这是压缩感知理论应用的基础和前提,只有选择...由于 l1 最小范数下的算法 速度慢,新的快速贪婪法被逐渐采用,如匹配追踪法(...

  • 压缩感知原理

    连续边缘的图像信号的Curvelet系数等都具有足够的 稀疏性,可以通过压缩感知理论...在稀疏分解算法的设计方面,基于贪婪迭代思想的MP(Matching Pursuit)算法表现出 ...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email