動機
貪婪近似每次選一個有希望的字典元素,相關計算往往比搜尋全部子集便宜。但高相關可能來自錯誤原子模仿多個真實元素的組合。要證明選擇確實識別稀疏表示,必須限制錯誤原子模仿完整真實支撐的能力。
前面的追蹤筆記已推導殘差更新,並區分普通匹配追蹤與正交重擬合。本節補完整恢復證明。主要設定是有限、確定且無雜訊。兩兩原子相關界會導出小子集線性無關、稀疏係數唯一,以及每一步選擇正確;這是三個不同結論,各自需要論證。
充分相干門檻不是必要條件,不符合門檻也不表示每個訊號都失敗。另一方面,稀疏表示唯一不保證貪婪法在指定步數找到它。最後,樣本字典向量也未必穩定表示連續函數;樣本恢復與節點間近似仍是不同問題。
定義
定義 16.1.1
(歸一字典的相干度)
設有限實字典 ,每列向量滿足 。其相干度為 ;只有一列,即 時,定義 。支撐是不同列指標的集合,至多有 個非零係數稱為 稀疏。以 表示主要定理的真支撐;它恰有正整數 個元素,每個對應係數非零。
對已選指標集合 ,令 為 中相應各列組成的子矩陣,以最小二乘最小化 。若這些列線性無關,係數唯一,殘差為 ,其中 投影到已選列的生成空間;殘差與全部已選原子垂直。此處「獨立」是確定向量的線性無關,不是觀測的概率獨立。
定義 16.1.2
(正交匹配追蹤)
正交匹配追蹤(orthogonal matching pursuit,OMP)從 及 開始。只要殘差非零,便在未選指標中選一個使 最大者,加入 ,以最小二乘重新擬合全部已選係數,再重新計算殘差。用固定的相等處理規則,例如取最小指標,算法便完全確定。殘差為零或達到指定預算時停止。定理使用精確算術及至少為 的預算。
重擬合不可省略。普通追蹤只增加一個原子的倍數,未必重新與舊原子正交。本節歸納依賴每步正交投影。原子歸一也屬設定;若不歸一,相關大小還混入任意列長,不能使用同一選擇分析。
定理 / 命題
定理 16.1.3
(相干度控制獨立性及稀疏唯一性)
任意含 個原子的子集滿足
若 ,該子集線性無關。特別地,若 ,每個訊號最多有一個至多 稀疏的係數表示。
唯一性說明貪婪方法應當找到甚麼;第二個定理則說明 OMP 何時確實找到它。
定理 16.1.4
(完整無雜訊 OMP 恢復保證)
設 恰有 個非零係數,且
OMP 只選 中的指標,並在 次選擇後精確恢復全部係數;殘差不會更早變為零。真原子之間的相等不影響保證,因為證明給出最大真相關與每個假相關之間的嚴格間隙。
證明思路
證明
(Gram 界、獨立性與稀疏唯一性)
對第一個定理,把 展開為對角項與交叉項。對角項之和為 ;交叉項的絕對貢獻至多為 。恆等式 ,連同 ,把該和限制在 以內。這證明了兩個 Gram 不等式;下因子為正時,也證明了線性無關。
兩個至多 稀疏表示若生成同一向量,其差只涉及至多 列。嚴格相干條件使這些列獨立,故差為零,證明唯一。但這還沒有證明貪婪法能找到該表示。
證明
(對正確 OMP 選擇作歸納)
歸納假設已選的是真支撐的真子集。正交殘差仍在全部真原子生成空間,故可寫為 ,表示因獨立性而唯一。殘差不能零,否則原訊號可由真支撐的真子集表示,與全部真係數非零矛盾。
選殘差表示中絕對值最大的係數。對應真原子相關至少為 ,任何假原子相關最多為 。前者嚴格較大,恰好就是定理的條件。已選原子的相關因重擬合為零,所以大的真相關必定屬未選真原子,下一步選擇正確。
完成真稀疏數目的選擇後,集合就是全真支撐,最小二乘擬合等於訊號,唯一係數等於原係數。證明在精確無雜訊模型下不限制真係數大小,但不因此給任意有界雜訊相同支撐保證。
證明透視
每個假設在歸納中的位置
三件事用在三個不同地方。生成空間不變量,即先前每次選擇都正確,使殘差保持 的形式;只有這樣才能使用相干比較,而第二個例題說明一次選錯便破壞它。嚴格條件 只用一次,用來分開真原子的下界 與假原子的上界 ;正因間隙是嚴格的,真原子之間相等並無害處。正交重擬合使已選原子的相關為零,所以勝出的真相關屬於新原子。真原子列的線性無關使 唯一,並排除在第 步之前出現零殘差。這些都不能以「殘差範數下降」這一觀察代替。
若已知正確支撐,而數據改為 ,其中 ,重擬合給出的係數誤差至多為 。事實上,係數變化是對 的最小二乘響應,而第一個定理給出最小奇異值的下界。重建訊號的誤差至多為 ,因為它是 的正交投影。這些是已知支撐下的條件界,並沒有證明有雜訊的 OMP 會找到該支撐。
相干條件的嚴格性不是技術細節,邊界上的一個具體配置說明了這一點。
反例模式
在相干邊界上,相等可能選中假原子
斷言:在邊界 上保證仍然成立。取 及單位向量
則 ,,所以 ,。令 ,。三個相關為 、、。按最小指標規則,OMP 選中假原子 。殘差為 ,它與 、 的相關都是 ,故其次選第二個原子。兩個已選原子都在前兩個座標的平面內,而 的第三座標是 ,所以 次選擇後殘差 仍非零。第三步會選 ,重擬合後 的係數為零,但「恰好 次、只選真原子」的恢復已經失敗。修正後的陳述就是原定理,帶嚴格不等式 。
例題詳解
例題 16.1.5
(符合保證的非正交恢復軌跡)
取 、、 及 。相干度為 ,所以定理涵蓋二稀疏訊號。令 。初始相關為 、、 及 ,所以第一次選第四個原子。
第一次係數為 ,殘差為 ,新相關為 ,因此第二次選第一個。重新擬合後,第一及第四原子係數為一及二,殘差零。第四個原子的係數會改變;若凍結第一次數值,就不是這裏的 OMP。
例題 16.1.6
(表示唯一,OMP 仍可先選錯)
三維字典取前兩座標及 。三列線性無關,訊號 在整個字典中表示唯一,但與假第三原子的初始相關是 ,比兩個真相關都大,所以先選錯。
首殘差為 。用最小指標相等規則,再選第一個。正交重擬合係數為第一個二分之一、第三個 ,殘差為 ,兩步後仍非零。相干門檻不成立,單靠表示唯一無法修補錯誤首選。
例題 16.1.7
(有雜訊時須換一種識別結論)
對第一個例題的支撐,Gram 特徵值為 及 。若此支撐已知而雜訊範數至多為 ,係數誤差至多為 ,重建訊號誤差至多為 。這些估計把係數的條件與訊號精度分開。
即使正交字典也無法在任意有界雜訊下識別任意小的非零係數。真訊號 加雜訊 ,與無雜訊訊號 的觀測相同。正係數不超過雜訊容許量時,兩種解釋都合法。係數下界是排除此消去的必要資訊,但單獨不足,還須有雜訊選擇分析保證選對;另一做法是改用不要求精確支撐的成功準則。
稠密字典每次相關掃描需 。每步重建 QR,全部選擇的擬合成本為 ;逐步維持正交基則可降至 ,加上掃描共 ,額外因子儲存 。這是算術成本,不表示所有有限精度實作同樣穩定。
常見錯誤
常見錯誤
(把相干門檻當作必要條件)
相干界是充分而非必要,違反它的字典仍可恢復很多特定訊號。等號邊界沒有嚴格比較,因此本定理不保證,上面的邊界配置正是如此。數值上的近似相等不能當作證明中的嚴格間隙,有雜訊實作亦需停止容許值,不能盲目等待精確零。
常見錯誤
(對在全部節點為零的樣本函數歸一)
連續字典函數取樣時,先形成加權樣本向量,再對非零範數歸一。相干度描述的是這個取樣幾何;函數若在全部節點為零,根本不能變成歸一原子。連續線性無關不會防止不良節點丟失資訊。
常見錯誤
(把樣本正交性當作連續精度)
若有限函數空間有下範數比較 ,正數 才能把空間內樣本差控制成連續誤差:除以其平方根即可。相干度本身不提供這個比較;第四道練習的相干度為零,誤差仍然放大。目標不在空間時,還有連續近似殘差及其樣本混疊,必須另外處理。
總結
有限歸一字典有清楚相干分析。小子集條件先給稀疏唯一性,嚴格相關比較再證每步無雜訊 OMP 恢復,正交重擬合提供歸納不變量。雜訊、有限精度及由樣本移到連續函數,都需要精確恢復定理以外的資訊。
練習
快速檢查
(字典相干度為 ,列數足夠。嚴格定理覆蓋的最大整數稀疏數是多少?任意三列子字典的奇異值平方有何界?)
解答 · 答案
條件為 ,所以 ,涵蓋的最大整數為二。對三列,奇異值平方介乎 與 之間。稀疏度為三時恰為等號,所以嚴格定理不適用。
快速檢查
(用第一個例題的字典及最小指標相等規則,追蹤訊號 的兩步選擇、重擬合係數及殘差。)
解答 · 答案
初始相關一、一、零及 ,先選第一個,係數一、殘差第二原子。未選相關為一、零及 ,故再選第二個。兩個正交原子重擬合係數皆一,殘差零。
快速檢查
(說明雜訊可消去真係數時的識別障礙,為何相干零不能排除?給一種有雜訊精確支撐保證所需的額外資訊。)
解答 · 答案
加上雜訊 的觀測,與無雜訊的 的觀測相同。若 在雜訊容許量之內,單憑該觀測,任何程序都不能區分這兩種解釋。正交性使無雜訊的方向互不相同,卻不能揭示被消去的訊號。非零係數相對於雜訊的大小下界,是排除這種消去的必要條件,但單獨並不足夠;還須有適當的有雜訊選擇分析,合併的假設才能給出恢復保證。
快速檢查
(在正負 兩點取樣常數及輸入函數,每個節點的概率權重明確為 ,其中 。求歸一樣本相干。若兩反應分別被擾動負及正 ,求負一至一均勻概率測度下的連續平方積分範數誤差。)
解答 · 答案
每節點權重為 時,歸一樣本原子是 及 ,任何正 都相干零。反應擾動對應擬合函數 ,其連續範數是 ,樣本範數則為 。節點向原點合併時,即使樣本完全正交,連續誤差仍可放大。