逍遙劍客的專欄

主要介紹MP(Matching Pursuits)算法和OMP(Orthogonal Matching Pursuit)算法[1]，這兩個算法雖然在90年代初就提出來了，但作為經典的算法，國內文獻(可能有我沒有搜索到)都僅描述了算法步驟和簡單的應用，並未對其進行詳盡的分析，國外的文獻還是分析的很透徹，所以我結合自己的理解，來分析一下寫到博客裡，算作筆記。

1. 信號的稀疏表示(sparse representation of signals)

給定一個過完備字典矩陣。 字典矩陣中所謂過完備性，指的是原子的個數遠遠大於信號y的長度(其長度很顯然是n)，即n<<k。

2.MP算法(匹配追蹤算法)

2.1 算法描述

作為對信號進行稀疏分解的方法之一，將信號在完備字典庫上進行分解。

假定被表示的信號為y，其長度為n。假定H表示Hilbert空間，在這個空間H裡，由一組向量，也就是單位向量長度為1。MP算法的基本思想：從字典矩陣D（也稱為過完備原子庫中），選擇一個與信號 y 最匹配的原子(也就是某列)，構建一個稀疏逼近，並求出信號殘差，然後繼續選擇與信號殘差最匹配的原子，反復迭代，信號y可以由這些原子來線性和，再加上最後的殘差值來表示。很顯然，如果殘差值在可以忽略的范圍內，則信號y就是這些原子的線性組合。如果選擇與信號y最匹配的原子？如何構建稀疏逼近並求殘差？如何進行迭代？我們來詳細介紹使用MP進行信號分解的步驟：[1] 計算信號 y 與字典矩陣中每列(原子)的內積，選擇絕對值最大的一個原子，它就是與信號 y 在本次迭代運算中最匹配的。用專業術語來描述：令信號，r0 表示一個字典矩陣的列索引。這樣，信號 y 就被分解為在最匹配原子。[2]對殘值R1f進行步驟[1]同樣的分解，那麼第K步可以得到：