动机
欠定矩阵有非零零空间向量,因此不可能从测量值唯一恢复任意系数。稀疏恢复问的是较窄的问题:两个只有少量非零项的向量,能否产生相同的测量值?即使答案是否定的,即稀疏向量由测量唯一确定,数值重建仍须处理噪声。本节区分三种结论:稀疏向量之间的唯一性、已知正确支撑集时的稳定性,以及移除已选列后的相关性界。这些结论本身都不保证算法能找到支撑集。
定义
设 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 ) ⊤ 。求已知支撑集的拟合、系数误差及残差,并验证噪声的勾股恒等式。)
解答 · 答案 拟合值是 β ^ = 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 的值,所以证明不能保证这种情形。