動機
稀疏模型用字典中少量列向量表示訊號。上一節證明了正交匹配追蹤(OMP)在無雜訊下的恢復保證。實際量度很少完全準確,因此現在必須分清兩個問題:假如有人告訴我們哪些列向量真正起作用,雜訊會使擬合係數偏離多少?假如支撐集未知,觀察所得的相關值何時足以辨認它?
第一個問題用已知支撐集上的普通最小二乘回答;第二個問題使用單步閾值選取。以下結果都是確定性的:雜訊可以是對抗性的,我們不假設任何概率分布。這不是含雜訊 OMP 正確選取支撐集的定理。一種方法的充分條件,不能未經證明就轉用於另一種方法。
定義
令 的列向量均為單位向量,並如上一節以 為其相干度;當 時定義 。對大小為 的索引集 , 由相應列向量組成, 稱為 Gram 矩陣。除非另有下標,以下向量範數均為歐氏(Euclidean)範數。
定義 16.2.1
(含雜訊稀疏模型及其參數)
觀測值為 ,其中 恰為非零係數的索引集、,且 。其參數為
由於每個原子均為單位向量,Cauchy–Schwarz 不等式給出 。這些參數是未知訊號的性質或界,並非假設算法都知道。辨認支撐集時假設 ,且數目 已知。
定義 16.2.2
(單步相關閾值選取)
給定 及稀疏度 ,單步相關閾值選取選出 最大的 個索引 ;同值時可任意決定。此方法在選取前不更新殘差,也不重擬合。
定理與命題
定理 16.2.3
(Gram 界與已知支撐集擬合)
對每個大小為 的非空 , 的每個特徵值 均滿足
若 ,則 的列向量線性無關,且在給定支撐集上的最小二乘估計唯一,滿足
更精確地說,重建訊號的誤差是 ,其中 是投影到 的正交投影;觀測殘差則是 。
概念視角代數
以圓盤陳述讀出 Gram 界
特徵值區間亦可直接從 的元素讀出。此矩陣是實對稱矩陣,每個對角元素為 ,每個非對角元素的絕對值不超過 。Gershgorin 圓盤定理把每個特徵值放在某個以對角元素為圓心的圓盤內,半徑是該行非對角元素絕對值之和:
對稱性使 為實數,於是圓盤收縮為定理中的區間。中間的量從不比相干度界差;若選中原子中只有少數幾對接近平行,它會更小。
第二個結果處理未知的支撐集。它只比較相關值,Gram 界要到最後才回來控制重擬合。
定理 16.2.4
(單步閾值選取的充分分離條件)
在同一模型下,若
則每個真實原子與 的絕對相關值均嚴格大於每個錯誤原子的絕對相關值。因此選出絕對相關值最大的 個索引便恢復 ;真實索引之間如何處理同值都不影響結論。此裕量本身推出 ;因此在選出的支撐集上重擬合便得到上述兩個誤差界。
證明
證明
(二次型界與投影恆等式)
對 ,展開二次型並利用相干度定義可得
最後一步使用 Cauchy–Schwarz 不等式 。將所得二次型上下界套用於特徵向量,即得特徵值界。若下界為正, 迫使滿足 的 為零。故 列滿秩,正規方程有上述唯一解。
令 。最小二乘正規方程說明 ,所以 ;正交投影給出 。結合 ,便得到係數誤差界。另一方面,以 減去擬合值所得的是另一個向量 。
閾值選取的證明直到最後一行才用到特徵值;它是兩族內積的比較。
證明
(比較最弱的真實相關值與最強的錯誤相關值)
對真實索引 ,反三角不等式及 給出
對錯誤索引 ,三角不等式給出
由於 且 ,假設中的裕量推出 ,故 。假設中的嚴格不等式亦令第一個界嚴格大於第二個界,因此前 個位置不可能包含錯誤索引,必然剛好選中全部 個真實索引。這是同時對所有索引成立的比較,容許負係數及對抗性雜訊;證明不要求真實相關值保持無雜訊時的符號。
證明透視
每個假設在比較中的作用
單位範數用了兩次。在 中,自身係數的因子是 ,而每個交叉項都以 為界。單位範數亦給出 。
關鍵一步是不逐一追蹤符號。一個下界對所有真實索引成立,一個上界對所有錯誤索引成立,所以單一個數便把兩組分開。無論真實相關值之間如何排序,前 個索引的集合都已確定。
常數 計算干擾的數目:真實原子遇上其餘 個真實原子,錯誤原子則遇上全部 個。雜訊在兩邊各出現一次,因而得到 。
論證分兩步收結。嚴格不等式排除兩組之間的同值,已知 則使算法剛好在選完真實原子時停止。若 未知,單靠分離並不給出算法:要在兩個界之間定下截斷值,便需要未知的訊號參數。最後, 把裕量轉化為 ,所以第一個定理無需額外假設便適用於重擬合。
此裕量是充分條件,並非必要條件。它使用最大係數 ,彷彿所有干擾相關值同時達到最壞符號與大小,因此即使閾值選取成功,條件也可能不成立。若沒有 的界,以 代替可得到較弱但仍正確的條件。這個代換依賴列向量已歸一化,以下的驗算說明這一點。
反例模式
列向量未歸一化時雜訊界失效
斷言:對正交但未歸一化的列向量,以原始內積計算 ,條件 仍保證閾值選取正確。取 中的 、、 及 。不同列向量的原始內積均為零,故 ,且 。
觀測值為 ,它與三個列向量的原始相關值是 、 及 。取 時,閾值選取必然選中索引 以及索引 之一,因此失敗。
出錯的一步是 :此處 超過 ,因為 。修正方法是把字典歸一化,以 代替 。相關值變為 、 及 ,嚴格裕量 保證恢復 。
例題
例題 16.2.5
(先選取,再重擬合)
令 、、,取 、 和 。則 、、 及 。條件成立,因為
相關值分別為 、 及 。前兩者最大,因此閾值選取恢復 。在選出的正交單位列向量上重擬合得到 ;係數誤差與訊號誤差的範數都是 。一般相干度界為 ;它有效但偏保守,因為實際選中列向量的 Gram 矩陣是單位矩陣。殘差為零:位於選中空間的雜訊被擬合係數吸收。
例題 16.2.6
(唯一不代表條件良好)
取 、,其中 。兩列線性無關,故其生成空間內每個向量的表示均唯一。其 Gram 特徵值是 。特別地,係數向量 的範數為一,但 。當 ,距離為一的兩個係數向量可以產生任意接近的訊號。每個固定正角度都有唯一解,但角度縮小時反問題的穩定常數無界增大。
例題 16.2.7
(唯一表示未必能由閾值選取恢復)
令 、、,並令 。三列線性無關,因此即使容許使用整個字典,表示仍唯一。但它們與 的絕對相關值為 、、。取 時,單步閾值選取的是索引 ,而非真實支撐集 。此例不滿足充分裕量;唯一性並不保證其結論。
常見錯誤
常見錯誤
(穩定的擬合不能證明支撐集正確)
正的 Gram 下界保證給定支撐集上的擬合穩定,並不告訴我們給定的支撐集是否正確。選取支撐集需要係數相對雜訊的裕量,而任何條件性界都不提供這一點。同樣地,最小二乘殘差為零不代表觀測沒有雜訊,「先選取,再重擬合」一例就顯示了這點。 是線性無關的充分條件,並非必要條件;它不成立並不證明矩陣奇異。
常見錯誤
(把係數誤差當作雜訊的一部分)
雜訊有正交分解 ,故 。係數誤差 屬於 ,不在訊號空間內;只有經 映射後,它才成為上述分量之一。其範數可以大於 ,但倍數至多為 。
常見錯誤
(接受裕量取等號)
兩個估計相等時不能排除真實與錯誤索引同值。在標準正交字典中取 、 及 。則 、 且 ,恰好 。觀測 的相關值是 與 ,同值處理規則可能選出錯誤索引 。
如果雜訊抵消一個非零係數,即使字典標準正交,也不能單憑觀測辨認該支撐集。最後,這裏對有限取樣向量的分析,本身既不控制取樣點之間的誤差,也不證明含雜訊 OMP 的逐步選擇正確。
總結
相干度控制選定 Gram 矩陣的所有特徵值;當下界為正,它也控制已知支撐集擬合中的雜訊放大。另一方面,逐一比較真實及錯誤相關值,可在明確的嚴格裕量下證明單步閾值選取恢復支撐集。兩種估計均為充分界,並非所有成功字典或訊號的完整刻畫。
習題
快速檢查
(歸一化字典的 。估計任意四列子字典的奇異值平方與 2-範數條件數。若真實支撐集有四列且 ,求已知支撐集係數誤差的上界。)
解答 · 答案
Gram 特徵值等於奇異值平方,位於 。因此任意這樣的子字典均為單射,其 2-範數條件數不超過 。係數誤差不超過 ,約為 。
快速檢查
(在三列標準正交字典中,取 、 及 。觀測到甚麼?任何確定性規則能否單靠觀測向量,區分此解釋與另一個具有相同雜訊限額的二稀疏解釋?)
解答 · 答案
觀測向量為 ;支撐集 、係數 及雜訊 也產生同一觀測。兩個解釋的稀疏度均為二,雜訊範數均為 。確定性規則在兩個模型中看到完全相同的數據,只能作出相同輸出,故即使已知 ,也不能對兩者均正確。此處 、 且 ,所以所需的嚴格裕量不成立。此抵消現象說明為甚麼一致保證需要雜訊與訊號的分離。
快速檢查
(在「先選取,再重擬合」一例的字典中,取 、 及 。計算所有相關值、已知 時選出的支撐集、重擬合係數及殘差。使用精確 時,充分閾值條件是否成立?)
解答 · 答案
相關值是 、 及 。最後一個小於一,故閾值選取 。重擬合係數為 ,殘差為 。此處 ,充分條件成為 ,確實成立。
快速檢查
(令 。證明可能較精確的條件 也保證單步閾值選取正確。解釋它為何至少與定理中的條件一樣寬鬆。)
解答
對真實索引,。每個錯誤相關值最多是 。題設使前一個界嚴格大於後一個界,故恢復成功。由於一個係數的大小為 ,其餘 個至多為 ,所以 。因此
原條件使右邊為正,因此推出新條件;新條件亦可能在原條件不成立的情況下成立。