矩阵扰动（matrix perturbation）与 Davis-Kahan 定理

这篇笔记想解决什么

设

$$\tilde{\mathbf M} = \mathbf M+\mathbf \Delta.$$

我们想知道：当矩阵受到一个小扰动（perturbation）$\mathbf \Delta$ 时，特征值（eigenvalues）和特征向量（eigenvectors）到底会变多少。

一个基本事实是：

• 特征值通常比较稳定。
• 特征向量本身往往不稳定，真正稳定的是对应的不变子空间（invariant subspace）。

这也是 Davis-Kahan 定理最核心的出发点。

对称矩阵的特征子空间分解

设 $\mathbf M\in\mathbb R^{n\times n}$ 是对称矩阵（symmetric matrix），其特征值分解（eigenvalue decomposition, EVD）写成

$$\mathbf M = \mathbf U\mathbf \Lambda \mathbf U^T,$$

其中 $\mathbf U\in\mathbb R^{n\times n}$ 是正交矩阵（orthogonal matrix），$\mathbf \Lambda=\operatorname{diag}(\lambda_1,\dots,\lambda_n)$。

给定整数 $r<n$，可将前 $r$ 个特征方向与剩余方向拆成两块：

$$\mathbf M = \begin{bmatrix} \mathbf U_1 & \mathbf U_2 \end{bmatrix} \begin{bmatrix} \mathbf \Lambda_1 & \mathbf 0 \\ \mathbf 0 & \mathbf \Lambda_2 \end{bmatrix} \begin{bmatrix} \mathbf U_1^T \\ \mathbf U_2^T \end{bmatrix},$$

其中

$$\mathbf \Lambda_1=\operatorname{diag}(\lambda_1,\dots,\lambda_r), \qquad \mathbf \Lambda_2=\operatorname{diag}(\lambda_{r+1},\dots,\lambda_n).$$

$\mathbf U_1,\mathbf U_2$ 都是半正交矩阵（semi-orthogonal matrix），满足

$$\mathbf U_1^T\mathbf U_1=\mathbf I_r, \qquad \mathbf U_2^T\mathbf U_2=\mathbf I_{n-r}.$$

对应的正交投影（orthogonal projection）分别是

$$\mathbf P_{\mathbf U_1}=\mathbf U_1\mathbf U_1^T, \qquad \mathbf P_{\mathbf U_2}=\mathbf U_2\mathbf U_2^T.$$

而且

$$\mathbf P_{\mathbf U_1}+\mathbf P_{\mathbf U_2}=\mathbf I_n,$$

所以这两个子空间互为正交补（orthogonal complement）。

这里可以把 $\mathbf U_1\mathbf U_1^T\mathbf x$ 理解成：先用 $\mathbf U_1^T\mathbf x$ 取出 $\mathbf x$ 在各个正交基方向上的系数，再用 $\mathbf U_1$ 把这些系数重组成子空间里的投影向量。若基底不是正交的，一般投影矩阵应写成 $\mathbf A(\mathbf A^T\mathbf A)^{-1}\mathbf A^T$。

Weyl 定理：特征值是稳定的

设

$$\tilde{\mathbf M} = \mathbf M+\mathbf \Delta = \tilde{\mathbf U}\tilde{\mathbf \Lambda}\tilde{\mathbf U}^T = \begin{bmatrix} \tilde{\mathbf U}_1 & \tilde{\mathbf U}_2 \end{bmatrix} \begin{bmatrix} \tilde{\mathbf \Lambda}_1 & \mathbf 0 \\ \mathbf 0 & \tilde{\mathbf \Lambda}_2 \end{bmatrix} \begin{bmatrix} \tilde{\mathbf U}_1^T \\ \tilde{\mathbf U}_2^T \end{bmatrix}.$$

Weyl 定理（Weyl theorem）告诉我们：

$$\|\tilde{\mathbf \Lambda}-\mathbf \Lambda\|_2 \le \|\mathbf \Delta\|_2.$$

这表示特征值的整体漂移（spectral shift）至多和扰动的谱范数（spectral norm）同一个量级。也就是说，只要 $\|\mathbf \Delta\|_2$ 小，特征值通常不会跑太远。

