笔记 / 详情

Matrix perturbation and Davis-Kahan Theorem

2026.04.08
方法备忘
4837 字数
目录

问题设定

矩阵扰动理论（matrix perturbation theory）研究的是：当一个矩阵由 M\mathbf M 变为 M~=M+Δ\tilde{\mathbf M}=\mathbf M+\mathbf\Delta 时，谱量（spectral quantities）如何变化。这里 Δ\mathbf\Delta 表示扰动，通常用谱范数 ∥Δ∥2\|\mathbf\Delta\|_2 或 Frobenius 范数 ∥Δ∥F\|\mathbf\Delta\|_F 衡量其大小。

一个基本区分是：特征值通常较稳定，而单个特征向量未必稳定。若某一组特征值之间存在重数或相距很近，则对应特征向量可以在同一不变子空间内发生任意旋转。因此，在统计估计、PCA、谱聚类和低秩矩阵分析中，更自然的对象通常不是某个特征向量本身，而是对应的特征子空间（eigenspace）或投影矩阵。

对称矩阵与谱子空间

设 M∈Rn×n\mathbf M\in\mathbb R^{n\times n} 为对称矩阵，其特征值分解为 M=UΛUT\mathbf M=\mathbf U\mathbf\Lambda\mathbf U^T，其中 U\mathbf U 为正交矩阵，Λ=diag⁡(λ1,…,λn)\mathbf\Lambda=\operatorname{diag}(\lambda_1,\dots,\lambda_n)。给定维数 r<nr<n，记 U1∈Rn×r\mathbf U_1\in\mathbb R^{n\times r} 为目标谱子空间的一组正交基，U2\mathbf U_2 为其正交补基，且 U1TU1=Ir\mathbf U_1^T\mathbf U_1=\mathbf I_r、U2TU2=In−r\mathbf U_2^T\mathbf U_2=\mathbf I_{n-r}。

对应的正交投影矩阵为 PU1=U1U1T\mathbf P_{\mathbf U_1}=\mathbf U_1\mathbf U_1^T。如果在同一个子空间内把基底改成 U1R\mathbf U_1\mathbf R，其中 RTR=Ir\mathbf R^T\mathbf R=\mathbf I_r，则投影矩阵不变。因此，PU1\mathbf P_{\mathbf U_1} 比 U1\mathbf U_1 本身更适合表示子空间。

Weyl 定理：特征值稳定性

设 M~=M+Δ\tilde{\mathbf M}=\mathbf M+\mathbf\Delta，且 λi\lambda_i 与 λ~i\tilde\lambda_i 分别为 M\mathbf M 与 M~\tilde{\mathbf M} 按同一顺序排列的特征值。Weyl 定理给出特征值扰动的基本界：

max⁡i∣λ~i−λi∣≤∥Δ∥2.\max_i|\tilde\lambda_i-\lambda_i|\le\|\mathbf\Delta\|_2.

该结论说明，特征值对谱范数扰动是 Lipschitz 稳定的。它不要求谱间隔（eigengap）存在；谱间隔真正影响的是特征向量或特征子空间的稳定性。

为什么比较子空间

直接比较 ∥U~1−U1∥F\|\tilde{\mathbf U}_1-\mathbf U_1\|_F 通常不是合适的，因为它依赖于基底选择。即使两个矩阵张成完全相同的子空间，只要选取的正交基相差一个旋转矩阵，该距离也可能不为零。更合理的比较方式是使用主角（principal angles）、投影矩阵差异，或正交补方向上的泄漏量。

设 A,B∈Rn×r\mathbf A,\mathbf B\in\mathbb R^{n\times r} 都有正交列，分别张成子空间 A\mathcal A 与 B\mathcal B。主角 θ1,…,θr\theta_1,\dots,\theta_r 由 ATB\mathbf A^T\mathbf B 的奇异值定义，即 σi(ATB)=cos⁡θi\sigma_i(\mathbf A^T\mathbf B)=\cos\theta_i。若 Bˉ\bar{\mathbf B} 是 B\mathbf B 的正交补基，则常用子空间距离为

d(A,B):=∥sin⁡Θ∥F=12∥PA−PB∥F=∥ATBˉ∥F.d(\mathcal A,\mathcal B):=\|\sin\mathbf\Theta\|_F =\frac{1}{\sqrt2}\|\mathbf P_{\mathbf A}-\mathbf P_{\mathbf B}\|_F =\|\mathbf A^T\bar{\mathbf B}\|_F.

这个等式把三个等价视角联系起来：主角的正弦、两个投影矩阵的差异，以及 A\mathcal A 向 B⊥\mathcal B^\perp 的泄漏程度。若 r=1r=1，它退化为两个单位向量夹角的正弦；若 r>1r>1，它描述的是两个 rr 维子空间的整体偏移。

正交 Procrustes 问题

如果必须比较两组基底，可以先消除基底旋转的不确定性。正交 Procrustes 问题为 min⁡RTR=Ir∥AR−B∥F2\min_{\mathbf R^T\mathbf R=\mathbf I_r}\|\mathbf A\mathbf R-\mathbf B\|_F^2。若 ATB=PΣQT\mathbf A^T\mathbf B=\mathbf P\mathbf\Sigma\mathbf Q^T，则最优旋转为 R^=PQT\hat{\mathbf R}=\mathbf P\mathbf Q^T。此时 ∥AR^−B∥F2=2r−2∑icos⁡θi\|\mathbf A\hat{\mathbf R}-\mathbf B\|_F^2=2r-2\sum_i\cos\theta_i，并且可由 ∥sin⁡Θ∥F2\|\sin\mathbf\Theta\|_F^2 控制。

