贪婪算法与压缩感知理论

摘要

贪婪算法以其重建速度快、重建方法实现简便的特点在压缩感知(Compressed sensing,CS)理论中获得了广泛的应用.本文首先介绍压缩感知的基本理论；然后,着重介绍现有几种重要的贪婪重建算法,包括MP,OMP,IBOOMP,StOMP,SP,ROMP和CoSaMP等,详细给出每种算法的数学框架和本质思想,着重从最优匹配原子的选择策略和残差信号的更新方式这两个方面对各种算法进行对比分析,以限制等容常数为条件讨论各种算法在实现重建时的性能,包括重建时间、重建的稳定性等；最后,通过模拟实验进一步验证了各种算法的重建效果,同时模拟实验结果还进一步得出各种算法的重建效果与待重建信号本身的稀疏度及测量次数这三者之间的关系,这也为新的更优算法的提出打下理论基础.%Recently a family of iterative greedy algorithms have received extensive application in compressed sensing (CS) due to their fast reconstruction and low reconstruction complexity. In this paper, the basic theory of CS is first introduced and then we put emphasis on the main greedy algorithms for reconstruction, which include MP, OMP, IBOOMP, StOMP, SP, ROMP, CoSaMP and so on and provide their mathematical frameworks, respectively. Next, we classify all the algorithms according to the strategy of element selection and the update of the residual error. Under the condition of restricted isometry constant, further discussion on the performance of reconstruction algorithms such as running time, reconstruction stability and so on is presented. Last, the reconstruction results from simulated experiments further show the performance of all algorithms. And from those results we also acquire the relationship among the performance of the algorithms, the sparsity of signals to be reconstructed and the number of measurements, which lays a good basis for proposing new and better algorithms.