第37卷第12期2011年12月
自动化学报
ACTAAUTOMATICASINICA
Vol.37,No.12December,2011
贪婪算法与压缩感知理论
方红1
杨海蓉2
摘要贪婪算法以其重建速度快、重建方法实现简便的特点在压缩感知(Compressedsensing,CS)理论中获得了广泛的应用.本文首先介绍压缩感知的基本理论;然后,着重介绍现有几种重要的贪婪重建算法,包括MP,OMP,IBOOMP,StOMP,SP,ROMP和CoSaMP等,详细给出每种算法的数学框架和本质思想,着重从最优匹配原子的选择策略和残差信号的更新方式这两个方面对各种算法进行对比分析,以限制等容常数为条件讨论各种算法在实现重建时的性能,包括重建时间、重建的稳定性等;最后,通过模拟实验进一步验证了各种算法的重建效果,同时模拟实验结果还进一步得出各种算法的重建效果与待重建信号本身的稀疏度及测量次数这三者之间的关系,这也为新的更优算法的提出打下理论基础.关键词DOI
贪婪算法,压缩感知,限制等容常数,残差,稀疏度10.3724/SP.J.1004.2011.01413
GreedyAlgorithmsandCompressedSensing
FANGHong1
YANGHai-Rong2
AbstractRecentlyafamilyofiterativegreedyalgorithmshavereceivedextensiveapplicationincompressedsensing(CS)duetotheirfastreconstructionandlowreconstructioncomplexity.Inthispaper,thebasictheoryofCSis rstintroducedandthenweputemphasisonthemaingreedyalgorithmsforreconstruction,whichincludeMP,OMP,IBOOMP,StOMP,SP,ROMP,CoSaMPandsoonandprovidetheirmathematicalframeworks,respectively.Next,weclassifyallthealgorithmsaccordingtothestrategyofelementselectionandtheupdateoftheresidualerror.Undertheconditionofrestrictedisometryconstant,furtherdiscussionontheperformanceofreconstructionalgorithmssuchasrunningtime,reconstructionstabilityandsoonispresented.Last,thereconstructionresultsfromsimulatedexperimentsfurthershowtheperformanceofallalgorithms.Andfromthoseresultswealsoacquiretherelationshipamongtheperformanceofthealgorithms,thesparsityofsignalstobereconstructedandthenumberofmeasurements,whichlaysagoodbasisforproposingnewandbetteralgorithms.Keywords
Greedyalgorithms,compressedsensing(CS),restrictedisometryconstant,residualerror,sparsity
传统的Shannon/Nyquist采样定理指出,带限信号的采样频率必须大于其带宽的两倍以上才能确保由采样值完全重构原始信号,而压缩感知(Com-pressivesensing,CS)理论作为Shannon/Nyquist采样定理的另一种选择正在被广泛研究.CS理论是由Donoho[1]和Candes[2]从信号稀疏分解和逼近理论进一步发展的一种新的信号处理理论.该理论的提出者之一,美国科学院院士、斯坦福大学的统计学家Donoho在信号处理的众多领域,如信号稀疏分解、逼近理论、小波变换、图像压缩等都做
录用日期2011-07-14
ManuscriptreceivedSeptember6,2010;acceptedJuly14,2011上海市优秀青年教师科研专项基金(EGD08006),上海第二工业大学校基金(XQD208008),安徽高校省级自然科学研究项目(KJ2011B131)资助
SupportedbyResearchFundfortheExcellentYouthSchol-arsofMinistryofEducationofShanghai(EGD08006),Founda-tionofShanghaiSecondPolytechnicUniversity(XQD208008),andAnhuiProvincialNaturalScienceFoundationProject(KJ2011B131)
1.上海第二工业大学理学院上海2012092.合肥师范学院数学系合肥230601
1.SchoolofScience,ShanghaiSecondPolytechnicUniversity,Shanghai2012092.DepartmentofMathematics,HefeiNor-malUniversity,Hefei230601收稿日期2010-09-06
出了巨大贡献[3 4].CS理论的本质内容是稀疏或可压缩信号(在某个基上具有稀疏描述)的少量随机的线性投影即包含了重构和处理的足够信息,也就是仅仅利用信号稀疏或可压缩的先验和少量的全局线性测量可以获得精确重建.这个研究思想挑战了Shannon/Nyquist采样定理的理论极限,对整个信号处理领域产生了极其重要的影响.目前,在美国、英国、德国、法国、瑞士、以色列等许多国家的知名大学(例如麻省理工学院(MassachusettsIn-stituteofTechnology)、斯坦福大学(StanfordUni-versity)、普林斯顿大学(PrincetonUniversity)、莱斯大学(RiceUniversity)、杜克大学(DukeUni-versity)、慕尼黑工业大学(TechnicalUniversityofMunich)、爱丁堡大学(EdinburghUniversity)等)都成立专门课题组对CS进行研究;2008年西雅图Intel、贝尔实验室、Google等知名公司也开始组织研究CS,这使得信号处理的许多应用领域也随着CS理论的研究发生根本性的发展和变化[5 7].在CS理论中,随机编码的鲁棒性关键在于要使随机化测量具有相等的优先等级,这种随机编码与当前的变换编码(例如Fourier或Wavelet)中的系数不同,
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)算法表现出 ...
热门文档