算法
3.1 算法描述
OMP算法的改進之處在於：在分解的每一步對所選擇的全部原子進行正交化處理，這使得在精度要求相同的情況下，OMP算法的收斂速度更快。
那么在每一步中如何對所選擇的全部原子進行正交化處理呢？在正式描述OMP算法前，先看一點基礎思想。
先看一個 k 階模型，表示信號 f 經過 k 步分解後的情況，似乎很眼熟，但要注意它與MP算法不同之處，它的殘值與前面每個分量正交，這就是為什麼這個算法多了一個正交的原因，MP中僅與最近選出的的那一項正交。
(1)
k + 1 階模型如下：
(2)
套用 k + 1階模型減去k 階模型，得到如下：
(3)
我們知道，字典矩陣D的原子是非正交的，引入一個輔助模型，它是表示對前k個項的依賴，描述如下：
(4)
和前面描述類似，在span(x1, ...xk)之一上的正交投影操作，後面的項是殘值。這個關係用數學符號描述：
請注意，這裡的 a 和 b 的上標表示第 k 步時的取值。
將(4)帶入(3)中，有：
（5）
如果一下兩個式子成立，(5)必然成立。
(6)
(7)
令，有
其中。
ak的值是由求法很簡單，通過對(7)左右兩邊添加作內積消減得到：
後邊的第二項因為它們正交，所以為0，所以可以得出ak的第一部分。對於，在（4）左右兩邊中與作內積，可以得到ak的第二部分。
對於(4)，可以求出，求的步驟請參見參考檔案的計算細節部分。為什麼這裡不提，因為後面會介紹更簡單的方法來計算。
3.2
收斂性證明
通過(7)，由於與正交，將兩個殘值移到右邊後求二范的平方，並將ak的值代入可以得到：
可見每一次殘差比上一次殘差小，可見是收斂的。
3.3 算法步驟
整個OMP算法的步驟如下：
由於有了上面的來龍去脈，這個算法就相當好理解了。
到這裡還不算完，後來OMP的疊代運算用另外一種方法可以計算得知，有位同學的論文[2]描述就非常好，我就直接引用進來：
對比中英文描述，本質都是一樣，只是有細微的差別。這裡順便貼出網一哥們寫的OMP算法的代碼，源出處不得而知，共享給大家。
再貼另外一個洋牛paper[3]中關於OMP的描述，之所以引入，是因為它描述的非常嚴謹，但是也有點苦澀難懂，不過有了上面的基礎，就容易多了。
它的描述中的Sweep步驟就是尋找與當前殘差最大的內積時列在字典矩陣D中的索引，它的這個步驟描述說明為什麼要選擇內積最大的以及如何選擇。見下圖，說的非常清晰。
它的算法步驟Update Provisional Solution中求很簡單，就是在 b = Ax 已知 A和b求x， 在x的最小二范就是A的偽逆與b相乘，即：
