SVD — 奇异向量分解

SVD, 奇异向量分解 (Singular Vector Decomposition). 对于 $\forall A$ ($A$ 不一定是方阵)，都可以写成： $AV = U\Sigma$。 即：

$$\begin{aligned} A = U \Sigma V^T = \vec{u_1}\sigma_1\vec{v_1}^T + \vec{u_2}\sigma_2\vec{v_2}^T + ... + \vec{u_n}\sigma_n\vec{v_n}^T \end{aligned}$$

其中：

• U, V 是正定矩阵，即 $V^{T} = V^{-1}$, $U^{T} = U^{-1}$.
• ${\sigma_i}^2 = \lambda_i$, $\lambda_i$ 是 $AA^T$ 的特征值，当然也是 $A^TA$ 的特征值。$\sigma_1 \sigma_2 ... \sigma_k$ 的排列顺序是按特征值的大小降序排列的。
• $u_i$ 是 $AA^T$ 的特征向量，是 A 列子空间上的向量。
• $v_i$ 是 $A^TA$ 的特征向量，是 A 行子空间上的向量。

要求 A 是非方阵，而组成 $A^TA, AA^T$ 对称矩阵。

对称矩阵

为什么要是对称矩阵那？因为对称矩阵有以下性质：

1. 对称矩阵的特征值都是实数，即：$\forall \lambda_i \in R$.
2. 若特征值 $\lambda_i \ne \lambda_j$, 则分别对应的特征向量是正交的。
3. 其特征值组成的特征向量矩阵 Q 是正交的，即 $Q^T = Q^{-1}$

根据上面的两个性质，则可以证明对称矩阵一定可以对角化。

为什么要对角化？

对角化需要矩阵是方阵。当方阵矩阵 A 有 n 个不相关的特征向量时 $\vec{x_1}, \vec{x_2}, ...\vec{ x_n}$ 组成 S , 则有

$$S^{-1} A S = \Lambda = \begin{bmatrix} \lambda_{1} & & \\ & \ddots & \\ & & \lambda_{n} \end{bmatrix}$$

• S 是特性向量矩阵。
• $\Lambda$ 是特征值矩阵。

使用对角化的矩阵可以来计算矩阵的变化率，和观察矩阵的状态。因为 $A^k = S \Lambda^{k} S^{-1}$, 利用这个式子我们可以计算如 Fibonacci 数列， Markov 矩阵等。

• Fibonacii 数列的增长率就是 [1 1; 1 0] 矩阵的特征值，约等于 1.618
• Markov 矩阵为 1 的特征值对就的特征向量是稳态特征向量 (steady state), 多次增长后所以列都会趋向于这稳定状态。

关于特征值和特征向量

特征向量是最能表示出矩阵特征的向量。

向量 $\vec{x}$ 乘上A 不会改变向量的方向，就是 A 的特征向量。即 $A\vec{x} = \lambda\vec{x}$ 。 基中上 $\lambda$ 是特征值，$\vec{x}$ 是特征向量。

对于特征值和特征向量的求解方法是：

1. 求解 $(A - \lambda I) = 0$ 求出特征值。
2. 求解 $(A - \lambda I) \vec{x} = 0$ 求出特征向量。

下面特征值的两个性质可以作为验证所示的特征值是否正确。

1. 和等于迹 $\sum_{i = 1}^{i = n} \lambda_i = trace(A)$
2. 积等于行列式的值 $\prod_{i = 1}^{i = n} \lambda_i = det(A)$

两个定义：

1. 当 $\forall \lambda > 0$ 时，A 称为正定矩阵。
2. 当 $\forall \lambda \geq 0$ 时，A 称为半正定矩阵。

LU 分解

顺便回顾下 LU 分解 (LU Decomposition, LU Factorization)。求解线性方程时，可以把 A 写成 A = LU 的形式。 其中 U 是上三角矩阵，而 L 是下三角矩阵。上面的矩阵通过高斯消元，矩阵的初等变换求得。

• U 第一行的第一个非零元素称为 pivot 。
• L 第一行的最后一个非零元素者是 1.

$EA = U, A = E^{-1}U = LU$, L 是初等变换矩阵的逆。

SVD 的应用

SVD 可以应用在图像压缩和数据压缩中。 压缩一个图像 (256 x 512) 一个 Naive 的方法的是将相邻的 4 个像素合成一个象素，即压缩比例是 4:1。这种 Naive 的没有经过分析而进行的粗暴压缩方法容易造成很严重的图像失真。

通过 SVD 我们可以将 (256 x 512) 压缩成 (256 + 512) 即压缩比例是 170 : 1。我们可以用 5 个秩为 1 的矩阵来表示。用 SVD 表示出来就是前 5 个最大的特征值。

$$\begin{aligned} A = \vec{u_1}\sigma_1\vec{v_1}^T + \vec{u_2}\sigma_2\vec{v_2}^T + ... + \vec{u_5}\sigma_n\vec{v_5}^T \end{aligned}$$