写在前面

在大牛Yuejie Chi的主页^[1]上找到一个讲谱方法的小册子^[2]，准备系统地学习下。

子空间度量

旋转模糊

记子空间 $\mathcal{U}$ 和 ${\mathcal{U}}^{\star}$ 的正交基分别为 $\boldsymbol{U}$ 和 $\boldsymbol{U}^{\star}$ 。为了测量子空间 $\mathcal{U}$ 和 ${\mathcal{U}}^{\star}$ 的距离，一个自然的想法是构造出一个度量$\vert\vert\vert{\boldsymbol{U}-{\boldsymbol{U}}^{\star}}\vert\vert\vert$，其中$\vert\vert\vert{\cdot}\vert\vert\vert$是感兴趣的一种范式，例如谱范数或Frobenius范数。然而这样的度量通常没有考虑全局的旋转模糊，即对任意旋转矩阵$\boldsymbol{R}\in\mathcal{O}^{r\times r}$，矩阵$\boldsymbol{U}\boldsymbol{R}$的列也是子空间$\mathcal{U}$的有效正交基。这意味着下面情况可能出现：当子空间 $\mathcal{U}$ 和 ${\mathcal{U}}^{\star}$ 相同时，其距离度量不为零，即

$$\vert\vert\vert{\boldsymbol{U}-{\boldsymbol{U}^{\star}}}\vert\vert\vert \neq 0$$

这表明，测量两个子空间的接近程度的任何有意义的度量，都应适当考虑旋转模糊。

距离度量

• 最佳旋转距离

计算距离之前找到最佳旋转矩阵$\boldsymbol R$，在最佳旋转时测量距离

$$\mathsf{dist}_{\vert\vert\vert{\cdot}\vert\vert\vert}\big(\boldsymbol{U},{\boldsymbol{U}}^{\star}\big) \doteq \min _{\boldsymbol{R}\in \mathcal{O}^{r\times r}} \vert\vert\vert\boldsymbol{U} \boldsymbol{R} - \boldsymbol{U}^{\star}\vert\vert\vert$$

• 投影矩阵之间的距离

由于子空间$\mathcal{U}$的投影矩阵$\boldsymbol{U}\boldsymbol{U}^{\top}$是唯一的，且不受旋转的影响，即

$$\boldsymbol{U}\boldsymbol{U}^{\top}=\boldsymbol{U}\boldsymbol{R}\boldsymbol{R}^{\top}\boldsymbol{U}^{\top}, \forall \boldsymbol{R}\in \mathcal{O}^{r\times r}$$

这种旋转不变性可用来定义子空间 $\mathcal{U}$ 和 ${\mathcal{U}}^{\star}$ 之间的距离

$$\mathsf{dist}_{\mathsf{p},\vert\vert\vert{\cdot}\vert\vert\vert}\big(\boldsymbol{U},{\boldsymbol{U}}^{\star}\big) \doteq \vert\vert\vert\boldsymbol{U} \boldsymbol{U}^{\top}- {\boldsymbol{U}}^{\star} {\boldsymbol{U}}^{\star\top}\vert\vert\vert$$

• 通过主角进行几何构造

设矩阵$\boldsymbol{U}^{\top}{\boldsymbol{U}}^{\star}$的奇异值为$\sigma_{1}\geq \sigma_{2}\geq \cdots\geq \sigma_{r} \geq 0$，由于

$$\| \boldsymbol{U}^{\top}{\boldsymbol{U}}^{\star} \| \leq \| \boldsymbol{U} \| \, \| {\boldsymbol{U}}^{\star} \|=1$$

所有的奇异值$\{\sigma_{i}\}_{i=1}^r$在区间$[0,1]$内。因此我们可以定义两个子空间之间的主角（或规范角）

$$\theta_{i} \doteq \arccos \left(\sigma_{i}\right)\qquad\text{for all }1\leq i\leq r,$$

这些角度满足

$$0\leq\theta_{1}\leq \cdots\leq\theta_{r}\leq\pi/2.$$

有了这些角度，就可以测量子空间之间的距离

$$\mathsf{dist}_{\mathsf{sin},\vert\vert\vert{\cdot}\vert\vert\vert}\big(\boldsymbol{U},{\boldsymbol{U}}^{\star}\big) \doteq \vert\vert\vert\sin\boldsymbol{\Theta}\vert\vert\vert$$

