摘要

當(dāng)解被限定為稀疏的時候，也就是期望有更少的非零元素時，貪婪準(zhǔn)則通常被用來解決不確定的可逆問題。OMP（正交匹配追蹤法）和OLS通常被用來解決這兩個問題。目前現(xiàn)有的文獻(xiàn)中，有大量的文獻(xiàn)都將這兩者混淆了。

1. 引言

本節(jié)，我們引入兩個貪婪的方法來解決上述兩個問題。給定一個向量x∈RNxx∈RNx，矩陣Φ∈RNx×NsΦ∈RNx×Ns，可以找到一個向量，使得均方誤差最小，并且s僅僅有最少的非零元素。

貪婪算法：

正交匹配追蹤法是信號處理中擬合稀疏模型的一種貪婪分布最小二乘法(greedy stepwise least squares)法。

貪婪算法(greedy algorithm)的基本思想是：

不求整體最優(yōu)解，而是試圖盡快找到某種意義上的局部最優(yōu)解。貪婪法雖然不能對所有問題得到整體最優(yōu)解，但對范圍相當(dāng)廣泛的許多問題能產(chǎn)生整體最優(yōu)解或者整體最優(yōu)解的近似解。和使用凸優(yōu)化算法的l1范數(shù)相比，貪婪算法在速度上具有很大優(yōu)勢。典型的貪婪算法有匹配追蹤法和正交匹配追蹤法：

匹配追蹤法：

匹配追蹤法(matching pursuit， MP) 是由法蘭西大牛Mallat于1993年提出。其基本思想是，不針對某個代價函數(shù)進(jìn)行最小化，而是考慮迭代地構(gòu)造一個稀疏解x: 只使用字典矩陣A的少數(shù)列向量的線性組合對觀測向量x實現(xiàn)稀疏逼近Ax=y，其中字典矩陣A被選擇的列向量所組成的集合是以逐列的方式建立的。在每一步迭代，字典矩陣中通當(dāng)前殘差向量r=Ax?y中最相似的列向量被選擇作為作用集的新一列。如果殘差隨著迭代的進(jìn)行遞減，則可以保證算法的收斂。

正交匹配追蹤：

匹配追蹤只能保證殘差向量與每一步迭代所選的字典矩陣列向量正交，但與以前選擇的列向量一般不正交。正交匹配追蹤(orthogonal matching pursuit, OMP)則能保證每步迭代后殘差向量與以前選擇的所有列向量正交，以保證迭代的最優(yōu)性，從而減少了迭代次數(shù)，性能也更穩(wěn)健。

正交匹配追蹤算法：

輸入 觀測數(shù)據(jù)向量y∈Rm和字典矩陣A∈Rm×n. 輸出 稀疏系數(shù)向量 x∈Rn. Step 1 初始化 令標(biāo)簽集Ω0=?,初始?xì)埐钕蛄縭0=y，令k=1. Step 2 辨識 求矩陣A中與殘差向量rk?1最強(qiáng)相關(guān)的列 jk∈argmaxj|<rk?1,?j>|,Ωk=Ωk?1∪jk Step 3 估計 最小化問題 minx∥y?AΩkx∥的解由 xk=(AHΩkAΩk)?1AHΩky給出，其中 AΩk=[aω1,...,aωk],ω1,...,ωk∈Ωk Step 4 更新殘差 rk=y?AΩkxk Step 5 令k=k+1，并重復(fù)Step 2 至Step 4。若某個停止判據(jù)滿足，則停止迭代。 Step 6 輸出系數(shù)向量 x(i)=xk(i), if i∈Ωk x(i)=0, otherwise

注: AH為共軛轉(zhuǎn)置

下面是三種常用的停止判據(jù)

運行到某個固定的迭代步數(shù)后停止。

殘差能量小于某個預(yù)先給定值ε。 ∥rk∥2≤ε

當(dāng)字典矩陣A的任何一列都沒有殘差向量rk的明顯能量時
∥AHrk∥∞≤ε

總結(jié)

以上是生活随笔為你收集整理的On the Difference Between Orthogonal Matching Pursuit and Orthogonal Least Squares的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。