CS的OMP算法

资 源 简 介

CS的OMP算法

详 情 说 明

正交匹配追踪（OMP）是压缩感知中经典的贪婪算法，用于从少量线性测量中重建稀疏信号。其核心思想是通过迭代选择与当前残差最相关的原子（即测量矩阵的列向量），逐步逼近原始信号。

算法流程可分为以下步骤： 初始化残差为观测信号，支撑集为空 每次迭代选择与残差相关性最强的原子加入支撑集 通过最小二乘更新对支撑集原子的系数估计 更新残差并检查停止条件（如达到预定稀疏度或残差阈值）

OMP的优势在于实现简单且收敛速度快，但要求信号具有严格稀疏性。其性能受三个关键因素影响： 测量数：恢复成功率随测量数增加呈指数上升，但存在临界阈值 信号稀疏度：当非零元数量超过一定比例时，性能急剧下降 测量矩阵特性：满足RIP条件的矩阵（如高斯随机矩阵）表现更优

典型实验结果会显示： 相位过渡图：展示不同稀疏度/测量数组合下的成功恢复区域 蒙特卡洛曲线：固定稀疏度时，成功率随测量数增长的变化趋势 噪声鲁棒性测试：信噪比对重构误差的影响

注意OMP与基追踪(BP)的区别——前者是贪婪迭代而后者是凸优化方法，OMP计算效率更高但需要更强的稀疏假设。现代改进版本如CoSaMP加入了回溯机制提升稳定性。