其中$\boldsymbol{\Theta}=\text{diag}(\theta_{1},\theta_{2},\ldots,\theta_{r}),\sin\boldsymbol{\Theta}=\text{diag}(\sin\theta_{1},\sin\theta_{2},\ldots,\sin\theta_{r})$。

度量之间的关系

• 当$2r\leq n$时，矩阵$\boldsymbol{U}\boldsymbol{U}^{\top}-{\boldsymbol{U}}^{\star}{\boldsymbol{U}}^{\star\top}$的奇异值为

$$\underbrace{\sin\theta_{r},\, \sin\theta_{r},\, \sin\theta_{r-1},\, \sin\theta_{r-1},\,\cdots,\,\sin\theta_{1},\,\sin\theta_{1}}_{2r},\;\underbrace{0,\,0,\,\cdots,\,0}_{n-2r}.$$

这意味着投影矩阵的差和子空间之间的主角具有明确的联系。

• 当$1\le r \le n$时，度量$\mathsf{dist}_{\mathsf{p},\vert\vert\vert{\cdot}\vert\vert\vert}\big(\cdot,\cdot\big)$和$\mathsf{dist}_{\mathsf{sin},\vert\vert\vert{\cdot}\vert\vert\vert}\big(\cdot,\cdot\big)$具有如下等式关系

$$\begin{aligned} \big\Vert \boldsymbol{U}\boldsymbol{U}^{\top}-{\boldsymbol{U}}^{\star}{\boldsymbol{U}}^{\star\top}\big\Vert & =\left\Vert \sin\boldsymbol{\Theta}\right\Vert = \big\Vert \boldsymbol{U}_{\perp}^{\top}\boldsymbol{U}^{\star}\big\Vert = \big\Vert \boldsymbol{U}^{\top}\boldsymbol{U}_{\perp}^{\star}\big\Vert\\ \tfrac{1}{\sqrt{2}} \big\Vert \boldsymbol{U}\boldsymbol{U}^{\top}-{\boldsymbol{U}}^{\star}{\boldsymbol{U}}^{\star\top}\big\Vert _{\mathrm{F}} & =\left\Vert \sin\boldsymbol{\Theta}\right\Vert _{\mathrm{F}} = \big\Vert \boldsymbol{U}_{\perp}^{\top}\boldsymbol{U}^{\star}\big\Vert_{\mathrm{F}} = \big\Vert \boldsymbol{U}^{\top}\boldsymbol{U}_{\perp}^{\star} \big\Vert_{\mathrm{F}} \end{aligned}$$

• 当$1\le r \le n$时，度量$\mathsf{dist}_{\vert\vert\vert{\cdot}\vert\vert\vert}\big(\cdot,\cdot\big)$和$\mathsf{dist}_{\mathsf{p},\vert\vert\vert{\cdot}\vert\vert\vert}\big(\cdot,\cdot\big)$具有如下不等式关系

$$\begin{aligned} \|\boldsymbol{U}\boldsymbol{U}^{\top} - \boldsymbol{U}^{\star}\boldsymbol{U}^{\star\top} \| &\leq \min_{\boldsymbol{R}\in \mathcal{O}^{r\times r}}\big\|\boldsymbol{U}\boldsymbol{R}-\boldsymbol{U}^{\star}\big\| \leq \sqrt{2} \|\boldsymbol{U}\boldsymbol{U}^{\top} - \boldsymbol{U}^{\star}\boldsymbol{U}^{\star\top} \| \\ \tfrac{1}{\sqrt{2}} \|\boldsymbol{U}\boldsymbol{U}^{\top} - \boldsymbol{U}^{\star}\boldsymbol{U}^{\star\top} \|_{\mathrm{F}} &\leq \min_{\boldsymbol{R}\in\mathcal{O}^{r\times r}}\left\Vert \boldsymbol{U}\boldsymbol{R}-\boldsymbol{U}^{\star}\right\Vert _{\mathrm{F}} \leq \|\boldsymbol{U}\boldsymbol{U}^{\top} - \boldsymbol{U}^{\star}\boldsymbol{U}^{\star\top} \|_{\mathrm{F}} \end{aligned}$$

