正交匹配追踪法(OMP)

正交匹配追踪法(OMP)

模型

OrthogonalMatchingPursuit (正交匹配追踪法)使用了 OMP 算法近似拟合了一个带 l0 l 0 范数限制的线性模型。

当提供参数n_nonzero_coefs时，优化目标为：

当提供参数 tol时，优化目标为：

算法

匹配追踪(MP)

假设初始的残差设置为 R0=y R 0 = y ， X=[x1,…,xp],||xi||2=1,∀i X = [ x 1 , … , x p ] , | | x i | | 2 = 1 , ∀ i

MP 首先选择满足下式的属性 xl0 x l 0 ：

此时 y y 可以分解为：

其中， ⟨R0,xl0⟩xl0 ⟨ R 0 , x l 0 ⟩ x l 0 表示 y y 在 xl0xl0 的投影， R1 R 1 表示用 xl0 x l 0 逼近 y y 的残差。

(1)式两边与 xl0xl0 做内积可知， xl0 x l 0 正交于 R1 R 1 ，因此：

为了最小化残差，MP算法迭代的寻找最优属性。一般的，对于第 t t 次迭代，设最优的属性为 xltxlt，逼近残差满足：

其中， xlt x l t 满足：

(2)式两边与 xlt x l t 做内积可知， xlt x l t 正交于 Rt+1 R t + 1 ，因此：

MP算法是收敛的，因为得出每一个残值比上一次的小，即 ||Rt||22>||Rt+1||22 | | R t | | 2 2 > | | R t + 1 | | 2 2

若提供参数n_nonzero_coefs时，迭代n_nonzero_coefs次停止，此时有：

若提供参数 tol时，当 ||Rn||22≤tol | | R n | | 2 2 ≤ tol 时，停止迭代，此时有：

缺点：如果残值在已选择的特征进行垂直投影是非正交性的，这会使得每次迭代的结果并不少最优的而是次最优的，收敛需要很多次迭代。举个例子说明一下：在二维空间上，有一个目标 y y 被 X=[x1,x2]X=[x1,x2] 来表达，MP算法迭代会发现总是在 x1 x 1 和 x2 x 2 上反复迭代，即 y=a1x1+a2x2+a3x1+⋯ y = a 1 x 1 + a 2 x 2 + a 3 x 1 + ⋯ ，这个就是残值在已选择的特征进行垂直投影的非正交性导致的。

正交匹配追踪法(OMP)

OMP算法的改进之处在于：在分解的每一步对所选择的全部原子进行正交化处理，这使得在精度要求相同的情况下，OMP算法的收敛速度更快。

算法：给定目标 y y ，设计矩阵 X=[x1,…,xp],||xi||2=1,∀iX=[x1,…,xp],||xi||2=1,∀i，停止条件n_nonzero_coefs或tol

1. 初始化： t=1,R0=y t = 1 , R 0 = y ，特征矩阵 D0=[ ] D 0 = [   ] ，指标集 L={ } L = {   }

2. 用以下公式寻找最优属性 xlt x l t
   

   |⟨Rt−1,xlt⟩|=supi|⟨Rt−1,xi⟩| | ⟨ R t − 1 , x l t ⟩ | = sup i | ⟨ R t − 1 , x i ⟩ |

3. 更新特征矩阵 Dt=[Dt−1,xlt] D t = [ D t − 1 , x l t ] 和指标集 L=L∪{lt} L = L ∪ { l t }

4. 计算稀疏系数
   

   w=argminw||y−Dtw||22 w = a r g m i n w ⁡ | | y − D t w | | 2 2
   
   此时 Dtw D t w 是 y y 在 span{xl1,…,xlt}span{xl1,…,xlt} 上的正交投影

5. 更新残差
   

   Rt=y−Dtw R t = y − D t w
   
   此时有 Rt⊥span{xl1,…,xlt} R t ⊥ span { x l 1 , … , x l t }

6. 检查是否满足停止条件，不满足则 t=t+1 t = t + 1

最后

以上就是哭泣店员最近收集整理的关于正交匹配追踪法(OMP)的全部内容，更多相关正交匹配追踪法(OMP)内容请搜索靠谱客的其他文章。