18.065 Lecture 6

课程主页：https://ocw.mit.edu/courses/mathematics/18-065-matrix-methods-in-data-analysis-signal-processing-and-machine-learning-spring-2018/index.htm

这一讲的主题是Singular Value Decomposition (SVD)。

基本概念和性质

对于$A\in \mathbb R^{m\times n}$，奇异值分解的形式为

$$A=U\Sigma V^T$$

其中

$$\begin{aligned} U&\in \mathbb R^{m\times m},U^TU=UU^T=I_m\\ \Sigma &= \left[ \begin{matrix} \sigma_1 && & \\ & \ddots && \\ &&\sigma_r& \\ &&&0 \end{matrix} \right] \in \mathbb R^{m\times n},\sigma_1 \ge \ldots \ge \sigma_r\\ V&\in \mathbb R^{n\times n},V^TV=VV^T=I_n \end{aligned}$$

由上述分解可得

$$\begin{aligned} AV&=U\Sigma \\ A^TU&= V\Sigma^T \end{aligned}$$

即

$$\begin{aligned} Av_i &=\begin{cases} \sigma_i u_i & 1\le i\le r\\ 0 & r+1\le i \end{cases}\\ A^Tu_i& =\begin{cases} \sigma_i v_i & 1\le i\le r\\ 0 & r+1\le i \end{cases} \end{aligned}$$

另一方面，我们有

$$\begin{aligned} A^TA&=V\Sigma^T U^T U\Sigma V^T\\ &= V(\Sigma^T\Sigma) V^T\\ AA^T&= U\Sigma V^TV\Sigma^T U^T \\ &=U(\Sigma\Sigma^T) U^T \end{aligned}$$

所以不难看出$v_i$为$A^TA$的特征向量，$u_i$为$AA^T$的特征向量。

证明

由半正定对称矩阵的正交分解可得

$$\begin{eqnarray*} A^T A&&=V\Lambda_1 V^T \in \mathbb R^{n\times n} \tag1\\ AA^T&&= U\Lambda_2 U^T \in \mathbb R^{m\times m}\tag 2 \end{eqnarray*}$$

其中

$$\begin{aligned} V&= \left[ \begin{matrix} v_1 & \ldots & v_n \end{matrix} \right] \\ U&= \left[ \begin{matrix} u_1 & \ldots & u_m \end{matrix} \right]\\ \Lambda_1 &= \text{diag}(\lambda_{11},\ldots ,\lambda_{1r},0,\ldots,0), \lambda_{11} \ge \ldots \ge \lambda_{11}>0\\ \Lambda_2 &= \text{diag}(\lambda_{21},\ldots ,\lambda_{2r},0,\ldots,0) ,\lambda_{21} \ge \ldots \ge \lambda_{2r}>0\\ r&=\text{rank}(AA^T)=\text{rank}(A^TA)=\text{rank}(A) \end{aligned}$$

下面先证明$\Lambda_1 ,\Lambda_2$的正对角元相同：

由(1)可得

$$A^TAv_i=\begin{cases} \lambda_{1i} v_i & i=1,\ldots ,r\\ 0 & i\ge r+1 \end{cases}$$

左乘$A$得到

$$AA^T(Av_i) =\lambda_{1i} (Av_i)$$

所以$\lambda_{1i}$是$AA^T$的特征值，对应的特征向量为$Av_i$；同理可得$\lambda_{2i}$是$A^TA$的特征值，对应的特征向量为$A u_i$。因此$\Lambda_1 ,\Lambda_2$的正对角元相同，不妨记为

$$\sigma_1^2\ge \ldots \ge \sigma_r^2$$

注意到由之前讨论可得

$$\{u_1,\ldots, u_r \}$$

以及

$$\{Av_1,\ldots ,Av_r \}$$

都是$AA^T $的非零特征值对应的特征向量，所以我们有

$$Av_i =k_i u_{a_i}, i=1,\ldots ,r$$

取模可得

$$\begin{aligned} \| Av_i\| & = \| k_iu_{a_i}\|\\ \| Av_i\|^2 & = \| k_iu_{a_i}\|^2\\ v_i^TA^TAv_i &= k_i ^2 u_{a_i}^Tu_{a_i}\\ \sigma_i^2 v_i^T v_i &= k_i^2u_{a_i}^Tu_{a_i}\\ k_i^2 & =\sigma_i^2 \end{aligned}$$

所以可以取

$$k_i=\sigma_i$$

因此

$$\begin{aligned} Av_i =\sigma_i u_{a_i}&& i=1,\ldots ,r \end{aligned}$$

另一方面，由之前讨论可得