特征子空间的扰动分析

设$n\times n$的实对称矩阵$\boldsymbol{M}^{\star}$ 和$\boldsymbol{M}=\boldsymbol{M}^{\star}+\boldsymbol{E}$ ，对其进行特征分解

$$\begin{aligned} \boldsymbol{M}^{\star} &=\sum_{i=1}^{n}\lambda_{i}^{\star}\boldsymbol{u}_{i}^{\star}\boldsymbol{u}_{i}^{\star\top} =\left[\begin{array}{cc} \boldsymbol{U}^{\star} & \boldsymbol{U}_{\perp}^{\star}\end{array}\right]\left[\begin{array}{cc} \boldsymbol{\Lambda}^{\star} & \boldsymbol{0}\\ \boldsymbol{0} & \boldsymbol{\Lambda}_{\perp}^{\star} \end{array}\right]\left[\begin{array}{c} \boldsymbol{U}^{\star\top}\\ \boldsymbol{U}_{\perp}^{\star\top} \end{array}\right]\\ \boldsymbol{M} &=\sum_{i=1}^{n}\lambda_{i}\boldsymbol{u}_{i}\boldsymbol{u}_{i}^{\top} =\left[\begin{array}{cc} \boldsymbol{U} & \boldsymbol{U}_{\perp}\end{array}\right]\left[\begin{array}{cc} \boldsymbol{\Lambda} & \boldsymbol{0}\\ \boldsymbol{0} & \boldsymbol{\Lambda}_{\perp} \end{array}\right]\left[\begin{array}{c} \boldsymbol{U}^{\top}\\ \boldsymbol{U}_{\perp}^{\top} \end{array}\right] \end{aligned}$$

其中分块矩阵按秩$r$来选择。

$$\begin{aligned} \boldsymbol{U} &=[\boldsymbol{u}_{1},\cdots,\boldsymbol{u}_{r}]\in\mathbb{R}^{n\times r}, \\ \boldsymbol{U}_{\perp} &=[\boldsymbol{u}_{r+1},\cdots,\boldsymbol{u}_{n}]\in\mathbb{R}^{n\times (n-r)},\\ \boldsymbol{\Lambda}&=\text{diag}\big([\lambda_{1},\cdots,\lambda_{r}]\big),\\ \boldsymbol{\Lambda}_{\perp} &=\text{diag}\big([\lambda_{r+1},\cdots,\lambda_{n}]\big). \end{aligned}$$

矩阵 $\boldsymbol{U}^{\star}, \boldsymbol{U}_{\perp}^{\star}, \boldsymbol{\Lambda}^{\star}, \boldsymbol{\Lambda}_{\perp}^{\star}$ 的定义类似。

Davis-Kahan $\sin\Theta$定理

对常数$\alpha,\beta\in \mathbb{R}$，eigengap$\Delta>0$，假设下面条件成立

$$\begin{aligned} \mathsf{eigenvalues}(\boldsymbol{\Lambda}^{\star}) &\subseteq [\alpha,\beta] ,\\ \mathsf{eigenvalues}(\boldsymbol{\Lambda}_{\perp}) &\subseteq (-\infty, \alpha-\Delta] \cup [\beta+\Delta, \infty) \end{aligned}$$

则

$$\begin{aligned} \mathsf{dist}\big(\boldsymbol{U},\boldsymbol{U}^{\star}\big) & \leq\sqrt{2}\|\sin\boldsymbol{\Theta}\|\leq\frac{\sqrt{2}\big\|\boldsymbol{E}\boldsymbol{U}^{\star}\big\|}{\Delta}\leq\frac{\sqrt{2}\|\boldsymbol{E}\|}{\Delta};\\ \mathsf{dist}_{\mathrm{F}}\big(\boldsymbol{U},\boldsymbol{U}^{\star}\big) & \leq\sqrt{2}\|\sin\boldsymbol{\Theta}\|_{\mathrm{F}}\leq\frac{\sqrt{2}\big\|\boldsymbol{E}\boldsymbol{U}^{\star}\big\|_{\mathrm{F}}}{\Delta}\leq\frac{\sqrt{2r}\|\boldsymbol{E}\|}{\Delta}. \end{aligned}$$

当条件替换如下时，定理仍然成立

