正交匹配追踪算法的迭代残差重建方法

付 敏, 王金平

正交匹配追踪算法的迭代残差重建方法

付 敏, 王金平*

（宁波大学 数学与统计学院, 浙江 宁波 315211）

正交匹配追踪(Orthogonal Matching Pursuit, OMP)算法是一种重要的压缩感知重构算法. OMP算法在每次迭代中选择与当前残差最相关的原子. 针对每次迭代需要重新计算残差的问题, 本文考虑偶数次迭代下残差未知的情况. 首先, 研究了奇数次迭代的残差与下一次迭代的残差之间的关系, 得到了一种偶数次迭代时选择原子的标准. 然后, 引入一种回溯机制来处理前面所得的迭代结果, 这种机制通过剔除其中多余的原子来实现精确重建. 据此, 提出了可减少计算残差的改进型正交匹配追踪算法.

稀疏重构; OMP算法; 回溯

压缩感知(Compressed Sensing, CS)理论[1]作为一种新的信号采样理论突破了传统Nyquist采样定理的限制, 它充分利用信号的稀疏性, 将高维信号没有损失地压缩采样成低维信号, 最后通过重构算法精确或高概率地重建原始信号. CS理论主要涉及稀疏表示、测量矩阵、重构算法等3个核心方面. 其中, 重构算法是将CS理论推向实用化的关键之一. 目前, 重构算法主要分为3类: (1)基追踪算法, (2)贪婪算法, (3)组合算法. 这些算法中, 贪婪算法因其结构简单易实现的优势而得到了广泛应用. OMP算法[2]是一种常用的压缩感知贪婪算法. 以OMP算法为原型, 研究者们提出了很多改进算法, 例如对原子正则化的正则化正交匹配追踪(Regularized OMP, ROMP)算法[3], 使用回溯思想的压缩采样匹配追踪(Compressive Sampling MP, CoSaMP)算法[4]和子空间追踪(Subspace Pursuit, SP)算法[5], 采用……