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

贪婪算法与压缩感知理论

12期方红等:贪婪算法与压缩感知理论1417

中,通过交替使用GreedyAdd和GreedyRemove这两个步骤,以严格保证冗余误差递减的原则,在当前支撑候选中删除或者添加原子.本质上说,SOSP

的进一步优化.区别SP主要在于对候选支撑T

最后我们介绍StOMP和CoSaMP算法,见算法6和算法7.

算法6.

StOMP算法

合,利用最小二乘求出待估信号在所得支撑上的系数,其缺点在于阈值参数选择较难;CoSaMP则在每次迭代中计算代理信号(即ΦTrs 1)中前2m个最大元所对应的支撑与前次逼近解的支撑并作为当次候选支撑,再利用最小二乘求出该支撑上的系数估计.从算法6的第4)步和算法7的第3)步可以看出两者都采用了“回溯”思想.

1)初始解x=0,初始残差r0=y,计数器s=1;2)第s阶段,计算Cs=ΦTrs 1= Φ,rs 1 ;3)设立软阈值h=tsσs,获得该阈值下的原子集合Js={j:|Cs(j)|>tsσs},其中,规范噪音水平为σs=

√

rs l2/,阈值参数2≤ts≤3;

4)Is=Is 1∪Js,计算支撑Is上的逼近系数向量:

1T

(xs)Is=(ΦTΦIsy;IsΦIs)

3.3算法的性能比较

在给出上述贪婪算法的数学框架后,我们以δm

为条件来讨论各种算法的性能.尽管RIP给出了通过算法可以获得重建的一个充分条件,但是由RIP的定义可知,为了获得更好的重建,我们希望在尽可能少的测量次数的条件下,获得尽可能小的限制等容常数,这是因为δm越小则整个测量系统的正交性越强,然而越是小的限制等容常数的RIP越难获得.

1)以OMP为代表的一次迭代选择一个原子的贪婪算法,没有给出确定的RIP条件保证,只是在精确测量的条件下,针对特殊的测量矩阵,例如高斯和贝努里随机测量矩阵等分别给出了获得近似重建的概率,既没有精确重建的保证也不能保证重建的稳定性,程序的运行时间取决于算法的第2)步,因此时间为O(mMN).

2)ROMP算法给出了噪声测量y=Φx+e下获得近似测量的保证,这里e表示误差向量,文献[27]中指出只要测量矩阵满足参数为(4m,δ)的

√

RIP,其中,δ=0.01/则对任意稀疏度为

l2≤m的向量都可以获得重建精度范围为 x x

√

e l2的结果,而当e=0时,可以获得精确重建,ROMP算法虽然添加了正则化的步骤,但是并没有额外增加运行时间,其总的运行时间与OMP相当.

3)SP算法在精确测量的条件下也能给出精确重建的保证,条件是测量矩阵必须满足参数(3m,0.06)为RIP,而在误差噪声测量条件下,SP

1+δ3m

l2≤δ3m则给出了重建误差为 x x e l2的(1 δ3m)

保证.SP运行时间可以达到O(log(m)MN).

4)StOMP算法最大的优点在于重建速度较快,能较好地解决高维信号的重建问题,但是它和OMP一样需要精确测量的保证,也不能给出确定的RIP条件,只能针对某些特殊矩阵给出一定的重建保证,其运行时间接近O(MN).

5)CoSaMP在测量矩阵满足(4m,0.1)的RIP的条件下给出了噪声测量的重建保证,与ROMP和SP不同的是,CoSaMP可以对任意噪声测量下保证重建,但是在精确测量的条件下并不能保证精确重建,其运行时间下限为O(MN).

总结前面的分析给出算法的性能对照,见表1.

5)更新残差为:rs=y Φxs;

6)检查终止条件(例如s=10),若未到停止时间,则假设 s=xs,s=s+1,转到第2)步,若到达停止时间,设x为算法的最终输出.

算法7.CoSaMP算法

输入:采样矩阵算子Φ,噪音测量向量y,稀疏度m输出:待估信号x一个m-稀疏逼近a

1)初始解a0=0,初始残差r0=y,计数器s=1;2)计算信号代理:c=ΦTrs 1;

3)鉴定大的成分,合并支撑集: =supp(c2m),T= ∪supp(as 1);

4)通过最小二乘法的信号估计:b|T=Φ Ty,b|Tc=0从而获得新的逼近as=bm;5)更新残差:rs=y Φas;

6)若满足停止标准,则输出a=as,若不满足,则可以令s=s+1,回到第2)步.

StOMP与CoSaMP在本质上都采用了“代

理”的思想,即如果测量矩阵满足限制等容常数δm<<1,则向量v=ΦTΦx=ΦTy可以看做待估信号x的一个“代理”,其合理性在于:根据RIC的定义,当δm<<1时,v中每m个元素构成的集合所包含的信息近似于x中m个元素所构成的集合,那么从v中前m个最大元所对应的支撑也应该对应于这些元素在x中的支撑.StOMP与CoSaMP的区别在于最优匹配原子的选择机制不同,StOMP通过设立软阈值h=tsσs直接判断入选的原子集

上一页第5页

你可能喜欢

热门文档

相关文档

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

    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