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

贪婪算法与压缩感知理论

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

们首先给出RIP的定义.

定义1(RIP).对矩阵Φ∈RM×N,若对所有满足|I|≤m<M的索引集合I {1,2,···,N}及任意向量v∈R|I|,存在常数0<δ<1,使得:

3贪婪算法

3.1信号稀疏重建与信号稀疏分解

在CS理论中,稀疏信号的重建即通过该信号在已知测量矩阵Φ上的M个非相干的线性投影y=Φx来获得重建.由于待重建信号x仅有m个非零元,因此,测量向量y可以看作Φ中m个列向量的线性组合.那么,利用y和Φ重建x就等价于在测量向量集合Φ中准确找到参与测量的m个列向量(原子).这用稀疏分解的语言来描述即:获得向量y在冗余字典Φ(M<N)上精确的m-稀疏描述,而所求的x就是该分解所获得的系数向量.因此,CS理论中的稀疏或可压缩信号的重建问题可以简单地看成信号稀疏分解过程,但是两者之间也存在着一定的区别,稀疏分解的目的是用尽可能少的原子去稀疏描述原始信号,所求描述中原子的个数越少越好,而稀疏重建的目的则是精确找到参与测量的原子,重建的精度取决于原子寻找的正确度而不是原子的个数.

(1 δ) v l2≤ ΦIv l2≤(1+δ) v l2

(1)

成立,则称该矩阵为满足参数(m,δ)的RIP,其中:ΦI表示由索引集合I {1,2,···,N}所指的Φ中列向量所构成的子矩阵,而使得式(1)成立的所有参数δ的下确界称作限制等容常数(Restrictedisometryconstant,RIC),记为δm.

性质1(RIC与特征值).如果测量矩阵Φ∈RM×N为具有参数(m,δ)的RIP,那么对所有满足|I|≤m的集合I {1,2,···,N},有:

T

1 δm≤λmin(ΦTIΦI)≤λmax(ΦIΦI)≤1+δm(2)

这里λmin和λmax分别表示矩阵的最小和最大特征值.

1)分析1:根据式(1)在理想状态下,即当δ=0时,则 v l2≤ ΦIv l2≤ v l2成立,即 ΦIv l2= v l2,此时,ΦI类似一个完全正交系统,保持了信号的全部能量,从而使得信号的精确重建成为可能;当0<δ<<1时,从空间几何的角度来看,此时测量系统几乎保持了不同稀疏信号之间的l2模距离,从而保证了重建的稳定性;为了保证稀疏信号的精确重建,则要在尽可能少的采样条件下,寻找具有较小的限制等容常数δm和较大参数m的测量矩阵.

2)分析2:从式(2)可以看出为了计算RIC,需

m

要计算CN个子矩阵的最大最小特征值,因此,确定矩阵的RIC的计算是一个NP难问题.目前关于RIP的研究主要针对不同算法给出可以获得精确重建的RIC条件,例如文献[32]中证明了当测量矩阵Φ的RIC满足δm+δ2m+δ3m<1时,基于最小化l1模的线性规划方法可以获得所有m-稀疏信号的精确重建;文献[33]中将条件修改为√δ3m+3δ4m<2;文献[34]中给出RIC满足δ2k< 1的充分条件的证明;文献[35]中又将条件修改为δ2k<0.4531;文献[36]中进一步将条件修改为δ2k<0.472.而最近,文献[37]中又给出更理想的充分条件形式δk<0.307,并证明了这个δk上限不可再被实质性的修改.

目前满足一定RIP的测量矩阵有很多,其中包括高斯随机测量矩阵、贝努里随机测量矩阵、部分傅里叶随机矩阵及文献[38]中提出的稀疏投影矩阵和非常稀疏投影矩阵等.本文中,为实现简便,我们都采用高斯随机测量矩阵,在下面的理论讨论中,不失一般性,假设信号为绝对稀疏信号.

3.2贪婪算法的数学框架

贪婪算法的基本思想就是通过迭代的方法依次找出待重建信号的支撑,基于某种贪婪准则一次求出一个或多个待估信号的构成元素.以MP和OMP为代表的贪婪算法,其寻找x信号支撑的思想最为简单,即每次迭代以对应ΦTy中绝对值最大元的列作为支撑候选,一次迭代确定一个入选原子,见算法1和算法2.

算法1.

MP算法

1)初始化冗余向量r0=y,迭代计数t=1;2)找到索引λt,使得:

λt=arg

j=1,2,···,N

max| rt 1,Φj |;

3)计算新的近似at和冗余rt:

at= rt 1,Φλt Φλt,

rt=rt at

4)t=t+1,如果t<K,返回第2)步.

MP算法与OMP算法具有相同的最优原子选择策略,每次迭代均以测量矩阵Φ中与当次冗余向量rt 1具有最大内积的列向量作为待估信号的支撑候选.但是两者在残差信号的更新方式上不同,MP算法由其最新误差rt与当次所选原子Φλt的正交性( rt,Φλt = rt 1 at,Φλt =0)来保证算法的收敛性,然而这点仅保证了冗余向量rt与Φλt的正交性,而不能保证rt与已选原子集合{Φλ1,Φλ2,···,Φλt}的正交性,这使得MP求得的近似解在最优K项近似的意义下都是次最优的,这也是MP算法需要较多次数的迭代才能保证收敛的原因.OMP算法通过递归的对已选原子集合正交化(见算法2中的第4)

上一页第3页

你可能喜欢

热门文档

相关文档

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

    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