$$\begin{aligned} \mathsf{eigenvalues}(\boldsymbol{\Lambda}^{\star}) &\subseteq (-\infty, \alpha-\Delta] \cup [\beta+\Delta, \infty) ; \\ \mathsf{eigenvalues}(\boldsymbol{\Lambda}_{\perp}) &\subseteq [\alpha,\beta]. \end{aligned}$$

在如下意义下，该定理可被推广至酉不变范数$\vert\vert\vert{\cdot}\vert\vert\vert$

$$\vert\vert\vert\sin\boldsymbol{\Theta}\vert\vert\vert \leq\frac{\vert\vert\vert\boldsymbol{E}\boldsymbol{U}^\star\vert\vert\vert}{\Delta}$$

如果$\|\boldsymbol{E}\|< (1-1/\sqrt{2}) (|\lambda_{r}^{\star}|-|\lambda_{r+1}^{\star}|)$，有

$$\begin{aligned} \mathsf{dist}\big(\boldsymbol{U},\boldsymbol{U}^{\star}\big) & \leq\sqrt{2}\|\sin\boldsymbol{\Theta}\|\leq\frac{2 \big\|\boldsymbol{E}\boldsymbol{U}^{\star}\big\|}{|\lambda_{r}^{\star}|-|\lambda_{r+1}^{\star}|}\leq\frac{2\|\boldsymbol{E}\|}{|\lambda_{r}^{\star}|-|\lambda_{r+1}^{\star}|};\\ \mathsf{dist}_{\mathrm{F}}\big(\boldsymbol{U},\boldsymbol{U}^{\star}\big) & \leq\sqrt{2}\|\sin\boldsymbol{\Theta}\|_{\mathrm{F}}\leq\frac{2 \big\|\boldsymbol{E}\boldsymbol{U}^{\star}\big\|_{\mathrm{F}}}{|\lambda_{r}^{\star}|-|\lambda_{r+1}^{\star}|}\leq\frac{2\sqrt{r}\|\boldsymbol{E}\|}{|\lambda_{r}^{\star}|-|\lambda_{r+1}^{\star}|}. \end{aligned}$$

奇异子空间的扰动分析

现在不再限制矩阵的对称性和方阵结构，考虑一般的矩阵$\boldsymbol{M}=\boldsymbol{M}^{\star}+\boldsymbol{E}\in\mathbb{R}^{n_1 \times n_2}$，不妨设$n_1\leq n_2$，对矩阵进行奇异值分解

$$\begin{aligned} \boldsymbol{M}^{\star} & =\sum_{i=1}^{n_1}\sigma_{i}^{\star}\boldsymbol{u}_{i}^{\star}\boldsymbol{v}_{i}^{\star\top} =\left[\begin{array}{cc} \boldsymbol{U}^{\star} & \boldsymbol{U}_{\perp}^{\star}\end{array}\right]\left[\begin{array}{ccc} \boldsymbol{\Sigma}^{\star} & \boldsymbol{0} & \boldsymbol{0}\\ \boldsymbol{0} & \boldsymbol{\Sigma}_{\perp}^{\star} & \boldsymbol{0} \end{array}\right]\left[\begin{array}{c} \boldsymbol{V}^{\star\top}\\ \boldsymbol{V}_{\perp}^{\star\top} \end{array}\right]\\ \boldsymbol{M} & =\sum_{i=1}^{n_1}\sigma_{i}\boldsymbol{u}_{i}\boldsymbol{v}_{i}^{\top} =\left[\begin{array}{cc} \boldsymbol{U} & \boldsymbol{U}_{\perp}\end{array}\right]\left[\begin{array}{ccc} \boldsymbol{\Sigma} & \boldsymbol{0} & \boldsymbol{0}\\ \boldsymbol{0} & \boldsymbol{\Sigma}_{\perp} & \boldsymbol{0} \end{array}\right]\left[\begin{array}{c} \boldsymbol{V}^{\top}\\ \boldsymbol{V}_{\perp}^{\top} \end{array}\right] \end{aligned}$$

其中分块矩阵按秩$r$来选择。

