奇异值分解

奇异值分解

注意：我们现在只讨论实矩阵的奇异值矩阵的分解。即给定矩阵 $A \in \mathbb{R}^{m\times n}$。

1. 奇异值

定理：$A^TA$ 的特征值都是实数且非负。

证明：设 $A^TA$ 的特征值 $\lambda$，对应的特征向量 $\pmb v \not=\pmb 0$，有：

$$A^TA\pmb v = \lambda\pmb v$$ $$||A\pmb v||^2 = (A\pmb v)^T(A\pmb v) = \pmb v^TA^TA\pmb v = \lambda\pmb v^T\pmb v = \lambda||\pmb v||^2 \ge0$$

可知$||\pmb v||^2 \gt 0$，因此 $\lambda \ge 0$。得证。

当将定义拓展到复数空间时，对称矩阵属于$\text{Hermite}$ 矩阵（$A^H=A$），$\text{Hermite}$ 矩阵的特征值均为实数。

定义：令 $\lambda_1,\lambda_2,…,\lambda_n$ 是 $A^TA$ 的特征值，且 $\lambda_1\ge\lambda_2\ge…\ge\lambda_n\ge0$，$\sigma_i=\sqrt \lambda_i$，我们称 $\sigma_i$ 为矩阵 $A$ 的奇异值。

定理：矩阵 $A$ 的正奇异值的数量等于矩阵 $A$ 的秩。

定理： 若矩阵 $A$ 的秩为 $r$，那么 $r(A^TA) = r(AA^T) = r$。

定理：矩阵 $A^TA$ 与矩阵 $AA^T$的特征值相同。

2. 奇异值分解

定理：给定任意矩阵 $A_{m\times n}$，总可以分解为以下的矩阵相乘形式：

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

其中：$U_{m\times m},\Sigma_{m\times n},V_{n\times n}$，且

$$UU^T=I,VV^T=I$$ $$\Sigma=\begin{pmatrix}\Sigma^\prime&O\\O&O\end{pmatrix}$$ $$\Sigma^\prime=\text{diag}\{\sigma_1,\sigma_2,...,\sigma_r\},\sigma_1\ge\sigma_2\ge...\ge\sigma_r\gt0$$

同时我们称 $U$ 是 $A$ 的左奇异向量，$V$ 是 $A$ 的右奇异向量。

详细证明过程可以参见《统计学习方法》（第二版）。

3. 性质

因为 $A = U\Sigma V^T,A^T = V\Sigma^TU^T$，所以：

$$AA^T =U\Sigma V^TV\Sigma^TU^T = U(\Sigma \Sigma ^T)U^T$$ $$A^TA = V\Sigma^TU^TU\Sigma V^T = V(\Sigma^T\Sigma)V^T$$

由以上可得：

• 正交矩阵 $V$ 是 $A^TA$ 的特征向量组成的矩阵
• 正交矩阵 $U$ 是 $AA^T$ 的特征向量组成的矩阵
• 由 $A = U\Sigma V^T$，有：$AV = U\Sigma$，

$$\pmb u_i = \frac{1}{\sigma_i}A\pmb v_i,i=1,2,...,r$$

​ $\pmb u_{r+1},\pmb u_{r+2},…,\pmb u_m$ 是矩阵 $A^T$ 零空间 $N(A^T)$ 的一组标准正交基。

• 由 $A = U\Sigma V^T$，有：$U^TA = \Sigma V^T$，进而：$A^TU = V\Sigma^T$。

$$\pmb v_i = \frac{1}{\sigma_i}A^T\pmb u_i,i=1,2,...,r$$

​ $\pmb v_{r+1},\pmb v_{r+2},…,\pmb v_n$ 是矩阵 $A$ 零空间 $N(A)$ 的一组标准正交基。

4. 计算

计算如下矩阵的奇异值分解。

$$A = \begin{pmatrix}1&2&0\\2&0&2\end{pmatrix}$$

可知：

$$A^T=\begin{pmatrix}1&2\\2&0\\0&2\end{pmatrix}$$

为了计算方便，计算 $AA^T$的特征值，即先求出 $U$，再计算 $V$。

