1414自动化学报37卷
它同时具有通用性、加密性、鲁棒性和可渐近性、可缩放性、计算的非对称性.同时,这种随机编码过程非常简单,仅需计算非相干投影而不做任何其他的处理.从而,可以把大部分的计算复杂性都放在解码器上.换句话说,这种随机编码采用了“少采样,后计算”的原则,把技术的负担从传感器转移到处理器上.因此,高效、快速、鲁棒的重建算法是将CS理论推向实用化的关键之一,也是CS理论研究的核心内容之一.
1基于CS理论的重建算法
目前基于CS理论的重建算法主要分成4类:凸优化方法、组合算法、统计优化方法及贪婪算法.凸优化方法的本质思想是针对最小化 1模提出的线性规划方法,现有的凸优化方法主要包括基追踪(Ba-sispursuit,BP)[8],梯度投影稀疏重建(Gradientprojectionforsparsereconstruction,GPSR)[9],迭代阈值法(Iterativethresholding,IT)[10],迭代硬阈值法(Iterativehardthresholding,IHT)[11]以及Bregman迭代法(Bregmaniterative,BI)[12 15]等.在4类重建算法中凸优化方法给出了最强的稀疏恢复的保证,在测量矩阵满足一定的条件下它能精确重建所有的稀疏信号,同时需要测量的次数也较少,然而,其最大的缺点在于重建速度慢,对于大尺度的重建问题实现困难;组合算法的本质思想是针对信号进行高度的结构化采样,经由群测试来快速获得信号支撑,主要包括稀疏傅里叶描述法[16],链追踪(Chainingpursuit,CP)[17],以及HHSP追踪(Heavyhittersonsteroidspursuit,HHSP)[18 19]等,组合算法所需要的测量次数较凸优化方法少,重建速度也较快,但是它只给出了在测量次数一定的条件下可以以高概率获得任何可压缩信号重建的保证而不是精确保证,同时组合算法没有给出确定性测量矩阵的限制条件,只是针对特定矩阵给出理论证明,这也为新的测量矩阵的提出带来困难.目前的统计优化方法主要包括两类:一类是贝叶斯统计框架下的稀疏重建算法[20 22];另一类是基于训练集合学习的统计优化方法[23],该方法的思想类似于主成分或者独立成分分析,利用典型信号的训练集通过学习的方法找出最优的线性投影集合.统计优化方法能在精确和非精确测量条件下给出精确重建信号的保证,它所需要的测量次数较凸优化方法多,但是重建时间较凸优化方法少,较好地平衡了重建中对测量次数和测量时间的要求.在CS理论中,由于图像重建过程可以看作已知信号在给定冗余字典上获得最稀疏分解的过程,而贪婪算法在信号稀疏分解任务中已经得到了成熟的应用,因此,借助于信号稀疏分解的思想,贪婪算法就很自然地被应用到CS
理论中.目前贪婪算法的种类很多,主要包括匹配追踪(Matchingpursuit,MP)[24]、正交匹配追踪(Or-thogonalmatchingpursuit,OMP)[25]、分级正交匹配追踪(Stagewiseorthogonalmatchingpursuit,StOMP)[26]、正则化的正交匹配追踪(Regularizedorthogonalmatchingpursuit,ROMP)[27]、压缩采样匹配追踪(Compressivesamplingmatchingpur-suit,CoSaMP)[28]、子空间追踪(Subspacepursuit,SP)[29]及改进的后退型OOMP(Improvedback-wardoptimizedOMP,IBOOMP)[30]等.贪婪算法是4类算法中重建速度最快的算法,尽管最初提出的OMP算法在重建效率上并不是很理想,但是随后提出的各种改进算法无论是在重建速度还是重建精度上都得到了很大改进.
本文首先介绍压缩感知的基本理论;其次,着重介绍现有几种重要贪婪重建算法,详细给出每种算法的数学框架,并根据算法中最优匹配原子的选择机制与残差更新方式的不同进行分类解析,以限制等容常数为条件来讨论各种算法在实现重建时的性能;最后,通过模拟实验对各种算法进行性能验证.
2CS理论
CS理论的本质是一种非适应性的、非线性的可压缩信号的重建方法.其主要内容是:在某组基(称为稀疏基)Ψ=[ψ1,ψ2,···,ψN]上具有m-稀疏描述的N采样的信号x∈RN,即
x=
N n=1
θ(n)ψn=
m l=1
θ(nl)ψ(nl)
可以通过它在另一组非相干的基(称为测量基)TT
Φ=(φT1,φ2,···,φM)上的M(m≤M<<N)
T
个线性投影y(i)= x,φi ,i∈{1,2,···,M}获得精确重建.利用矩阵的形式,测量过程可以记为y=Φx=ΦΨα.其中,α表示m-稀疏变换系数向量,称M维列向量y为测量向量,称由测量基Φ构成的M×N维矩阵为测量矩阵.其目标是通过M(M<<N)次测量得到的测量向量y精确重建或者逼近信号x.
由条件m≤M<<N可以看出CS理论主要解决的是欠采样情况下的信号重建问题.由于M<<N,从而使得信号x的重建本质上成为一个病态求逆问题,但是原始信号x自身的稀疏性是使得从少量测量恢复信号成为可能的第一个原因,而第二个原因则在于测量基与稀疏基之间的不相关性,因此,为保证重建测量矩阵必须满足一定的限制条件.Candes等[31]给出如下结论:为了重建稀疏或可压缩信号,测量矩阵Φ要满足一定参数的限制等容条件(Restrictedisometryproperty,RIP).下面我
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)算法表现出 ...
热门文档