4.3. 正交匹配追踪¶
4.3.1. 什么是正交匹配追踪¶
正交匹配追踪 (Orthogonal Matching Pursuit , OMP) 是一种信号稀疏分解方法, 由 Pati 等人 [10] 于1993年提出, OMP被广泛用于稀疏信号恢复 [11]. 稀疏分解旨在将信号分解为过完备字典中的尽可能少(稀疏)的原子的线性组合, 从而获得信号的简洁有效的表示.
4.3.2. 正交匹配追踪算法¶
正交匹配追踪算法步骤见算法1 [11].
注解
算法1: 正交匹配追踪算法步骤
输入: 列归一化过完备字典矩阵 , 观测向量 , 待恢复信号稀疏度 , 容忍残差模值
输出: 待估计稀疏信号 , 索引集合 , 观测向量近似 和残差向量
Step1: 初始化稀疏信号 , 残差 , 索引集合(支撑) , 迭代计数器 .
Step2: 选择与残差最相关的原子, 即求解索引 满足优化问题
Step3: 更新索引集 .
Step4: 求解新的最小二乘优化问题
求得的稀疏系数解为
Step5: 计算新的投影近似, 残差
Step6: 更新迭代计数器 若 且 , 重复 Step2 至 Step5, 否则停止迭代, 转 Step7.
Step7: 输出 , , . 其中, 在位置 处非零.
警告
待查证是否有相关文献, 没有的话, 是否可以发表 实际迭代过程中, 在求解逆矩阵 时容易出现其奇异的情况, 可以通过求解 来代替, 其中 .
提示
记 , 易知 为正交投影矩阵(线性投影), 将向量投影到由 的元素(类比坐标系)张成的线性空间中, 从而 , 则投影后的误差可以表示为
其中, 为残差中的信号成份, 为残差中的噪声成份.
4.3.3. 实验与分析¶
主要分析OMP算法在信号稀疏分解上的性能, 有关OMP在压缩感知中的应用参见 稀疏信号实验 小节.
仿真数据实验¶
实验中通过仿真生成含有三个频率成分的信号 , 仿真参数设置如下:
频率成分:
采样频率:
采样时间:
采样点数:
构造过完备DCT字典(参见 过完备DCT字典), 字典大小为 , 其中 , 为一可调变量, 通过OMP求解稀疏系数 , 并利用 式.4.1 恢复信号 .
实现代码, 参见文件 demo_omp_sin3_decomposition.py .
仿真生成的信号 如下图(左)所示, 其DCT变换后的系数如下图(右)所示
如图中所示, 三种频率成分对应六个峰, 峰的位置为频率的二倍(这是因为DCT变换中分母为 , 而不是 ), 峰的上下两个方向对应正频和负频.
即 时, 设置不同稀疏度下的信号重构均方误差结果如下:
---MSE(y, y1) with k = 2: 0.937048086151075
---MSE(y, y2) with k = 4: 0.5420001800721357
---MSE(y, y3) with k = 6: 0.25283463530586237
---MSE(y, y4) with k = 100: 0.002307660406098402
求解的频域稀疏系数为
恢复的信号为
即 时, 设置不同稀疏度下的信号重构均方误差结果如下:
---MSE(y, y1) with k = 2: 0.9865788586325661
---MSE(y, y2) with k = 4: 0.5829159447924545
---MSE(y, y3) with k = 6: 0.3169739132218109
---MSE(y, y4) with k = 100: 0.0023321884115169826
求解的频域稀疏系数为
恢复的信号为
即 时, 设置不同稀疏度下的信号重构均方误差结果如下:
---MSE(y, y1) with k = 2: 1.031848207375802
---MSE(y, y2) with k = 4: 0.6615399428007099
---MSE(y, y3) with k = 6: 0.4982313612363407
---MSE(y, y4) with k = 100: 0.32437796224425747
求解的频域稀疏系数为
恢复的信号为