$$AA^T=\begin{pmatrix}5&2\\2&8\end{pmatrix}$$ $$|\lambda I-A| = \left |\begin {matrix}\lambda-5&-2\\-2&\lambda - 8 \end{matrix} \right |$$

特征方程：

$$(\lambda-5)(\lambda-8)-4=(\lambda-4)(\lambda-9)=0$$

可知两个特征值分别为 $\lambda_1=9,\lambda_2=4$，因此奇异值 $\sigma_1 = \sqrt 9=3,\sigma_2=\sqrt 4=2$，所以

$$\Sigma = \begin{pmatrix}3&0&0\\0&2&0\end{pmatrix}$$

计算 $\lambda_1=9$ 对应的特征向量：

$$\begin{pmatrix}4&-2\\-2&1\end{pmatrix}\pmb x = \pmb 0$$

解得：$\pmb x = (1,2)^T$。单位化后可得：$\pmb u_1=(1/\sqrt5,2/\sqrt5)^T$

计算 $\lambda_2 = 4$ 对应的特征向量：

$$\begin{pmatrix}-1&-2\\-2&-4\end{pmatrix}\pmb x = \pmb 0$$

解得：$\pmb x = (2,-1)^T$。单位化后可得：$\pmb u_2=(2/\sqrt5,-1/\sqrt5)^T$

因此：

$$U = \begin{pmatrix}\frac{1}{\sqrt5}&\frac{2}{\sqrt5}\\ \frac{2}{\sqrt5}&-\frac{1}{\sqrt5}\end{pmatrix}$$

现在根据$\pmb v_i = \frac{1}{\sigma_i}A^T\pmb u_i,i=1,2,…,r$ 计算 $V$。

$$A^TU = \begin{pmatrix}1&2\\2&0\\0&2\end{pmatrix}\begin{pmatrix}\frac{1}{\sqrt5}&\frac{2}{\sqrt5}\\ \frac{2}{\sqrt5}&-\frac{1}{\sqrt5}\end{pmatrix} = \begin{pmatrix}\sqrt5&0\\\frac{2}{\sqrt5}&\frac{4}{\sqrt5}\\\frac{4}{\sqrt5}&-\frac{2}{\sqrt5}\end{pmatrix}$$

可得：$\pmb v_1=(\frac{\sqrt5}{3},\frac{2}{3\sqrt5},\frac{4}{3\sqrt5})^T,\pmb v_2=(0,\frac{2}{\sqrt 5},-\frac{1}{\sqrt 5})^T$

又$\pmb v_3$是$N(A)$的一组基，即：

$$A = \begin{pmatrix}1&2&0\\2&0&2\end{pmatrix}\begin{pmatrix}x_1\\x_2\\x_3\end{pmatrix} = \pmb 0$$

解得 $(-2,1,2)^T$。单位化可得 ： $\pmb v_3=(-2/3,1/3,2/3)$。因此：

$$V = \begin{pmatrix}\frac{\sqrt 5}{3}&0&-\frac{2}{3}\\\frac{2}{3\sqrt5}&\frac{2}{\sqrt 5}&\frac{1}{3}\\\frac{4}{3\sqrt5}&-\frac{1}{\sqrt5}&\frac{2}{3} \end{pmatrix}$$

综上，$A$ 的奇异值分解如下：

$$A =\begin{pmatrix}\frac{1}{\sqrt5}&\frac{2}{\sqrt5}\\ \frac{2}{\sqrt5}&-\frac{1}{\sqrt5}\end{pmatrix}\begin{pmatrix}3&0&0\\0&2&0\end{pmatrix}\begin{pmatrix}\frac{\sqrt 5}{3}&0&-\frac{2}{3}\\\frac{2}{3\sqrt5}&\frac{2}{\sqrt 5}&\frac{1}{3}\\\frac{4}{3\sqrt5}&-\frac{1}{\sqrt5}&\frac{2}{3} \end{pmatrix}^T$$

注意：$V$ 是转置过的，计算时要注意一下。

也可以计算$A^TA$的特征值与特征向量，得到矩阵 $V$，然后根据 $\pmb u_i = \frac{1}{\sigma_i}A\pmb v_i,i=1,2,…,r$ 得到矩阵 $U$。