$$\begin{aligned} Av_i =0&&i\ge r+1 \end{aligned}$$

记

$$\Sigma = \left[ \begin{matrix}\sigma_1 && & \\ & \ddots && \\ &&\sigma_r& \\ &&&0 \end{matrix} \right]$$

将$U$重新记为

$$U=\left[ \begin{matrix} u_{a_1} & \ldots & u_{a_m} \end{matrix} \right]$$

那么将上述结论写成矩阵形式可得

$$\begin{aligned} AV&=U\Sigma \\ A&=U\Sigma V^T \end{aligned}$$

因此得到奇异值分解。

理解

奇异值分解告诉我们每个线性变换$A$可以表达为正交变换$V^T$，伸缩变换$\Sigma$和正交变换$U$的复合。

习题

1

由$S$为对称矩阵可得

$$S=V\Lambda V^T$$

其中

$$\begin{aligned} V&=\left[ \begin{matrix} v_1 & \ldots & v_n \end{matrix} \right]\\ \Lambda &= \text{diag} (\lambda_1,\ldots,\lambda_n) \end{aligned}$$

记

$$c= \left[ \begin{matrix} c_1 \\ \vdots \\ c_n \end{matrix} \right]$$

那么

$$x=Vc$$

首先有

$$\begin{aligned} x^T x &=c^TV^TVc\\ &=c^Tc\\ &= \sum_{i=1}^n c_i^2\\ x^TSx &=c^TV^TV\Lambda V^TVc\\ &=c^T\Lambda c\\ &=\sum_{i=1}^n \lambda_i c_i^2 \end{aligned}$$

6

因为

$$A=\left[ \begin{array}{ll}{3} & {4} \\ {0} & {5}\end{array}\right]$$

所以

$$\begin{aligned} A^TA&=\left[ \begin{array}{ll} {3} & {0}\\ {4} & {5} \end{array}\right] \left[ \begin{array}{ll} {3} & {4} \\ {0} & {5} \end{array}\right]\\ &= \left[ \begin{array}{ll} 9 & 12 \\ 12 & 41 \end{array}\right]\\ AA^T &= \left[ \begin{array}{ll} {3} & {4} \\ {0} & {5} \end{array}\right] \left[ \begin{array}{ll} {3} & {0}\\ {4} & {5} \end{array}\right]\\ &=\left[ \begin{array}{ll} 25 & {20}\\ {20} & {25} \end{array}\right] \end{aligned}$$

求解

$$\det(\lambda I_2 -AA^T) =0$$

得到

$$(\lambda - 25)^2 = 20^2\\ \lambda_1 =45,\lambda_2=5$$

因此

$$\sigma_1 =3\sqrt 5,\sigma_2 =\sqrt 5$$

求$AA^T$的特征向量得到

$$\begin{aligned} u_1 &= \left[ \begin{matrix} \frac 1 {\sqrt 2 }\\ \frac 1 {\sqrt 2 } \end{matrix} \right] \\ u_2 &= \left[ \begin{matrix} \frac 1 {\sqrt 2 }\\ -\frac 1 {\sqrt 2 } \end{matrix} \right] \end{aligned}$$

所以

$$\begin{aligned} v_1 &= \frac{A^Tu_1}{\sigma_1} \\ &=\frac{\left[ \begin{array}{ll} {3} & {0}\\ {4} & {5} \end{array}\right]\left[ \begin{matrix} \frac 1 {\sqrt 2 }\\ \frac 1 {\sqrt 2 } \end{matrix} \right]}{3\sqrt 5}\\ &= \frac{\left[ \begin{matrix} \frac 3 {\sqrt 2 }\\ \frac 9 {\sqrt 2 } \end{matrix} \right]}{3\sqrt 5}\\ &=\left[ \begin{matrix} \frac 1 {\sqrt {10} }\\ \frac 3{\sqrt {10} } \end{matrix} \right]\\ v_2 &= \frac{A^Tu_2}{\sigma_2} \\ &=\frac{\left[ \begin{array}{ll} {3} & {0}\\ {4} & {5} \end{array}\right]\left[ \begin{matrix} \frac 1 {\sqrt 2 }\\ -\frac 1 {\sqrt 2 } \end{matrix} \right]}{\sqrt 5}\\ &= \frac{\left[ \begin{matrix} \frac 3 {\sqrt 2 }\\ -\frac 1 {\sqrt 2 } \end{matrix} \right]}{\sqrt 5}\\ &=\left[ \begin{matrix} \frac 3 {\sqrt {10} }\\ -\frac 1{\sqrt {10} } \end{matrix} \right] \end{aligned}$$