由唯一性到可計算的目標
寬矩陣可能在足夠稀疏的向量之中唯一確定訊號,但逐一搜尋所有可能的支撐集需要組合搜尋。基追蹤以絕對值之和代替非零項的數目。這個替換會否保留答案?關鍵不只是零空間有沒有稀疏向量,更在於每個無法被量測察覺的擾動如何分布其質量。
定義 16.5.1
(限制於指標集與基追蹤)
設 ,。對 ,令 在 上等於 ,其餘座標為零; 是補集。對無雜訊數據 ,基追蹤求解
最小解存在:可行集非空,與半徑 的閉 球之交是緊緻集。球外每個可行點的目標值都大於 ,所以交集上的最小解也是全局最小解。解不一定唯一。以下均處理實向量與精確運算;此約束問題不同於帶正懲罰參數的 lasso。
精確判準
兩個可行向量相差 中的一個元素,所以關於基追蹤的每個問題,其實都是零空間向量如何分布 質量的問題。
定義 16.5.2
( 階嚴格零空間性質)
若對每個非零 和每個 的集合,
則稱 具有 階嚴格零空間性質。若 ,它真空成立。
定理 16.5.3
(零空間刻畫)
以下兩項等價:
- 對每個至多有 個非零項的 , 是數據 的唯一基追蹤解。
- 具有 階嚴格零空間性質。
證明
(以反三角不等式證充分性;以拆分零空間向量證必要性)
假設嚴格性質成立。令 的支撐集包含於 ,,並設另一可行向量為 。則 。若 ,在 上使用反三角不等式得
所以每個不同的可行向量都有嚴格較大的目標值,唯一性成立。
反過來,若該性質不成立,便有非零 與 ,使 。取 、。因為 ,故 ,而 。又 ,所以 不是唯一最小解:另一可行向量的目標值或更小,或與它相等。必要性得證。
證明透視
嚴格性與階數 $s$ 在哪裏起作用
充分性只用到兩件事。第一,可行的競爭者與 相差一個零空間向量 。第二, 在 上為零,所以競爭者在 上要付出全部質量 ,而在 上反三角不等式說明它至多節省 。嚴格不等式把「至多節省」變成對每個 都嚴格淨虧損;若只有非嚴格不等式,只能得到 ,容許打平。
不明顯的一步在必要性。把壞的零空間向量 沿 切成 與 。前者至多有 個非零項,所以是第一項中合法的測試訊號;階數 只在這裏用到。後者給出相同的量測,因為兩者之差是 。等式 已經造成打平,這就是要求唯一性時第二項不能減弱為 的原因。
此性質排除了支撐集大小至多為 的非零零空間向量:把其支撐集分成兩個大小至多為 的集合,對兩者分別使用嚴格不等式便得到矛盾。因此每個 稀疏 都是 的唯一 稀疏解。反向不成立,下面的具體矩陣說明這一點。
反例模式
稀疏唯一性不蘊涵零空間性質
斷言:若沒有支撐集大小至多為 的非零零空間向量,則基追蹤恢復每個 稀疏向量。取 及
每個非零零空間向量的三個座標都不為零,所以斷言的假設成立。取 ,內外質量都是 ,嚴格性質不成立。具體地, 與 給出 ,兩者的 範數都是 。兩者都是最小解:任何可行 滿足 ,所以 。因此 不是唯一最小解。正確的條件是定理中的 質量不等式,而不是支撐集大小。
非稀疏訊號的尾項誤差界
精確稀疏是一種理想化。有用的保證應在訊號只是接近稀疏時平穩地退化。
定義 16.5.4
(最佳 項 誤差)
對任意 ,
取絕對值最大的 個座標可得到一個最小集合;絕對值相同時可任意選取。這個集合是分析工具,重建算法不需要事先知道它。
定理 16.5.5
(確定性的逐訊號誤差界)
假設存在 ,使每個 和每個 均滿足 。對任意 和精確數據 的任意基追蹤解 ,
證明
(比較最小解與真實訊號)
令 ,並選取最佳集合 。由可行性知 ,由最小化知 。分別在 和 使用反三角不等式,得
所以 。代入假設,得 。最後
這是對精確量測的確定性界,既沒有假設亦沒有證明量測雜訊下的誤差界;有雜訊時需要適當的穩健假設及修改可行集。
常見錯誤
(把精確數據的誤差界當作雜訊界)
若數據為 且 ,真實的 通常不滿足 。上面的證明兩次用到 的可行性:得出 ,以及比較 與 。兩步都不再成立,所以在放寬約束並把零空間假設加強為穩健版本之前,這個不等式對有雜訊的數據並無結論。
例題
例題 16.5.6
(一個不可見方向)
取
對任何非零零空間向量及單元素集合 ,內部質量是 ,外部是 。故 時嚴格性質成立,量化條件亦成立,最佳常數為 :每個一稀疏向量都能唯一恢復。例如 給出 ,它是唯一最小解。
同一數據亦有另一稀疏表示 ,其 範數為 而非 。因此基追蹤不能恢復這個二稀疏 ,因為可行向量 有較小目標值。一稀疏保證不能自動延伸至二稀疏情況。
概念視角分析
逐個訊號的對偶憑證
零空間性質對所有 稀疏訊號一致成立。凸對偶則為一個固定的、支撐集為 的 提供檢驗: 是唯一的基追蹤最小解,當且僅當 中以 為指標的各列線性無關,並且存在 使
對上面的矩陣及 ,取 得 ,證實可以恢復。對 而言,條件 迫使 或 ,與該處發現的打平情況一致。
例題 16.5.7
(接近一稀疏訊號的逐訊號誤差界)
保留同一個 、 與 ,常數為 。令 ,則 ,。每個可行向量是 ,目標值為
絕對偏差之和恰在點 的中位數處取最小,所以唯一最小點是 ,,而真實訊號的值為 。因此 ,,故
中間不等式亦可核對:取 ,。基追蹤沒有傳回 ,但誤差受尾項 控制。
例題 16.5.8
(邊界情況:階數等於環境維數)
令 。此時可取 ,,嚴格性質要求每個非零 都有 。這不可能,所以 階嚴格性質成立當且僅當 ,這迫使 。此時可行集 只有一點 ,恢復是平凡的。另外對每個 都有 ,所以誤差界給出 。因此寬矩陣()只可能對某些 的階數滿足該性質。
常見錯誤與練習詳解
常見錯誤
(最稀疏解不一定是唯一 ℓ1 最小解)
「支撐集最小的可行解必然是唯一 最小解。」定理要求檢查每個零空間方向。對上面的矩陣 , 是該方程組唯一的一稀疏解,因此也是唯一最稀疏解,卻與較稠密的解 同時達到最小 範數。判準中只有相等並不足夠。
快速檢查
(對第一個例題的矩陣 , 階嚴格零空間性質是否成立?)
用零空間向量 測試一個二元素集合。
解答 · 答案
不成立。對 及 ,,而 。拆分構造給出 與 ,正是同一數據的兩個表示 與 ,後者範數較小。
快速檢查
(對 ,計算 與 。)
保留絕對值最大的座標,把其餘座標的絕對值相加。
解答 · 答案
時保留 ,餘下 ,故 。 時保留 與 ,餘下 ,故 。
快速檢查
(若逐訊號誤差界的假設在 、 時成立,關於 可得甚麼結論?)
把假設應用於每個單元素集合。
解答 · 答案
當 ,每個 對每個單一指標 都滿足 。因此 ,。此時可行集是 ,所以 ,與誤差界 一致。