正交匹配跟蹤演算法OMP
本文翻譯自部落格
正交匹配跟蹤演算法（OMP）
1. 簡介
考慮以下情況，給定
和
，
我們可以計算
這是非常簡單地，也就是
。
現在讓我們介紹比較難的部分，給定
和
，
如何找到最接近的x？
在壓縮感知技術中，給定x和A，求解y的過程被稱為
壓縮，
然而另一方面，給定y
和A，求解x的過程稱為
重構
。重構問題是比較難的一個任務。
下面這段來自西瓜書，周志華老師專門為壓縮感知寫了一個小節來講這個問題。在現實應用中，傳輸的是數字訊號，以節省傳輸空間，根據奈奎斯特取樣定理，取樣頻率必須是模擬訊號最高頻率的兩倍，則取樣後的數字訊號保留了模擬訊號的全部資訊，由此獲得的數字訊號可以精確重構原模擬訊號。然而為了便於傳輸，常常對取樣後的訊號進行壓縮，那麼根據壓縮後的訊號可以重構原始的模擬訊號嗎？
假設y是壓縮後的訊號（長度為n），也被稱為壓縮訊號，原始的訊號是x （長度為m），m>>n，
其中
是對於訊號x的觀測矩陣，也稱為壓縮矩陣或者感知矩陣。由於n< 解釋下壓縮感知：壓縮感知關注的是如何利用 訊號本身所具有的稀疏性 ，從部分觀測樣本中恢復原始訊號，通常認為壓縮感知分為 感知測量 和 重構恢復 兩個階段， 感知測量 關注的是如何對原始訊號進行處理以獲得稀疏樣本表示， 重構恢復 關注的是如何基於稀疏性從少量的觀測中復原訊號，這是壓縮感知中的精髓，當我們談到壓縮感知時，通常指的是這部分。 2 基礎概念 我們認為壓縮矩陣A是有一系列 基訊號 或者 原子 組成的，也就是說 其中， 被稱為 原子 或者 基訊號 。 現在我們讓 那麼 上面的方程說明了y是A中原子的 線性組合 ，而線性組合係數恰好是x。 實際上，我們知道x1=-1。2， x2=1， x3=0。 換句話說原子a1對於y貢獻了-1。2，a2對於y貢獻了1，a3對於y貢獻了0。 正交匹配跟蹤演算法要找到對y貢獻最大的那個原子，然後是貢獻次之的原子，一直進行到貢獻最小的原子。這個迭代過程要進行m次，因為A 中有m個原子（m列），在上面的那個例子中，m=3。 3 計算貢獻 在矩陣A中有三個原子， ， 壓縮訊號y 我們計算每個原子對於y的貢獻 同理 根據上述結果，可以看出a1對於y的貢獻最大，值為-1。34（這裡只考慮大小，不用管負號，負號只是代表方向相反。我也想說下自己對於這塊的理解，這裡使用的是點積（內積），求的是y和A中每個原子的相關性）。當然也可以使用一步矩陣相乘直接計算出貢獻 可以得到相同的結果，圖1展示了A中的原子和y。 4 計算殘差 根據上一節中的計算結果，我們選擇貢獻最大的原子 ，相關的係數是 ，如果我們從y中減去， 那麼剩餘的殘差是 那麼所得的殘差由什麼意義呢？請看圖2。從y中減去了所有與原子a1有關的資訊，殘差與a1正交。 5 重複迭代 在第一次迭代時，我們選擇了原子a1， 將其作為一個基放入新的壓縮矩陣 中，也就是 並且將貢獻係數寫入到重構訊號 中， -1。34被放置到第一個元素的位置是因為這個貢獻係數來自於A中的第一個基a1。 殘差r 現在我們要從剩餘的原子a2或者a3中選擇出對殘差貢獻最大的， 由於a2的貢獻比較大（0。98>0。7，忽略負號），所以選擇a2。 現在我們將已經選擇了的基a1，a2都放到新的壓縮矩陣中 中，那麼 接下來這一步是與之前提出的另一種方法匹配跟蹤演算法（MP）不同的地方，我們計算 對於y的貢獻，得到係數（而不是MP中的做法，計算a2對殘差的貢獻，得到係數）。為了解決這個問題，需要解最小二乘問題，如下 寫成數學公式如下： 在這個例子中， 得到 。我們知道 的解是 ，其中 是 的偽逆，也就是說 ，在我們這個例子中 可以在MATLAB中使用pinv（）來計算偽逆。計算完偽逆之後，我們得到了 接著更新重構訊號 我們將得到的 分別放入 中第一和第二個位置，因為它們分別對應了我們選擇的第一和第二個原子。 在得到更新後的 和 後，我們更新殘差 現在我們得到的殘差是0，所以停止迭代。 6 最後一次迭代 因為殘差已經為0，所以這一步並不是必須的。許多OMP演算法需要設定一個關於訊號稀疏性的引數m，這告訴演算法它需要迭代m次，即使殘差為0，也需要迭代m次。 我們重構的訊號 為 與原始訊號是一致的。 8 注意事項 （a）在計算最大貢獻的時候，矩陣A中的原子應當是歸一化後的，而不是使用歸一化前的原子。 （b）如果矩陣A中的原子已經歸一化了，那麼在計算的時候就不需要歸一化了。 （c）在計算貢獻時，計算的是殘差與矩陣A中每個歸一化的原子的點積 （d）在匹配跟蹤演算法中（MP），重構訊號 是透過計算基訊號和殘差的點積得到的，對於正交匹配跟蹤演算法（OMP），重構訊號 是透過計算最小二乘解 得到的，這個過程需要花費一些時間，所以OMP演算法比MP演算法要慢一些。 （e）殘差是透過原始的 計算得到的。 （f）迭代次數最多是A的列數，或者是訊號x的稀疏m已知，那麼就迭代m次。 9 OMP缺陷 當A中存在中兩個原子有相關性時，OMP演算法可能會得到一個錯誤的重構訊號。 #FormatImgID_92##FormatImgID_93#
![a1=[\begin{matrix} -0.707\\ 0.707\\ \end{matrix}]](https://img.heatask.com/upload/website_attach/I4Uh2zg5zZMgvQGwH4JC04VifzHUGgpp6bNh0LyifgTTsVy6AV8I7zVPxdWiTg3-+vASsnuk4rBPuzT-3W5Yt_Dl2KPSybwhqkZksnGTDZ=ng6GMVQ8Q6_VPxZEB76pU+bt9snuk4rBPuzT-3W5YskZ-d.jpeg)