为什么要比较子空间，而不是直接比较特征向量

和特征值不同，特征向量可能非常不稳定。尤其当特征值彼此很接近时，哪怕扰动很小，特征向量也可能发生明显旋转（rotation）。

因此，直接比较

$$\|\tilde{\mathbf U}_1-\mathbf U_1\|_F$$

往往不是最好的做法，因为这个量会把“同一个子空间内部仅仅换了一组基底”也当成差异。

更合理的对象是：

• $\mathbf U_1$ 张成的子空间；
• $\tilde{\mathbf U}_1$ 张成的子空间。

也就是说，真正该比较的是子空间距离（subspace distance）。

主角（principal angles）与子空间距离

设 $\mathbf A,\mathbf B\in\mathbb R^{n\times r}$ 都有正交列，分别张成子空间 $\mathcal A,\mathcal B$。主角（principal angles）$\theta_1,\dots,\theta_r$ 定义为：$\cos\theta_1,\dots,\cos\theta_r$ 正好是 $\mathbf A^T\mathbf B$ 的奇异值（singular values）。

等价地，

$$\mathbf A^T\mathbf B = \mathbf U\,\operatorname{diag}(\cos\theta_1,\dots,\cos\theta_r)\,\mathbf V^T = \mathbf U\cos\mathbf \Theta\,\mathbf V^T,$$

其中 $\mathbf \Theta=\operatorname{diag}(\theta_1,\dots,\theta_r)$。

若 $\bar{\mathbf B}$ 表示 $\mathbf B$ 的正交补基底，即

$$\mathbf B\mathbf B^T+\bar{\mathbf B}\bar{\mathbf B}^T=\mathbf I_n,$$

则可以推出

$$\mathbf A^T\bar{\mathbf B} = \mathbf U\sin\mathbf \Theta\,\bar{\mathbf V}^T$$

对某个半正交矩阵 $\bar{\mathbf V}$ 成立。

于是，子空间距离可以定义为

$$d(\mathcal A,\mathcal B) := \|\sin\mathbf \Theta\|_F = \frac{1}{\sqrt 2}\|\mathbf P_{\mathbf A}-\mathbf P_{\mathbf B}\|_F = \|\mathbf A^T\bar{\mathbf B}\|_F.$$

这个定义很重要，因为它把“夹角大小”“投影矩阵差异”“正交补上的泄漏量”三件事统一了起来。

若 $r=1$，主角就退化成两个向量之间的普通夹角；若 $r>1$，它描述的是两个子空间整体之间的相对位置，而不是某一个特征向量的逐点差。

正交 Procrustes 问题

如果我们允许对基底做一个最优旋转（optimal rotation），就会得到正交 Procrustes 问题（orthogonal Procrustes problem）：

$$\min_{\mathbf R\in\mathbb R^{r\times r}:\ \mathbf R^T\mathbf R=\mathbf I_r} \|\mathbf A\mathbf R-\mathbf B\|_F^2.$$

令

$$\mathbf C=\mathbf A^T\mathbf B=\mathbf U\cos\mathbf \Theta\,\mathbf V^T,$$

则最优解为

$$\hat{\mathbf R} = \mathbf U\mathbf V^T = \mathbf C(\mathbf C^T\mathbf C)^{-1/2}.$$

此时

$$\|\mathbf A\hat{\mathbf R}-\mathbf B\|_F^2 = 2r-2\sum_{i=1}^r\cos\theta_i = 4\sum_{i=1}^r\sin^2\frac{\theta_i}{2} \le 2\sum_{i=1}^r\sin^2\theta_i = 2\,d^2(\mathcal A,\mathcal B).$$

这说明：如果先允许基底做最优旋转，那么“基底矩阵的差”其实可以被子空间距离控制住。

Davis-Kahan 正弦定理

现在回到扰动问题。我们希望控制

$$\sin\mathbf \Theta(\tilde{\mathbf U}_1,\mathbf U_1) = \|\tilde{\mathbf U}_2^T\mathbf U_1\|_F.$$

注意

