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直接判断入选的原子集
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)_IT/计算机_专业资料。压缩感知理论(Compressive ...(2)贪婪匹配追踪(MP)算法 :从字典中一 个一个挑选向量,每一步都使得信号的...
K X K 如何找到信号最佳的稀疏域?这是压缩感知理论应用的基础和前提,只有选择...由于 l1 最小范数下的算法 速度慢,新的快速贪婪法被逐渐采用,如匹配追踪法(...
连续边缘的图像信号的Curvelet系数等都具有足够的 稀疏性,可以通过压缩感知理论...在稀疏分解算法的设计方面,基于贪婪迭代思想的MP(Matching Pursuit)算法表现出 ...
热门文档