因此，Procrustes 距离本质上是在“先对齐基底”后比较子空间。它常用于把 Davis-Kahan 型子空间误差转化为特征向量矩阵的误差界。

Davis-Kahan 正弦定理

设 M\mathbf M 和 M~=M+Δ\tilde{\mathbf M}=\mathbf M+\mathbf\Delta 均为对称矩阵。令 U1\mathbf U_1 与 U~1\tilde{\mathbf U}_1 分别表示目标谱簇对应的 rr 维特征子空间，令 δ\delta 表示该谱簇与其补空间之间的有效谱间隔。Davis-Kahan 正弦定理的典型形式为

∥sin⁡Θ(U~1,U1)∥F≤∥ΔU1∥Fδ≤r ∥Δ∥2δ.\|\sin\mathbf\Theta(\tilde{\mathbf U}_1,\mathbf U_1)\|_F \le \frac{\|\mathbf\Delta\mathbf U_1\|_F}{\delta} \le \frac{\sqrt r\,\|\mathbf\Delta\|_2}{\delta}.

这里 ∥sin⁡Θ(U~1,U1)∥F\|\sin\mathbf\Theta(\tilde{\mathbf U}_1,\mathbf U_1)\|_F 是两个特征子空间之间的距离。分子表示扰动强度，分母表示谱分离程度。若 δ\delta 很小，即使 ∥Δ∥2\|\mathbf\Delta\|_2 很小，特征子空间也可能发生显著旋转；若 δ\delta 足够大，子空间误差通常与 ∥Δ∥2/δ\|\mathbf\Delta\|_2/\delta 同阶。

证明思路可以概括为一个 Sylvester 方程。记 H=U~2TU1\mathbf H=\tilde{\mathbf U}_2^T\mathbf U_1，则由 M~−M=Δ\tilde{\mathbf M}-\mathbf M=\mathbf\Delta 可得到 U~2TΔU1=Λ~2H−HΛ1\tilde{\mathbf U}_2^T\mathbf\Delta\mathbf U_1=\tilde{\mathbf\Lambda}_2\mathbf H-\mathbf H\mathbf\Lambda_1。当两块谱之间相距至少 δ\delta 时，右侧线性算子可逆并具有下界，从而得到 ∥H∥F≤∥U~2TΔU1∥F/δ\|\mathbf H\|_F\le\|\tilde{\mathbf U}_2^T\mathbf\Delta\mathbf U_1\|_F/\delta。这正是主角正弦距离的控制。

常见的充分条件是：原矩阵目标谱簇与其余谱之间存在间隔，且扰动谱范数小于该间隔的常数倍。具体常数取决于定理采用的是原始谱间隔、扰动后谱间隔，还是二者之间的分离距离。

Wedin 定理：一般矩阵的奇异子空间扰动

当 M\mathbf M 不是对称矩阵时，应比较奇异子空间。设 M=UΣVT\mathbf M=\mathbf U\mathbf\Sigma\mathbf V^T，并令 U1,V1\mathbf U_1,\mathbf V_1 表示前 rr 个奇异方向；扰动后相应记为 U~1,V~1\tilde{\mathbf U}_1,\tilde{\mathbf V}_1。若目标奇异值簇与剩余奇异值之间存在有效间隔 δ>0\delta>0，Wedin 定理给出

∥sin⁡Θ(U~1,U1)∥F2+∥sin⁡Θ(V~1,V1)∥F2≤∥U1TΔ∥F2+∥ΔV1∥F2δ2.\|\sin\mathbf\Theta(\tilde{\mathbf U}_1,\mathbf U_1)\|_F^2 + \|\sin\mathbf\Theta(\tilde{\mathbf V}_1,\mathbf V_1)\|_F^2 \le \frac{\|\mathbf U_1^T\mathbf\Delta\|_F^2+\|\mathbf\Delta\mathbf V_1\|_F^2}{\delta^2}.

该结果是 Davis-Kahan 定理在奇异值分解中的对应形式：它同时控制左奇异子空间与右奇异子空间。若只研究对称矩阵的特征子空间，Davis-Kahan 已足够；若研究低秩矩阵、矩阵补全或一般矩阵估计，Wedin 型界通常更自然。

使用时需要注意的点

  • 特征值稳定不等于特征向量稳定。特征向量稳定性需要谱间隔。
  • 单个特征向量有符号不确定性；多维特征子空间还有旋转不确定性。因此，投影矩阵或主角距离通常更稳健。
  • Davis-Kahan 控制的是子空间误差，而不是逐个坐标的误差。若需要逐行或逐元素控制，通常还需要更强的条件。
  • 对称矩阵使用 Davis-Kahan；一般矩阵的左右奇异子空间扰动通常使用 Wedin 定理。
  • 在统计应用中，误差界常写成“扰动大小 / 谱间隔”。估计质量不仅取决于噪声强度，也取决于目标谱结构是否可分离。

一句话总结

矩阵扰动理论的核心是：Weyl 定理说明特征值对谱范数扰动稳定；Davis-Kahan 与 Wedin 定理说明特征子空间或奇异子空间的误差由扰动大小和谱间隔的比值控制。真正决定谱方法稳定性的，不只是扰动是否小，而是扰动相对于 eigengap 是否足够小。

References

  1. C. Davis and W. M. Kahan, The Rotation of Eigenvectors by a Perturbation. III, SIAM Journal on Numerical Analysis, 7(1), 1970.
  2. P.-Å. Wedin, Perturbation Bounds in Connection with Singular Value Decomposition, BIT Numerical Mathematics, 12(1), 1972.
  3. G. W. Stewart and J.-G. Sun, Matrix Perturbation Theory, Academic Press, 1990.
  4. R. Bhatia, Matrix Analysis, Springer, 1997.