$$\begin{aligned} \boldsymbol{\Sigma} &=\mathsf{diag}\big([\sigma_{1},\cdots,\sigma_{r}]\big),\\ \boldsymbol{\Sigma}_{\perp} &=\mathsf{diag}\big([\sigma_{r+1},\cdots,\sigma_{n_1}]\big),\\ \boldsymbol{U} &=[\boldsymbol{u}_{1},\cdots,\boldsymbol{u}_{r}]\in \mathbb{R}^{n_1\times r},\\ \boldsymbol{U}_{\perp} &=[\boldsymbol{u}_{r+1},\cdots,\boldsymbol{u}_{n_1}]\in \mathbb{R}^{n_1\times (n_1-r)},\\ \boldsymbol{V} &=[\boldsymbol{v}_{1},\cdots,\boldsymbol{v}_{r}]\in \mathbb{R}^{n_2\times r},\\ \boldsymbol{V}_{\perp} &=[\boldsymbol{v}_{r+1},\cdots,\boldsymbol{v}_{n_2}] \in \mathbb{R}^{n_2\times (n_2-r)}. \end{aligned}$$

矩阵$\boldsymbol{\Sigma}^{\star},\boldsymbol{\Sigma}_{\perp}^{\star},\boldsymbol{U}^{\star},\boldsymbol{U}_{\perp}^{\star},\boldsymbol{V}^{\star},\boldsymbol{V}_{\perp}^{\star}$的定义类似。

Wedin's $\sin\Theta$定理

如果$\|\boldsymbol{E}\|<\sigma_{r}^{\star}-\sigma_{r+1}^{\star}$，则

$$\begin{aligned} \max\left\{ \mathsf{dist}\big(\boldsymbol{U},\boldsymbol{U}^{\star}\big),\mathsf{dist}\big(\boldsymbol{V},\boldsymbol{V}^{\star}\big)\right\} & \leq\frac{ \sqrt{2} \max\big\{ \|\boldsymbol{E}^{\top}\boldsymbol{U}^{\star}\|,\|\boldsymbol{E}\boldsymbol{V}^{\star}\|\big\} }{\sigma_{r}^{\star}-\sigma_{r+1}^{\star}-\|\boldsymbol{E}\|};\\ \max\left\{ \mathsf{dist}_{\mathrm{F}}\big(\boldsymbol{U},\boldsymbol{U}^{\star}\big),\mathsf{dist}_{\mathrm{F}}\big(\boldsymbol{V},\boldsymbol{V}^{\star}\big)\right\} & \leq\frac{\sqrt{2}\max\big\{ \|\boldsymbol{E}^{\top}\boldsymbol{U}^{\star}\|_{\mathrm{F}},\|\boldsymbol{E}\boldsymbol{V}^{\star}\|_{\mathrm{F}}\big\} }{\sigma_{r}^{\star}-\sigma_{r+1}^{\star}-\|\boldsymbol{E}\|}. \end{aligned}$$

进一步，如果$\|\boldsymbol{E}\|< (1-1/\sqrt{2})(\sigma_{r}^{\star}-\sigma_{r+1}^{\star})$，有

$$\begin{aligned} \max\left\{ \mathsf{dist}\big(\boldsymbol{U},\boldsymbol{U}^{\star}\big),\mathsf{dist}\big(\boldsymbol{V},\boldsymbol{V}^{\star}\big)\right\} & \leq\frac{ 2 \|\boldsymbol{E}\| }{\sigma_{r}^{\star}-\sigma_{r+1}^{\star}}, \\ \max\left\{ \mathsf{dist}_{\mathrm{F}}\big(\boldsymbol{U},\boldsymbol{U}^{\star}\big),\mathsf{dist}_{\mathrm{F}}\big(\boldsymbol{V},\boldsymbol{V}^{\star}\big)\right\} & \leq \frac{ 2\sqrt{r}\|\boldsymbol{E}\| }{\sigma_{r}^{\star}-\sigma_{r+1}^{\star}}, \end{aligned}$$

小结

后面还有一系列扰动理论及其应用，有时间再看，先接触下。

References

---

1. Yuejie Chi homepage: http://users.ece.cmu.edu/~yuejiec/index.html (opens new window) ↩︎

2. Y. Chen, Y. Chi, J. Fan, and C. Ma. Spectral Methods for Data Science: A Statistical Perspective (opens new window). Foundation and Trends in Machine Learning, arXiv:2012.08496v1 (opens new window), 2020. ↩︎