$$\tilde{\mathbf U}_2^T\mathbf \Delta\mathbf U_1 = \tilde{\mathbf U}_2^T(\tilde{\mathbf M}-\mathbf M)\mathbf U_1 = \tilde{\mathbf \Lambda}_2\tilde{\mathbf U}_2^T\mathbf U_1 - \tilde{\mathbf U}_2^T\mathbf U_1\mathbf \Lambda_1.$$

若记

$$\mathbf H=\tilde{\mathbf U}_2^T\mathbf U_1,$$

则上式可写成

$$\tilde{\mathbf U}_2^T\mathbf \Delta\mathbf U_1 = \tilde{\mathbf \Lambda}_2\mathbf H-\mathbf H\mathbf \Lambda_1.$$

进一步可得

$$\|\tilde{\mathbf U}_2^T\mathbf \Delta\mathbf U_1\|_F \ge \delta\,\|\mathbf H\|_F,$$

其中 eigengap 定义为

$$\delta := \min_{1\le i\le r,\ r+1\le j\le n} |\lambda_i-\tilde{\lambda}_j|.$$

于是得到 Davis-Kahan 定理（Davis-Kahan theorem）：

$$\|\sin\mathbf \Theta(\tilde{\mathbf U}_1,\mathbf U_1)\|_F \le \frac{\|\mathbf \Delta\mathbf U_1\|_F}{\delta}.$$

这条不等式最值得记住的地方是：

• 分子是扰动大小；
• 分母是谱分离（eigengap）。

所以 eigengap 越小，子空间就越不稳定；eigengap 越大，特征子空间就越稳。

一个常用的充分条件（sufficient but not necessary condition）是

$$0<\|\mathbf \Delta\|_2 < \min_{1\le i\le r,\ r+1\le j\le n} |\lambda_i-\lambda_j|.$$

这个条件的意思是：原矩阵两块谱之间本来就分得开，而且扰动还没有大到把它们“挤穿”。

Wedin 定理：非对称情形的推广

当矩阵不再对称时，更自然的对象是奇异值分解（singular value decomposition, SVD）。

设

$$\mathbf M = \begin{bmatrix} \mathbf U_1 & \mathbf U_2 \end{bmatrix} \begin{bmatrix} \mathbf \Sigma_1 & \mathbf 0 \\ \mathbf 0 & \mathbf \Sigma_2 \end{bmatrix} \begin{bmatrix} \mathbf V_1^T \\ \mathbf V_2^T \end{bmatrix},$$

以及

$$\tilde{\mathbf M} = \mathbf M+\mathbf \Delta = \begin{bmatrix} \tilde{\mathbf U}_1 & \tilde{\mathbf U}_2 \end{bmatrix} \begin{bmatrix} \tilde{\mathbf \Sigma}_1 & \mathbf 0 \\ \mathbf 0 & \tilde{\mathbf \Sigma}_2 \end{bmatrix} \begin{bmatrix} \tilde{\mathbf V}_1^T \\ \tilde{\mathbf V}_2^T \end{bmatrix}.$$

若

$$\delta = \min\left\{ \min_{1\le i\le r,\ r+1\le j\le n} |\sigma_i-\tilde{\sigma}_j|, \ \min_{1\le i\le r}\sigma_i \right\} > 0,$$

则 Wedin 定理（Wedin theorem）给出

$$\|\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 在一般矩阵上的版本：它同时控制左奇异子空间（left singular subspace）和右奇异子空间（right singular subspace）的偏移。

相应地，一个常见充分条件是

$$\sigma_r>0 \qquad\text{且}\qquad 0<\|\mathbf \Delta\|_2 < \min_{1\le i\le r,\ r+1\le j\le n} |\sigma_i-\sigma_j|.$$

一句话总结

矩阵扰动理论（matrix perturbation theory）里，一个很值得记住的结构是：

• Weyl 定理控制特征值或奇异值的漂移。
• 主角（principal angles）和投影矩阵差异用来刻画子空间偏移。
• Davis-Kahan 定理处理对称矩阵的特征子空间扰动。
• Wedin 定理处理一般矩阵的奇异子空间扰动。

真正决定特征向量或奇异向量稳不稳定的，往往不是“扰动小不小”这一件事，而是“扰动大小”和“谱间隔（spectral gap）”之间的相对关系。

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.