動機
欠定矩陣有非零零空間向量,因此不可能從量測值唯一恢復任意係數。稀疏恢復問的是較窄的問題:兩個只有少量非零項的向量,能否產生相同量測值?即使答案是否定的,即稀疏向量由量測唯一確定,數值重建仍須處理雜訊。本節區分三種結論:稀疏向量之間的唯一性、已知正確支撐集時的穩定性,以及移除已選列後的相關性界。這些結論本身都不保證算法能找到支撐集。
定義
設 A ∈ R m × N A\in\mathbb R^{m\times N} A ∈ R m × N ,列向量為 a j a_j a j 。對 S ⊆ { 1 , … , N } S\subseteq\{1,\ldots,N\} S ⊆ { 1 , … , N } ,A S A_S A S 表示相應的列子矩陣,而 ∥ x ∥ 0 \|x\|_0 ∥ x ∥ 0 計算非零項個數。對 1 ≤ k ≤ N 1\leq k\leq N 1 ≤ k ≤ N ,假設存在 0 ≤ δ < 1 0\leq\delta<1 0 ≤ δ < 1 ,使每個支撐集大小不超過 k k k 的向量都滿足
( 1 − δ ) ∥ x ∥ 2 2 ≤ ∥ A x ∥ 2 2 ≤ ( 1 + δ ) ∥ x ∥ 2 2 . (1-\delta)\|x\|_2^2\leq\|Ax\|_2^2\leq(1+\delta)\|x\|_2^2. ( 1 − δ ) ∥ x ∥ 2 2 ≤ ∥ A x ∥ 2 2 ≤ ( 1 + δ ) ∥ x ∥ 2 2 . 這稱為矩陣具有階數 k k k 、常數至多為 δ \delta δ 的限制等距性(RIP)。一般而言,δ k \delta_k δ k 表示令兩側不等式對所有上述向量成立的最小 δ ≥ 0 \delta\geq0 δ ≥ 0 ;此常數可以大於或等於一,而階數 k k k 的 RIP 恰在 δ k < 1 \delta_k<1 δ k < 1 時成立。
假設同時包含上界和下界;每列長度為一並不足以保證 RIP。當 k = N k=N k = N 時,δ < 1 \delta<1 δ < 1 要求滿列秩;列數多於行數的矩陣仍可能在較小階數滿足 RIP。以下均使用實數和精確運算。
概念視角 代數
受限等距作為 Gram 子矩陣的特徵值條件 若 x x x 的支撐在 S S S 內,則 ∥ A x ∥ 2 2 = x S ⊤ G S x S \|Ax\|_2^2=x_S^\top G_Sx_S ∥ A x ∥ 2 2 = x S ⊤ G S x S ,其中 G S = A S ⊤ A S G_S=A_S^\top A_S G S = A S ⊤ A S 。因此常數為 δ \delta δ 的 k k k 階 RIP 恰好是說:每個 ∣ S ∣ ≤ k |S|\leq k ∣ S ∣ ≤ k 的 G S G_S G S 的每個特徵值都在 [ 1 − δ , 1 + δ ] [1-\delta,1+\delta] [ 1 − δ , 1 + δ ] 內,即
δ k = max ∣ S ∣ ≤ k ∥ A S ⊤ A S − I ∥ 2 . \delta_k=\max_{|S|\leq k}\|A_S^\top A_S-I\|_2. δ k = ∣ S ∣ ≤ k max ∥ A S ⊤ A S − I ∥ 2 . 等價地,每個這樣的 A S A_S A S 的奇異值都在 [ 1 − δ , 1 + δ ] [\sqrt{1-\delta},\sqrt{1+\delta}] [ 1 − δ , 1 + δ ] 內。只需檢查 ∣ S ∣ = k |S|=k ∣ S ∣ = k 的集合:較小的 Gram 矩陣是較大者的主子矩陣,特徵值交錯定理使它的特徵值留在較大者的範圍內。例題正是這樣計算 δ 2 \delta_2 δ 2 的。
定理/命題
設 s ≥ 1 s\geq1 s ≥ 1 為整數、2 s ≤ N 2s\leq N 2 s ≤ N ,且階數 2 s 2s 2 s 的 RIP 以 δ < 1 \delta<1 δ < 1 成立。若 x , z x,z x , z 均至多有 s s s 個非零項,並且 A x = A z Ax=Az A x = A z ,則 x = z x=z x = z 。更一般地,若 ∥ A x − y ∥ 2 ≤ ε \|Ax-y\|_2\leq\varepsilon ∥ A x − y ∥ 2 ≤ ε 及 ∥ A z − y ∥ 2 ≤ ε \|Az-y\|_2\leq\varepsilon ∥ A z − y ∥ 2 ≤ ε ,則
∥ x − z ∥ 2 ≤ 2 ε 1 − δ . \|x-z\|_2\leq\frac{2\varepsilon}{\sqrt{1-\delta}}. ∥ x − z ∥ 2 ≤ 1 − δ 2 ε . 這比較任意兩個稀疏可行向量,並沒有說明如何找到它們。
若支撐集不必尋找,而是直接給定,便有更精確、更簡單的結論。
假設 ∣ S ∣ ≤ k |S|\leq k ∣ S ∣ ≤ k 、階數 k k k 的 RIP 以 δ < 1 \delta<1 δ < 1 成立,且 y = A S β + e y=A_S\beta+e y = A S β + e 、∥ e ∥ 2 ≤ ε \|e\|_2\leq\varepsilon ∥ e ∥ 2 ≤ ε 。在「已給定」集合 S S S 上的唯一最小二乘解滿足
β ^ = β + ( A S ⊤ A S ) − 1 A S ⊤ e , ∥ β ^ − β ∥ 2 ≤ ε 1 − δ , ∥ A S ( β ^ − β ) ∥ 2 ≤ ε . \widehat\beta=\beta+(A_S^\top A_S)^{-1}A_S^\top e,\qquad
\|\widehat\beta-\beta\|_2\leq\frac{\varepsilon}{\sqrt{1-\delta}},\qquad
\|A_S(\widehat\beta-\beta)\|_2\leq\varepsilon. β = β + ( A S ⊤ A S ) − 1 A S ⊤ e , ∥ β − β ∥ 2 ≤ 1 − δ ε , ∥ A S ( β − β ) ∥ 2 ≤ ε . 殘差是 ( I − P S ) e (I-P_S)e ( I − P S ) e ,其中 P S P_S P S 是到 span ( A S ) \operatorname{span}(A_S) span ( A S ) 的正交投影。已知 S S S 是預知正確集合的假設,並非擬合本身的結論。
證明概要或思路
差向量 h = x − z h=x-z h = x − z 最多只有 2 s 2s 2 s 個非零項。RIP 下界給出 1 − δ ∥ h ∥ 2 ≤ ∥ A h ∥ 2 \sqrt{1-\delta}\|h\|_2\leq\|Ah\|_2 1 − δ ∥ h ∥ 2 ≤ ∥ A h ∥ 2 ;若 A x = A z Ax=Az A x = A z ,右邊為零。有雜訊時,三角不等式給 ∥ A h ∥ 2 ≤ ∥ A x − y ∥ 2 + ∥ A z − y ∥ 2 ≤ 2 ε \|Ah\|_2\leq\|Ax-y\|_2+\|Az-y\|_2\leq2\varepsilon ∥ A h ∥ 2 ≤ ∥ A x − y ∥ 2 + ∥ A z − y ∥ 2 ≤ 2 ε 。兩項結論隨即成立。這也解釋為何需要階數 2 s 2s 2 s 而非只用 s s s :兩個支撐集可以互不相交。
RIP 下界確保 A S A_S A S 單射,故正規方程有上述唯一解。擬合誤差 A S ( β ^ − β ) = P S e A_S(\widehat\beta-\beta)=P_Se A S ( β − β ) = P S e 是雜訊的投影,其範數至多為 ε \varepsilon ε 。再把 RIP 下界套用到係數誤差,便得係數估計 ε / 1 − δ \varepsilon/\sqrt{1-\delta} ε / 1 − δ ,是一般兩個可行向量距離上界的一半。剩餘雜訊 ( I − P S ) e (I-P_S)e ( I − P S ) e 與擬合誤差正交,兩者範數平方之和等於 ∥ e ∥ 2 2 \|e\|_2^2 ∥ e ∥ 2 2 。雜訊落在擬合空間內時,殘差雖小,係數誤差仍可能不小。
投影掉已選列
令 T , U , V T,U,V T , U , V 兩兩不相交,且 ∣ T ∣ + ∣ U ∣ + ∣ V ∣ ≤ k |T|+|U|+|V|\leq k ∣ T ∣ + ∣ U ∣ + ∣ V ∣ ≤ k 。寫 Q = I − P T Q=I-P_T Q = I − P T 和 B U = Q A U B_U=QA_U B U = Q A U 。RIP 保證 A T A_T A T 的列線性無關,並約定 P ∅ = 0 P_\varnothing=0 P ∅ = 0 。
引理 16.4.4
(投影後的限制等距性與交叉相關)
設階數 k k k 的 RIP 以常數 δ < 1 \delta\lt1 δ < 1 成立。對每個指標屬於 U U U 的 u u u 及指標屬於 V V V 的 v v v ,
( 1 − δ ) ∥ u ∥ 2 2 ≤ ∥ B U u ∥ 2 2 ≤ ( 1 + δ ) ∥ u ∥ 2 2 , ∣ ⟨ B U u , B V v ⟩ ∣ ≤ δ ∥ u ∥ 2 ∥ v ∥ 2 , (1-\delta)\|u\|_2^2\leq\|B_Uu\|_2^2\leq(1+\delta)\|u\|_2^2,\qquad
|\langle B_Uu,B_Vv\rangle|\leq\delta\|u\|_2\|v\|_2, ( 1 − δ ) ∥ u ∥ 2 2 ≤ ∥ B U u ∥ 2 2 ≤ ( 1 + δ ) ∥ u ∥ 2 2 , ∣ ⟨ B U u , B V v ⟩ ∣ ≤ δ ∥ u ∥ 2 ∥ v ∥ 2 , 而且把 U U U 換成 U ∪ V U\cup V U ∪ V 時範數界仍然成立。
對 U U U 上的向量 u u u ,正交投影使到 span ( A T ) \operatorname{span}(A_T) span ( A T ) 的距離最小,所以
∥ B U u ∥ 2 2 = min c ∥ A U u − A T c ∥ 2 2 ≥ ( 1 − δ ) min c ( ∥ u ∥ 2 2 + ∥ c ∥ 2 2 ) = ( 1 − δ ) ∥ u ∥ 2 2 . \|B_Uu\|_2^2=\min_c\|A_Uu-A_Tc\|_2^2\geq(1-\delta)\min_c(\|u\|_2^2+\|c\|_2^2)=(1-\delta)\|u\|_2^2. ∥ B U u ∥ 2 2 = c min ∥ A U u − A T c ∥ 2 2 ≥ ( 1 − δ ) c min ( ∥ u ∥ 2 2 + ∥ c ∥ 2 2 ) = ( 1 − δ ) ∥ u ∥ 2 2 . 選 c = 0 c=0 c = 0 並用 RIP 上界,得到 ∥ B U u ∥ 2 2 ≤ ( 1 + δ ) ∥ u ∥ 2 2 \|B_Uu\|_2^2\leq(1+\delta)\|u\|_2^2 ∥ B U u ∥ 2 2 ≤ ( 1 + δ ) ∥ u ∥ 2 2 。同樣的上下界適用於聯集 U ∪ V U\cup V U ∪ V 。至於交叉項,先把非零的 u , v u,v u , v 各自除以範數,再把上下界套到其和與差。由於支撐集不相交,這兩個係數向量的範數平方均為二;極化恆等式把內積的四倍限制在 4 δ 4\delta 4 δ 以內。再乘回原有範數;零向量的情況顯然成立。
證明透視
投影後的列為何仍保有等距性 關鍵一步是把 ∥ B U u ∥ 2 \|B_Uu\|_2 ∥ B U u ∥ 2 看成對 T T T 上所有重擬合 c c c 取最小值。每個競爭者 A U u − A T c A_Uu-A_Tc A U u − A T c 都是一個支撐在 T ∪ U T\cup U T ∪ U 上的向量之像,所以 RIP 下界適用,且其範數平方為 ∥ u ∥ 2 2 + ∥ c ∥ 2 2 ≥ ∥ u ∥ 2 2 \|u\|_2^2+\|c\|_2^2\geq\|u\|_2^2 ∥ u ∥ 2 2 + ∥ c ∥ 2 2 ≥ ∥ u ∥ 2 2 ;這裏用到 ∣ T ∣ + ∣ U ∣ ≤ k |T|+|U|\leq k ∣ T ∣ + ∣ U ∣ ≤ k ,投影並不損失下界常數。上界只需單一競爭者 c = 0 c=0 c = 0 。
交叉相關界是另一個獨立步驟。極化恆等式把 4 ⟨ B U u , B V v ⟩ 4\langle B_Uu,B_Vv\rangle 4 ⟨ B U u , B V v ⟩ 寫成 ∥ B U u + B V v ∥ 2 2 \|B_Uu+B_Vv\|_2^2 ∥ B U u + B V v ∥ 2 2 與 ∥ B U u − B V v ∥ 2 2 \|B_Uu-B_Vv\|_2^2 ∥ B U u − B V v ∥ 2 2 之差,因此需要 U ∪ V U\cup V U ∪ V 上的範數界,亦即完整的條件 ∣ T ∣ + ∣ U ∣ + ∣ V ∣ ≤ k |T|+|U|+|V|\leq k ∣ T ∣ + ∣ U ∣ + ∣ V ∣ ≤ k 。U U U 與 V V V 不相交,才使 u ± v u\pm v u ± v 的範數平方恰為二;否則兩個誤差項不會相消成 4 δ 4\delta 4 δ 。
故重新擬合之後,互不相交的訊號組之投影交叉相關性仍受控制。假設 y = A T c + A U β + e y=A_Tc+A_U\beta+e y = A T c + A U β + e ,其中 β \beta β 的指標屬於 U U U ,且 ∥ e ∥ 2 ≤ ε \|e\|_2\leq\varepsilon ∥ e ∥ 2 ≤ ε 。在 T T T 上做最小二乘擬合後,殘差是 r = Q y = Q A U β + Q e r=Qy=QA_U\beta+Qe r = Q y = Q A U β + Q e 。錯誤組的投影相關性滿足
∥ B V ⊤ r ∥ 2 ≤ δ ∥ β ∥ 2 + 1 + δ ε . \|B_V^\top r\|_2\leq\delta\|\beta\|_2+\sqrt{1+\delta}\,\varepsilon. ∥ B V ⊤ r ∥ 2 ≤ δ ∥ β ∥ 2 + 1 + δ ε .
訊號項由引理對單位 v v v 取上確界而來;雜訊項則由 Cauchy–Schwarz 不等式、投影上界,以及正交投影的收縮性 ∥ Q e ∥ 2 ≤ ∥ e ∥ 2 ≤ ε \|Qe\|_2\leq\|e\|_2\leq\varepsilon ∥ Q e ∥ 2 ≤ ∥ e ∥ 2 ≤ ε 得到。這只是針對指定不相交集合的界,並不是 OMP 的選擇定理:要證明選擇正確,還須給出嚴格更大的正確相關性下界,並處理所有候選指標及停止條件。
投影後的界亦控制正確集合 U U U 上的代理值,這與為錯誤組相關性定界是兩回事。令 H = B U ⊤ B U H=B_U^\top B_U H = B U ⊤ B U ,投影後的 RIP 表示 H H H 的所有特徵值均在 [ 1 − δ , 1 + δ ] [1-\delta,1+\delta] [ 1 − δ , 1 + δ ] 內,因此 ∥ H − I ∥ 2 ≤ δ \|H-I\|_2\leq\delta ∥ H − I ∥ 2 ≤ δ 。由 Q 2 = Q Q^2=Q Q 2 = Q 及 B U ⊤ Q = B U ⊤ B_U^\top Q=B_U^\top B U ⊤ Q = B U ⊤ ,可得
∥ B U ⊤ r − β ∥ 2 = ∥ ( H − I ) β + B U ⊤ Q e ∥ 2 ≤ δ ∥ β ∥ 2 + 1 + δ ε . \|B_U^\top r-\beta\|_2=\|(H-I)\beta+B_U^\top Qe\|_2\leq\delta\|\beta\|_2+\sqrt{1+\delta}\,\varepsilon. ∥ B U ⊤ r − β ∥ 2 = ∥ ( H − I ) β + B U ⊤ Q e ∥ 2 ≤ δ ∥ β ∥ 2 + 1 + δ ε .
兩項分別量度投影後 Gram 矩陣的偏差與投影後的雜訊。這解釋了「投影後的相關性不是係數」一例中的代理值誤差比較。它沒有說代理值等於係數;要比較正確與錯誤的界並得出選擇結論,仍須適當的係數大小。
訊號有尾項時有何改變?
精確稀疏是一種理想化:量測可能包含幾個大係數,以及許多小係數。令 x s x_s x s 保留 x x x 中絕對值最大的 s s s 項,相等時以任一固定方式選取,並寫 r = x − x s r=x-x_s r = x − x s 。這是歐氏(Euclidean)範數下的最佳 s s s 項近似:固定支撐集後,最佳係數就是 x x x 本身的座標,所以保留平方最大的項使捨棄的平方和最小。然而被捨棄的尾項仍進入量測:y = A x + e = A x s + ( A r + e ) y=Ax+e=Ax_s+(Ar+e) y = A x + e = A x s + ( A r + e ) 。從 s s s 稀疏模型的角度看,有效雜訊是物理雜訊與尾項量測之和。
命題 16.4.5
(可壓縮訊號的最小殘差稀疏擬合)
設 ∥ e ∥ 2 ≤ ε \|e\|_2\leq\varepsilon ∥ e ∥ 2 ≤ ε 、2 s ≤ N 2s\leq N 2 s ≤ N ,且階數 2 s 2s 2 s 的 RIP 以 δ < 1 \delta<1 δ < 1 成立。令 z z z 在所有至多 s s s 個非零項的向量中使 ∥ A z − y ∥ 2 \|Az-y\|_2 ∥ A z − y ∥ 2 最小,並設 E = 2 ( ε + ∥ A r ∥ 2 ) / 1 − δ E=2(\varepsilon+\|Ar\|_2)/\sqrt{1-\delta} E = 2 ( ε + ∥ A r ∥ 2 ) / 1 − δ 。則
∥ z − x s ∥ 2 ≤ E , ∥ z − x ∥ 2 ≤ E + ∥ r ∥ 2 . \|z-x_s\|_2\leq E,\qquad \|z-x\|_2\leq E+\|r\|_2. ∥ z − x s ∥ 2 ≤ E , ∥ z − x ∥ 2 ≤ E + ∥ r ∥ 2 .
最小化解存在:大小至多 s s s 的支撐集只有有限多個,相應子矩陣的像都是閉的有限維子空間,正交投影給出各支撐集上的最佳擬合。因 x s x_s x s 是合法競爭者,∥ A z − y ∥ 2 ≤ ∥ A x s − y ∥ 2 = ∥ A r + e ∥ 2 ≤ ε + ∥ A r ∥ 2 \|Az-y\|_2\leq\|Ax_s-y\|_2=\|Ar+e\|_2\leq\varepsilon+\|Ar\|_2 ∥ A z − y ∥ 2 ≤ ∥ A x s − y ∥ 2 = ∥ A r + e ∥ 2 ≤ ε + ∥ A r ∥ 2 。三角不等式及對至多 2 s 2s 2 s 稀疏向量 z − x s z-x_s z − x s 使用 RIP,得到
∥ z − x s ∥ 2 ≤ ∥ A z − y ∥ 2 + ∥ y − A x s ∥ 2 1 − δ ≤ 2 ( ε + ∥ A r ∥ 2 ) 1 − δ . \|z-x_s\|_2\leq\frac{\|Az-y\|_2+\|y-Ax_s\|_2}{\sqrt{1-\delta}}\leq\frac{2(\varepsilon+\|Ar\|_2)}{\sqrt{1-\delta}}. ∥ z − x s ∥ 2 ≤ 1 − δ ∥ A z − y ∥ 2 + ∥ y − A x s ∥ 2 ≤ 1 − δ 2 ( ε + ∥ A r ∥ 2 ) . 第二個不等式由 ∥ z − x ∥ 2 ≤ ∥ z − x s ∥ 2 + ∥ r ∥ 2 \|z-x\|_2\leq\|z-x_s\|_2+\|r\|_2 ∥ z − x ∥ 2 ≤ ∥ z − x s ∥ 2 + ∥ r ∥ 2 得出。
∥ r ∥ 2 \|r\|_2 ∥ r ∥ 2 這一項不可省略:即使完美恢復 x s x_s x s ,被捨棄的部分仍未重建。對最大項相等時的任何支撐集選法,估計同樣成立。這是理想化的比較,並非有效率的搜尋算法;它不表示某個數值求解器能找到最佳擬合,也不是 ℓ 1 \ell_1 ℓ 1 最小化解的保證,後者需要另外的論證。
另一個理想化問題是在 ∥ A z − y ∥ 2 ≤ η \|Az-y\|_2\leq\eta ∥ A z − y ∥ 2 ≤ η 的約束下最小化 ∥ z ∥ 0 \|z\|_0 ∥ z ∥ 0 ,其中 η ≥ ε + ∥ A r ∥ 2 \eta\geq\varepsilon+\|Ar\|_2 η ≥ ε + ∥ A r ∥ 2 。x s x_s x s 可行,所以每個全局最小化解至多有 s s s 個非零項,兩可行向量定理給出 ∥ z − x ∥ 2 ≤ 2 η / 1 − δ + ∥ r ∥ 2 \|z-x\|_2\leq 2\eta/\sqrt{1-\delta}+\|r\|_2 ∥ z − x ∥ 2 ≤ 2 η / 1 − δ + ∥ r ∥ 2 。最小化解存在:取存在可行向量的最小支撐集大小即可。殘差容許值必須涵蓋尾項;只用 ε \varepsilon ε 未必使 x s x_s x s 可行。這與上面的最小殘差問題是不同的最優化問題,但兩個估計使用相同的稀疏差向量論證。
∥ A r ∥ 2 \|Ar\|_2 ∥ A r ∥ 2 取決於感測矩陣,不知道尾項時可能難以計算。不過有一個簡單的確定性界。階數 2 s 2s 2 s 的 RIP 給出每列 ∥ a j ∥ 2 ≤ 1 + δ \|a_j\|_2\leq\sqrt{1+\delta} ∥ a j ∥ 2 ≤ 1 + δ 。把 A r Ar A r 展開為各列之和並用三角不等式,得 ∥ A r ∥ 2 ≤ 1 + δ ∥ r ∥ 1 \|Ar\|_2\leq\sqrt{1+\delta}\|r\|_1 ∥ A r ∥ 2 ≤ 1 + δ ∥ r ∥ 1 。此界忽略相消,往往偏保守。較精細的確定性界使用分塊:把 r r r 的非零座標按絕對值遞減排列,依次切成大小為 s s s 的組 T 1 , … , T J T_1,\ldots,T_J T 1 , … , T J (最後一組可以較小)。對每塊使用階數 s s s 的 RIP,並注意 T j T_j T j 的每項都不大於 T j − 1 T_{j-1} T j − 1 上的平均絕對值,便得
∥ A r ∥ 2 ≤ ∑ j = 1 J ∥ A r T j ∥ 2 ≤ 1 + δ s ∑ j = 1 J ∥ r T j ∥ 2 , ∥ r T j ∥ 2 ≤ s max i ∈ T j ∣ r i ∣ ≤ ∥ r T j − 1 ∥ 1 s ( j ≥ 2 ) . \|Ar\|_2\leq\sum_{j=1}^J\|Ar_{T_j}\|_2\leq\sqrt{1+\delta_s}\sum_{j=1}^J\|r_{T_j}\|_2,\qquad
\|r_{T_j}\|_2\leq\sqrt s\max_{i\in T_j}|r_i|\leq\frac{\|r_{T_{j-1}}\|_1}{\sqrt s}\quad(j\geq2). ∥ A r ∥ 2 ≤ j = 1 ∑ J ∥ A r T j ∥ 2 ≤ 1 + δ s j = 1 ∑ J ∥ r T j ∥ 2 , ∥ r T j ∥ 2 ≤ s i ∈ T j max ∣ r i ∣ ≤ s ∥ r T j − 1 ∥ 1 ( j ≥ 2 ) .
對 j ≥ 2 j\geq2 j ≥ 2 求和,再用 ∥ r T 1 ∥ 2 ≤ ∥ r ∥ 2 \|r_{T_1}\|_2\leq\|r\|_2 ∥ r T 1 ∥ 2 ≤ ∥ r ∥ 2 ,得到
∥ A r ∥ 2 ≤ 1 + δ s ( ∥ r ∥ 2 + ∥ r ∥ 1 s ) . \|Ar\|_2\leq\sqrt{1+\delta_s}\left(\|r\|_2+\frac{\|r\|_1}{\sqrt s}\right). ∥ A r ∥ 2 ≤ 1 + δ s ( ∥ r ∥ 2 + s ∥ r ∥ 1 ) .
零尾項給出零;只有一組時,第二個和式為空。此界不要求尾項稀疏,兩個界可取較小者。
很容易寫出 ∥ A r ∥ 2 ≤ 1 + δ ∥ r ∥ 2 \|Ar\|_2\leq\sqrt{1+\delta}\|r\|_2 ∥ A r ∥ 2 ≤ 1 + δ ∥ r ∥ 2 。當 r r r 有多於 2 s 2s 2 s 個非零項時,這一步沒有根據,因為階數 2 s 2s 2 s 的 RIP 對這類向量沒有任何說法。逐列界 1 + δ ∥ r ∥ 1 \sqrt{1+\delta}\|r\|_1 1 + δ ∥ r ∥ 1 對稠密尾項仍然有效。另外,單個尾項係數很小,並不表示許多小係數合起來的尾項可以忽略。
係數誤差與支撐集判定
向量誤差界只有配合真係數大小的下界,才能變成支撐集判定。
設 2 s ≤ N 2s\leq N 2 s ≤ N ,且階數 2 s 2s 2 s 的 RIP 以 δ < 1 \delta<1 δ < 1 成立。假設真 x x x 恰好 s s s 稀疏、支撐集為 S S S ,而 z z z 與 x x x 均為 s s s 稀疏,且與 y y y 的擬合誤差都不超過 ε \varepsilon ε 。令 B = 2 ε / 1 − δ B=2\varepsilon/\sqrt{1-\delta} B = 2 ε / 1 − δ 。若 x x x 的每個非零項絕對值都嚴格大於 2 B 2B 2 B ,則 { j : ∣ z j ∣ > B } = S \{j:|z_j|>B\}=S { j : ∣ z j ∣ > B } = S 。
唯一性與雜訊穩定性定理給出 ∥ z − x ∥ 2 ≤ B \|z-x\|_2\leq B ∥ z − x ∥ 2 ≤ B ,所以每個座標誤差至多為 B B B 。在 S S S 以外,∣ z j ∣ |z_j| ∣ z j ∣ 至多為 B B B ;在 S S S 之內,∣ z j ∣ ≥ ∣ x j ∣ − B |z_j|\geq|x_j|-B ∣ z j ∣ ≥ ∣ x j ∣ − B ,嚴格大於 B B B 。門檻規則只在絕對值超過 B B B 時才判定指標存在,所以恰好給出 S S S ;嚴格不等式亦消除了門檻上的歧義。
這是充分而非必要條件;實際誤差可能遠小於上界。係數太小時有一個基本障礙。設 ε > 0 \varepsilon>0 ε > 0 ,A A A 有單位列 a j a_j a j ,取非零純量 t t t 使 ∣ t ∣ ≤ ε |t|\leq\varepsilon ∣ t ∣ ≤ ε 。觀測 y = 0 y=0 y = 0 既符合 x = 0 x=0 x = 0 且無雜訊,也符合 x = t e j x=te_j x = t e j 且雜訊 e = − t a j e=-ta_j e = − t a j 。兩個雜訊都滿足同一界,支撐集卻不同。只用 y y y 、A A A 及雜訊界的規則,無法在兩種情況下都辨認支撐集。即使對單位矩陣,這個歧義仍然存在,所以它不只是由條件差的列引起。
例題
取 a 1 = ( 1 , 0 ) ⊤ a_1=(1,0)^\top a 1 = ( 1 , 0 ) ⊤ 、a 2 = ( 1 / 2 , 3 / 2 ) ⊤ a_2=(1/2,\sqrt3/2)^\top a 2 = ( 1/2 , 3 /2 ) ⊤ 。Gram 矩陣的特徵值為 1 / 2 1/2 1/2 和 3 / 2 3/2 3/2 ,故 δ 2 = 1 / 2 \delta_2=1/2 δ 2 = 1/2 。每個一稀疏向量都可由精確量測唯一識別。取 S = { 1 , 2 } S=\{1,2\} S = { 1 , 2 } 、β = ( 1 , 2 ) ⊤ \beta=(1,2)^\top β = ( 1 , 2 ) ⊤ 和 e = ( 0 , 1 / 10 ) ⊤ e=(0,1/10)^\top e = ( 0 , 1/10 ) ⊤ ,直接解三角方程得到 β ^ = ( 1 − 1 / ( 10 3 ) , 2 + 1 / ( 5 3 ) ) ⊤ \widehat\beta=(1-1/(10\sqrt3),\,2+1/(5\sqrt3))^\top β = ( 1 − 1/ ( 10 3 ) , 2 + 1/ ( 5 3 ) ) ⊤ 。係數誤差的範數為 5 / 3 / 10 < 2 / 10 \sqrt{5/3}/10<\sqrt2/10 5/3 /10 < 2 /10 ,符合已知支撐集的界。兩列生成 R 2 \mathbb R^2 R 2 ,所以殘差為零;零殘差沒有消除係數誤差。
取單位列 a 1 = e 1 a_1=e_1 a 1 = e 1 、a 2 = ( e 1 + 3 e 2 ) / 2 a_2=(e_1+\sqrt3e_2)/2 a 2 = ( e 1 + 3 e 2 ) /2 、a 3 = e 3 a_3=e_3 a 3 = e 3 。完整 Gram 矩陣特徵值為 1 / 2 , 1 , 3 / 2 1/2,1,3/2 1/2 , 1 , 3/2 ,故 δ 3 = 1 / 2 \delta_3=1/2 δ 3 = 1/2 。令 T = { 1 } T=\{1\} T = { 1 } ,則 Q a 2 = 3 e 2 / 2 Qa_2=\sqrt3e_2/2 Q a 2 = 3 e 2 /2 ,Q a 3 = e 3 Qa_3=e_3 Q a 3 = e 3 。內積為零,符合上界 0 ≤ 1 / 2 0\leq1/2 0 ≤ 1/2 。可是 ∥ Q a 2 ∥ 2 2 = 3 / 4 \|Qa_2\|_2^2=3/4 ∥ Q a 2 ∥ 2 2 = 3/4 而非一:不能默默把投影後的列當作單位向量。
設 a 1 = ( 1 , 0 ) ⊤ a_1=(1,0)^\top a 1 = ( 1 , 0 ) ⊤ 、a 2 = ( 3 / 5 , 4 / 5 ) ⊤ a_2=(3/5,4/5)^\top a 2 = ( 3/5 , 4/5 ) ⊤ 、T = { 1 } T=\{1\} T = { 1 } ,且 y = 2 a 1 + a 2 + ( 0 , 1 / 10 ) ⊤ y=2a_1+a_2+(0,1/10)^\top y = 2 a 1 + a 2 + ( 0 , 1/10 ) ⊤ 。這裏 δ 2 = 3 / 5 \delta_2=3/5 δ 2 = 3/5 、ε = 1 / 10 \varepsilon=1/10 ε = 1/10 。在 T T T 上重新擬合後,r = ( 0 , 9 / 10 ) ⊤ r=(0,9/10)^\top r = ( 0 , 9/10 ) ⊤ ,且 Q a 2 = ( 0 , 4 / 5 ) ⊤ Qa_2=(0,4/5)^\top Q a 2 = ( 0 , 4/5 ) ⊤ 。兩者的相關性是 18 / 25 18/25 18/25 ,但剩餘的真係數為一。即使沒有雜訊,相關性也只有 16 / 25 16/25 16/25 ,因為投影改變了列的長度。除以 ∥ Q a 2 ∥ 2 2 = 16 / 25 \|Qa_2\|_2^2=16/25 ∥ Q a 2 ∥ 2 2 = 16/25 可得到單列最小二乘係數,但比較相關性時使用的是未除的值。上面的正確集合代理值界容許的誤差為 3 / 5 + 8 / 5 / 10 3/5+\sqrt{8/5}/10 3/5 + 8/5 /10 ,大於實際的代理值誤差 7 / 25 7/25 7/25 。
例題 16.4.10
(稀疏唯一性與非平凡零空間可以並存)
考慮
A = ( 1 0 1 / 2 0 1 1 / 2 ) . A=\begin{pmatrix}1&0&1/\sqrt2\\0&1&1/\sqrt2\end{pmatrix}. A = ( 1 0 0 1 1/ 2 1/ 2 ) . 每列長度都是一,所以 δ 1 = 0 \delta_1=0 δ 1 = 0 。第一、二列的 Gram 矩陣為 I 2 I_2 I 2 ;第一、三列或第二、三列的 Gram 矩陣均有特徵值 1 ± 1 / 2 1\pm1/\sqrt2 1 ± 1/ 2 。因此 δ 2 = 1 / 2 < 1 \delta_2=1/\sqrt2<1 δ 2 = 1/ 2 < 1 ,任何兩個不同的一稀疏向量都不會給出相同的精確量測。然而 v = ( − 1 / 2 , − 1 / 2 , 1 ) ⊤ v=(-1/\sqrt2,-1/\sqrt2,1)^\top v = ( − 1/ 2 , − 1/ 2 , 1 ) ⊤ 滿足 A v = 0 Av=0 A v = 0 ,所以對 y = ( 1 , 0 ) ⊤ y=(1,0)^\top y = ( 1 , 0 ) ⊤ ,每個
z ( t ) = ( 1 − t / 2 , − t / 2 , t ) ⊤ , t ∈ R , z(t)=(1-t/\sqrt2,\,-t/\sqrt2,\,t)^\top,\qquad t\in\mathbb R, z ( t ) = ( 1 − t / 2 , − t / 2 , t ) ⊤ , t ∈ R , 都滿足 A z ( t ) = y Az(t)=y A z ( t ) = y 。當 t = 0 t=0 t = 0 ,它是一稀疏解;當 t = 1 t=1 t = 1 ,三個座標均非零。兩解之差的支撐集有三項,超出階數二 RIP 的控制範圍,所以沒有矛盾。單有零殘差,不足以保證任意解接近稀疏真值。
取 A = I 3 A=I_3 A = I 3 、s = 1 s=1 s = 1 、x = ( 3 , 1 / 5 , − 1 / 10 ) ⊤ x=(3,1/5,-1/10)^\top x = ( 3 , 1/5 , − 1/10 ) ⊤ 及 e = ( 0 , 1 / 10 , 0 ) ⊤ e=(0,1/10,0)^\top e = ( 0 , 1/10 , 0 ) ⊤ 。於是 y = ( 3 , 3 / 10 , − 1 / 10 ) ⊤ y=(3,3/10,-1/10)^\top y = ( 3 , 3/10 , − 1/10 ) ⊤ ,而 x s = ( 3 , 0 , 0 ) ⊤ x_s=(3,0,0)^\top x s = ( 3 , 0 , 0 ) ⊤ 、r = ( 0 , 1 / 5 , − 1 / 10 ) ⊤ r=(0,1/5,-1/10)^\top r = ( 0 , 1/5 , − 1/10 ) ⊤ 。最佳一稀疏擬合保留 y y y 中絕對值最大的座標,得 z = ( 3 , 0 , 0 ) ⊤ z=(3,0,0)^\top z = ( 3 , 0 , 0 ) ⊤ 。這裏 δ 2 = 0 \delta_2=0 δ 2 = 0 、ε = 1 / 10 \varepsilon=1/10 ε = 1/10 、∥ A r ∥ 2 = 5 / 10 \|Ar\|_2=\sqrt5/10 ∥ A r ∥ 2 = 5 /10 。一般界為 E = ( 1 + 5 ) / 5 E=(1+\sqrt5)/5 E = ( 1 + 5 ) /5 ,實際距離 ∥ z − x s ∥ 2 \|z-x_s\|_2 ∥ z − x s ∥ 2 卻是零。總誤差 ∥ z − x ∥ 2 = 5 / 10 \|z-x\|_2=\sqrt5/10 ∥ z − x ∥ 2 = 5 /10 正是被捨棄的尾項。若只用逐列界 ∥ A r ∥ 2 ≤ ∥ r ∥ 1 = 3 / 10 \|Ar\|_2\leq\|r\|_1=3/10 ∥ A r ∥ 2 ≤ ∥ r ∥ 1 = 3/10 ,便得較鬆的 E ≤ 4 / 5 E\leq4/5 E ≤ 4/5 。兩個界都不預測等號成立。
常見錯誤
反例模式
單列條件良好不能證明一稀疏唯一性 設 A = [ a a ] A=[a\ a] A = [ a a ] ,其中 a a a 是單位向量。每個一稀疏 x x x 都滿足 ∥ A x ∥ 2 = ∥ x ∥ 2 \|Ax\|_2=\|x\|_2 ∥ A x ∥ 2 = ∥ x ∥ 2 ,所以階數一的常數為零。然而 A ( 1 , 0 ) ⊤ = A ( 0 , 1 ) ⊤ A(1,0)^\top=A(0,1)^\top A ( 1 , 0 ) ⊤ = A ( 0 , 1 ) ⊤ 。由於 ( 1 , − 1 ) ⊤ (1,-1)^\top ( 1 , − 1 ) ⊤ 在零空間中,階數二的下界失效。因此即使階數一的條件完美,也不足以證明一稀疏向量的唯一性。
RIP 是充分條件,並非每個成功例子都必須滿足的必要描述。定義本身沒有提供有效率的方法計算 δ k \delta_k δ k ;直接方法之一是檢查相關的列子矩陣,而本節例子只計算很小矩陣的常數。
已知支撐集的估計假設正確的 S S S 已經給定。它沒有聲稱擬合能找到 S S S ,也沒有聲稱在雜訊中能辨認微小的非零係數;門檻推論需要真係數大小的明確下界。
單個錯誤組的投影相關性界只說明該組不能相關得太強。貪婪選擇正確,要求某個正確相關性嚴格大於每個錯誤相關性,這還需要正確代理值的下界及適當的係數大小。
總結
RIP 下界控制稀疏差向量及已知支撐集的擬合誤差,上界控制雜訊相關性。投影後,最小化論證仍保留其餘各列的限制範數界。這些結論的假設與結論各不相同,都不應與完整的稀疏恢復算法混淆。
習題
快速檢查
(假設 2 s ≤ N 2s\leq N 2 s ≤ N 、δ 2 s ≤ 1 / 4 \delta_{2s}\leq1/4 δ 2 s ≤ 1/4 ,兩個 s s s 稀疏向量各自的量測值與 y y y 的歐氏距離皆不超過 0.03 0.03 0.03 。求兩者距離的上界。)
解答 · 答案 距離至多為 0.06 / 3 / 4 = 0.12 / 3 ≈ 0.0693 0.06/\sqrt{3/4}=0.12/\sqrt3\approx0.0693 0.06/ 3/4 = 0.12/ 3 ≈ 0.0693 。這是上界,並不聲稱兩向量的距離必定等於 0.0693 0.0693 0.0693 。
快速檢查
(設 A = I 2 A=I_2 A = I 2 、S = { 1 } S=\{1\} S = { 1 } 、真係數為 2 2 2 、雜訊為 ( 1 / 5 , 1 / 10 ) ⊤ (1/5,1/10)^\top ( 1/5 , 1/10 ) ⊤ 。求已知支撐集的擬合、係數誤差及殘差,並驗證雜訊的畢氏(Pythagoras)恆等式。)
解答 · 答案 擬合值是 β ^ = 11 / 5 \widehat\beta=11/5 β = 11/5 ,係數誤差為 1 / 5 1/5 1/5 ,殘差為 ( 0 , 1 / 10 ) ⊤ (0,1/10)^\top ( 0 , 1/10 ) ⊤ 。擬合誤差 P S e = ( 1 / 5 , 0 ) ⊤ P_Se=(1/5,0)^\top P S e = ( 1/5 , 0 ) ⊤ 及殘差 ( I − P S ) e = ( 0 , 1 / 10 ) ⊤ (I-P_S)e=(0,1/10)^\top ( I − P S ) e = ( 0 , 1/10 ) ⊤ 的範數平方分別為 1 / 25 1/25 1/25 和 1 / 100 1/100 1/100 ,總和是 1 / 20 = ∥ e ∥ 2 2 1/20=\|e\|_2^2 1/20 = ∥ e ∥ 2 2 。因 δ = 0 \delta=0 δ = 0 ,係數上界為 1 / 20 \sqrt{1/20} 1/20 ,大於 1 / 5 1/5 1/5 。
快速檢查
(對「投影後的相關性」一例,計算 a 1 ⊤ a 2 a_1^\top a_2 a 1 ⊤ a 2 、∥ Q a 2 ∥ 2 2 \|Qa_2\|_2^2 ∥ Q a 2 ∥ 2 2 及 ⟨ Q a 2 , Q a 3 ⟩ \langle Qa_2,Qa_3\rangle ⟨ Q a 2 , Q a 3 ⟩ 。說明 a 2 a_2 a 2 是否與 a 1 a_1 a 1 線性無關。)
解答 · 答案 三個值依次為 1 / 2 1/2 1/2 、3 / 4 3/4 3/4 、零。非零的投影範數說明 a 2 a_2 a 2 不在 a 1 a_1 a 1 的生成空間內,故兩列雖有非零相關性,仍線性無關。
快速檢查
(設 A = [ a a ] A=[a\ a] A = [ a a ] ,a a a 為單位向量,且 y = a y=a y = a 。給出兩個不同的一稀疏精確解,並解釋為何唯一性定理不適用。)
解答 · 答案 ( 1 , 0 ) ⊤ (1,0)^\top ( 1 , 0 ) ⊤ 和 ( 0 , 1 ) ⊤ (0,1)^\top ( 0 , 1 ) ⊤ 均精確擬合。非零差向量 ( 1 , − 1 ) ⊤ (1,-1)^\top ( 1 , − 1 ) ⊤ 是二稀疏的零空間向量,因此階數二不可能有小於一的 RIP 常數。
快速檢查
(設 A = I 3 A=I_3 A = I 3 、s = 1 s=1 s = 1 、x = ( 2 , 1 / 5 , 0 ) ⊤ x=(2,1/5,0)^\top x = ( 2 , 1/5 , 0 ) ⊤ 及 e = ( 0 , 0 , 1 / 10 ) ⊤ e=(0,0,1/10)^\top e = ( 0 , 0 , 1/10 ) ⊤ 。求 y = A x + e y=Ax+e y = A x + e 的一個最佳一稀疏擬合、它與 x x x 的誤差,以及用精確 ∥ A r ∥ 2 \|Ar\|_2 ∥ A r ∥ 2 計算的尾項界 E + ∥ r ∥ 2 E+\|r\|_2 E + ∥ r ∥ 2 。)
解答 · 答案 數據為 ( 2 , 1 / 5 , 1 / 10 ) ⊤ (2,1/5,1/10)^\top ( 2 , 1/5 , 1/10 ) ⊤ ,保留最大座標得 z = ( 2 , 0 , 0 ) ⊤ z=(2,0,0)^\top z = ( 2 , 0 , 0 ) ⊤ 。這裏 x s = z x_s=z x s = z ,r = ( 0 , 1 / 5 , 0 ) ⊤ r=(0,1/5,0)^\top r = ( 0 , 1/5 , 0 ) ⊤ ,實際誤差 ∥ z − x ∥ 2 = 1 / 5 \|z-x\|_2=1/5 ∥ z − x ∥ 2 = 1/5 。由於 δ 2 = 0 \delta_2=0 δ 2 = 0 、∥ A r ∥ 2 = 1 / 5 \|Ar\|_2=1/5 ∥ A r ∥ 2 = 1/5 ,所給的界為 2 ( 1 / 10 + 1 / 5 ) + 1 / 5 = 4 / 5 2(1/10+1/5)+1/5=4/5 2 ( 1/10 + 1/5 ) + 1/5 = 4/5 。它只是上界,擬合不必達到。
快速檢查
(設門檻推論的假設以 δ = 3 / 4 \delta=3/4 δ = 3/4 、ε = 1 / 100 \varepsilon=1/100 ε = 1/100 成立。求 B B B ,以及使每個非零係數都能以門檻 B B B 偵測到的充分下界。為何係數絕對值恰好等於該下界時,證明不能保證偵測?)
解答 · 答案 B = 2 ( 1 / 100 ) / 1 / 4 = 1 / 25 B=2(1/100)/\sqrt{1/4}=1/25 B = 2 ( 1/100 ) / 1/4 = 1/25 。充分條件是每個非零係數的絕對值嚴格大於 2 / 25 2/25 2/25 。等號成立時,座標誤差原則上可把真係數的絕對值降至恰好 B B B ,而規則只保留嚴格大於 B B B 的值,所以證明不能保證這種情況。