【数学基础】第十七课:奇异值分解

奇异值分解

Posted by x-jeff on November 24, 2020

本文为原创文章,未经本人允许,禁止转载。转载请注明出处。

1.奇异值分解

奇异值分解(Singular Value Decomposition,简称SVD):对于任何一个矩阵$B_{m\times n}$,存在正交矩阵$P_{m\times m},Q_{n\times n}$,使得$B=PDQ^T$。其中,$D_{m\times n}$是一个只有对角元素不为零的矩阵。

矩阵$P=(\vec{p_1},\vec{p_2},…,\vec{p_m})$的大小为$m\times m$,列向量$\vec{p_1},\vec{p_2},…,\vec{p_m}$是$BB^T$的特征向量,也被称为矩阵$B$的左奇异向量(left singular vector)

矩阵$Q=(\vec{q_1},\vec{q_2},…,\vec{q_m})$的大小为$n\times n$,列向量$\vec{q_1},\vec{q_2},…,\vec{q_m}$是$B^TB$的特征向量,也被称为矩阵$B$的右奇异向量(right singular vector)

矩阵$D$主对角线上的元素称为奇异值

$D_{m\times n}$的形式举例如下($a_{mm}\neq 0$):

\[\begin{bmatrix} a_{11} & 0 & 0 & 0 & 0 \\ 0 & a_{22} & 0 & 0 & 0 \\ 0 & 0 & a_{33} & 0 & 0 \end{bmatrix}\]

2.如何计算SVD

  1. 计算$BB^T$和$B^TB$。
  2. 分别计算$BB^T$和$B^TB$的特征向量及其特征值。
  3. $BB^T$的特征向量组成$P$;而$B^TB$的特征向量组成$Q$。
  4. 对$BB^T$和$B^TB$的非零特征值求平方根,对应上述特征向量的位置,填入$D$的对角元。

举个例子,假设我们有矩阵$B$:

\[B=\begin{bmatrix} 1 & 1 \\ 1 & 1 \\ 0 & 0 \\ \end{bmatrix}\]

计算$BB^T$:

\[BB^T=\begin{bmatrix} 1 & 1 \\ 1 & 1 \\ 0 & 0 \\ \end{bmatrix} \begin{bmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ \end{bmatrix}=\begin{bmatrix} 2 & 2 & 0 \\ 2 & 2 & 0 \\ 0 & 0 & 0 \\ \end{bmatrix}\]

对其进行特征分解,分别得到特征值$\lambda_1,\lambda_2,\lambda_3$及其特征向量$x_1,x_2,x_3$:

\[\lambda _1 =4;x_1=\begin{bmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \\ 0 \\ \end{bmatrix}\] \[\lambda _2 =0;x_2=\begin{bmatrix} -\frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \\ 0 \\ \end{bmatrix}\] \[\lambda _3 =0;x_3=\begin{bmatrix} 0 \\ 0 \\ 1 \\ \end{bmatrix}\]

特征向量$x_1,x_2,x_3$组合起来得到$P$:

\[P=\begin{bmatrix} \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} & 0 \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 \\ 0 & 0 & 1 \\ \end{bmatrix}\]

计算$B^TB$:

\[B^TB=\begin{bmatrix} 1 & 1 & 0 \\ 1 & 1 & 0 \\ \end{bmatrix} \begin{bmatrix} 1 & 1 \\ 1 & 1 \\ 0 & 0 \\ \end{bmatrix} =\begin{bmatrix} 2 & 2 \\ 2 & 2 \\ \end{bmatrix}\]

同样的对其进行特征分解,得到特征值$\lambda_1,\lambda_2$和特征向量$x_1,x_2$:

\[\lambda_1=4;x_1=\begin{bmatrix} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \\ \end{bmatrix}\] \[\lambda_2=0;x_2=\begin{bmatrix} -\frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \\ \end{bmatrix}\]

特征向量$x_1,x_2$组合起来得到$Q$:

\[Q=\begin{bmatrix} \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \end{bmatrix}\]

将矩阵$BB^T$或矩阵$B^TB$的非零特征值从大到小排列后开根号填入$D$的对角元:

\[D=\begin{bmatrix} 2 & 0 \\ 0 & 0 \\ 0 & 0 \\ \end{bmatrix}\]

最终得到$B$的奇异值分解:

\[B=PDQ^T=\begin{bmatrix} \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} & 0 \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} 2 & 0 \\ 0 & 0 \\ 0 & 0 \\ \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \end{bmatrix}^T = \begin{bmatrix} 1 & 1 \\ 1 & 1 \\ 0 & 0 \\ \end{bmatrix}\]

3.SVD的应用

SVD通常用于以下领域:

  1. PCA。
  2. 推荐系统。
  3. 图像压缩。
  4. 潜在语义索引(Lstent Semantic Indexing, LSI)。

4.参考资料

  1. 一步步教你轻松学奇异值分解SVD降维算法
  2. 奇异值分解(SVD)的计算方法