贪婪算法与压缩感知理论

摘要：

贪婪算法以其重建速度快、重建方法实现简便的特点在压缩感知(Compressed sensing,CS)理论中获得了广泛的应用.本文首先介绍压缩感知的基本理论；然后,着重介绍现有几种重要的贪婪重建算法,包括MP,OMP,IBOOMP,StOMP,SP,ROMP和CoSaMP等,详细给出每种算法的数学框架和本质思想,着重从最优匹配原子的选择策略和残差信号的更新方式这两个方面对各种算法进行对比分析,以限制等容常数为条件讨论各种算法在实现重建时的性能,包括重建时间、重建的稳定性等；最后,通过模拟实验进一步验证了各种算法的重建效果,同时模拟实验结果还进一步得出各种算法的重建效果与待重建信号本身的稀疏度及测量次数这三者之间的关系,这也为新的更优算法的提出打下理论基础.

关键词：贪婪算法、压缩感知、限制等容常数、残差、稀疏度

所属期刊栏目：37

分类号：TP301.6(计算技术、计算机技术)

资助基金：上海市优秀青年教师科研专项基金EGD08006;上海第二工业大学校基金XQD208008;安徽高校省级自然科学研究项目KJ2011B131

在线出版日期：2012-03-20（万方平台首次上网日期，不代表论文的发表时间）

页码：1413-1421