動機
感測器很少給出精確的線性量測。若堅持精確擬合有雜訊的觀測,擬合出的係數可能解釋的是量測誤差,而不是背後的訊號。另一方面,若容許任意大的偏差,零向量便成為一個容易但毫無資訊的答案。我們需要一個容許量:大得足以包含真實訊號,又小得足以保留資訊。
精確恢復有兩個互相獨立的障礙。第一,觀測可能與 不同。第二,近似稀疏的訊號可能有許多小係數,而非恰好 個非零項。本節推導一個對每個障礙各有一項的誤差界。其假設不只控制零空間中不可見的改變,也控制量測矩陣幾乎看不見的改變。常數取決於該矩陣;結論是確定性的,不需要雜訊的概率模型。
定義
以下在實數上以精確運算處理。設 ,;對 ,令 在 上等於 ,其餘座標為零,補集記作 。
定義 16.6.1
(最佳 項尾誤差與有雜訊基追蹤)
對訊號 ,定義
設 ,,其中 是指定的上界。有雜訊基追蹤選取下列問題的任意一個全局最小解:
包含 個絕對值最大座標的集合達到最小值:若保留了一個較小座標而捨棄了一個較大座標,交換二者不會增加被捨棄的和;絕對值相同時可任選。這個最佳集合供分析使用,重建程序不需要預先知道它。若兩個座標絕對值相同而只能保留其一,兩種選擇都達到同一尾誤差;證明只需固定其中一個,而下面的假設對所有允許的集合成立,所以這種平手不影響結論。真實 未知時,這個集合及尾誤差也未知:定理描述重建品質與訊號可壓縮程度的關係,並不是單靠數據便可計算的誤差證書。
為何使用兩種不同的範數?在係數空間, 範數是各座標絕對值之和,既量度總誤差,也使最小化偏向較簡潔的表示。在數據空間, 範數把量測殘差視為一個向量的歐幾里得(Euclid)長度。兩者作用於不同空間,不能等同;穩健性質中的常數 正是連接兩種尺度的一部分。改變量測單位或重新縮放 ,可用的 亦會改變。
真實的 是可行的。因此可行集與半徑 的閉 球相交;在有限維中此交集是緊緻集,連續目標函數在其上達到最小值。球外的點不可能比可行點 更好,所以全局最小解存在。它不一定唯一;下面的結論對每個最小解都成立。
定義 16.6.2
(穩健零空間性質)
若存在常數 、,使每個 及每個 的集合都滿足
則稱 具有 階 穩健零空間性質。
這是關於所有向量及所有允許支撐集的假設,並非每個矩陣都具備。對 ,它化成定量的普通零空間不等式;對一般的 ,額外一項量度該改變有多「可見」。只知道定性的零空間陳述,並不能提供雜訊計算所需的上述常數;只檢查少數支撐集或少數試驗向量,亦不能確立這個對全部向量成立的不等式。
概念視角幾何
精確恢復即零空間避開一個錐
對精確數據,極小點就是最小的 球(一個正軸體)與仿射集 相接觸的點。因此 是唯一極小點,恰好當沒有非零 滿足 :零空間與 範數在 處的下降錐只交於原點。 的零空間不等式對每個非零的零空間向量給出 ,因此對每個支撐在 內的 都有 :關於 的一個條件,同時排除了所有 稀疏點的錐。
定理:分開尾項與雜訊
定理 16.6.3
(有界雜訊下的穩定恢復)
設上述穩健零空間性質成立。令 、,並令 為以該容許量求解的有雜訊基追蹤之任意全局最小解。則
第一項是以 稀疏向量近似 的代價,第二項是容許量測誤差的代價;兩者單位不同、來源亦不同。若 是 稀疏,第一項消失;若數據精確且 ,第二項消失。兩者同時消失時,誤差界變成精確恢復的陳述。
推論 16.6.4
(精確數據下稀疏訊號的精確及唯一恢復)
在 階穩健零空間性質下,若 至多有 個非零項、 且 ,則 是有雜訊基追蹤的唯一最小解。
證明
(誤差界的兩項同時為零)
此時 且 ,定理對每個最小解 給出 。由上面的緊緻性論證,最小解存在,所以最小解的集合恰為 。唯一性在這裏是結論,定理並沒有假設它。
因為 ,同一右邊也控制歐氏(Euclidean)誤差,但一般不是在更強假設下可得的較精細歐氏估計。帶較小或不同尺度 項的定理需要另外證明。
證明:一個錐與一個量測界
證明
(錐不等式、量測界與穩健性質)
令 ,並令 包含 中絕對值最大的 個座標。因 可行而 使目標最小,
分別在 與 上使用反三角不等式:在 上得 ;在補集上得 。與最優性合併並消去 ,得到錐不等式
係數二並非隨意的放寬:移項之前,尾項在兩邊各出現一次。此不等式說明,除非原訊號有可觀的尾項,最小解不能把遠多於大座標上的誤差放到大座標以外。
與 都可行,所以
兩個殘差可以方向相反,這解釋了係數二。它們不必相等:一般 。
依次使用穩健性質、錐不等式及量測界,
因為 ,相除得
錐不等式亦給出 。代入並化簡即得所示的界:
證明透視
每個假設在哪裏用到
證明有三個輸入,各用一次。 相對於可行競爭者 的最優性給出錐不等式;這是唯一用到目標函數的地方,也是尾項 出現的原因:反三角不等式的兩邊各貢獻一次。 與 兩者的可行性給出 ;這是唯一用到雜訊水平的地方。穩健性質是橋樑:它套用在實際誤差 上,而 一般不在 中,所以其 項正好吸收量測界。
收尾一步雖是代數,卻不可缺少。穩健不等式以 自身的 倍加上已知項來界定它,只有 才容許把該項移到左邊。若 ,不等式與任意大的 並不矛盾,下面的邊界反例正說明這一點。
常見錯誤
(把只控制零空間的不等式用於有雜訊數據)
當 ,兩個可行向量之差 通常滿足 。只控制 的零空間不等式對這個 毫無說明,所以不能代替穩健性質;沒有常數 、 的定性零空間陳述亦不能。
例題
例題 16.6.5
(已知矩陣、尾項與有雜訊數據)
取 、、、、。雜訊為 ,所以所述容許量有效。對每個 及單元素集合 ,;因此 、 是有效常數。
任何可行 都滿足 ,所以 。點 可行且達到這個下界;等號亦迫使 及 ,所以此最小解唯一。最佳一項尾誤差為 ,實際誤差為 。定理給出 。正確的上界對特定訊號與觀測不必是緊的。
例題 16.6.6
(真正欠定的矩陣)
令
其零空間是 ,所以有無窮多個向量給出相同量測。儘管如此,它以 、 具有穩健性質。為了對每個 驗證,令 。對 ,先用三角不等式,再用 Cauchy–Schwarz 不等式,得
對 ,把 與 互換。對 ,
空集的情況是平凡的,所以所述常數對所有大小至多為一的集合都成立。我們並沒有聲稱 是最佳的。對 及精確數據 ,定理說明即使 有非平凡零空間, 仍是唯一最小解。
例題 16.6.7
(邊界情況:數據精確,被捨棄的尾項仍改變答案)
保留上面的 ,取 ,,,。每個可行向量的形式為 ,目標值為 ,在三個轉折點 的中位數 處取最小。因此唯一最小解是 ,且
儘管觀測精確,結果並不精確,因為原向量不是一稀疏。定理中的尾項容許這種情況;它沒有聲稱此處達到係數六。
例題 16.6.8
(容許殘差會收縮解)
仍用同一 ,取 、無雜訊數據 ,但容許 。可行性推出 ,所以
向量 可行且達到此界。事實上它是唯一最小解:等號迫使第一個擬合座標為 且 ;殘差球再迫使第二個擬合座標為零,故 。其誤差為 ,而尾項為零,所以保證值是 。即使實際雜訊剛好為零,保守的容許量也可能帶來重建誤差。
假設不成立時
反例模式
零空間邊界上的等號並不足夠
對 、、、 及 , 與 都是全局最小解:任何可行 都有 。零空間向量 在 內外質量相等,而 。因此無論 為何,任何 都不滿足穩健性質。只容許 既不支持精確恢復,也不容許證明中的除法。
常見錯誤
(宣稱的雜訊上界小於實際雜訊)
令 、、,卻錯誤地宣稱 。唯一可行點是 。雖然單位矩陣滿足穩健性質,而 是一稀疏,所謂零誤差的結論卻是錯的:實際雜訊為 ,所以 不可行。定理沒有失效,失效的是其前提。估計或界定雜訊是另一項建模工作。
常見錯誤
(把容許量當作 LASSO 懲罰參數)
有雜訊基追蹤施加的是殘差約束;帶懲罰的 LASSO 則最小化殘差損失與 懲罰之和。在額外條件及適當選擇參數下,兩者的解可以聯繫起來,但 並不自動就是 LASSO 懲罰,上面的定理亦不是關於 LASSO 的定理。
同樣,數值求解器若只給出近似可行或近似最優的點,所用的界必須包含這些容許誤差;不應把精確最優性默默歸於有限步計算。驗證穩健性質本身可能很困難。一個有利的例子不能為任意字典作證明,沒有更多假設也推不出任何概率、隨機設計或限制等距性的保證。
練習
快速檢查
(對欠定例題中的矩陣,設 、。計算定理給出的 誤差數值上界。這能證明支撐集被精確恢復嗎?)
解答 · 答案
此處 、,所以尾項與雜訊的係數分別是 與 。上界為 ,約為 。單有誤差界不能證明支撐集精確恢復:任意小的非零係數仍可能被引入或抹去,需要額外的門檻及係數大小假設。
快速檢查
(對同一矩陣及精確觀測 ,已知真實向量是一稀疏,求 時有雜訊基追蹤的最小解。毋須列出所有可行向量,解釋它為何唯一。)
解答 · 答案
一稀疏向量 給出指定的量測。它的最佳一項尾誤差與容許量都是零,所以定理迫使每個最小解都等於這個向量。由上面的緊子水平集論證,最小解存在,所以即使可行集還包含其他非稀疏向量,它仍是唯一最小解。
快速檢查
(令 、、、。指出實際雜訊,求解約束問題,並準確說明為何不能套用恢復定理。)
解答 · 答案
實際雜訊為 ,其範數 。約束 使 成為唯一最小解。真實訊號不可行,所以與 的最優性比較及 量測界都不能使用。
練習 16.6.9
(設定理的假設成立,但計算所得的可行向量 只滿足 ,其中 已知。證明下面的界,並說明它對計算殘差有何要求。)
綜合證明
解答(4)
- 1
帶目標值超額重做錐不等式
令 ,並選取最佳集合 。同樣的反三角計算現在給出 。
- 2
保留量測界
。
依據: 與 均滿足 。
- 3
使用穩健性質並解出支撐集上的質量
關鍵一步
依據: 容許把 一項移到左邊。
- 4
合併並讀出殘差要求
∎由 ,代入後得到係數 、 及 。此保證要求 ;若計算殘差較大,便須修訂量測界。
相關筆記
精確數據的零空間性質討論無雜訊基追蹤的唯一性;LASSO 的近端梯度法討論另一種帶懲罰的目標及可計算的最優化證書。