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}\]