线性代数 - 奇异值分解

49

概述

特征值与特征向量 一篇中我们讨论了 $n$ 阶对称矩阵 $\mathbf{S}$ 的对角化。即任一对称矩阵 $\mathbf{S}$ 都可以分解为 $\mathbf{Q} \boldsymbol{\Lambda} \mathbf{Q}^T$。本篇将介绍任一 $m \times n$ 的矩阵 $\mathbf{A}$ 的对角化,即奇异值分解Singular Value Decomposition)。任一 $m \times n$ 的矩阵 $\mathbf{A}$ 都可以分解为一个 $m \times m$ 的正交矩阵 $\mathbf{U}$,一个 $m \times n$ 的对角矩阵 $\boldsymbol{\Sigma}$ 以及一个 $n \times n$ 的正交矩阵 $\mathbf{V}$ 的转置 $\mathbf{V}^T$ 的乘积,即:

$$ \mathbf{A} = \mathbf{U} \boldsymbol{\Sigma} \mathbf{V}^T $$

$\mathbf{A}$ 为什么可以如此分解呢?首先来看奇异值分解的原理。

奇异值分解

假设 $ \mathbf{A} $ 是一个 $ m \times n $ 的矩阵,如何对其进行分解呢?在 特征值与特征向量 中我们已经知道如何分解一个对称矩阵,而 $\mathbf{A}^T \mathbf{A}$ 恰好就是一个对称矩阵!我们没有理由不对它进行一番研究!

$\mathbf{A}^T\mathbf{A}$ 是一个 $n \times n$ 的对称矩阵,它有 $n$ 个大于或等于 $0$ 的实特征值,不妨将这些特征值由大到小排列,记为 $\lambda_1$, $\lambda_2$, $\cdots$, $\lambda_n$,即:

$$ \lambda_1 \geqslant \lambda_2 \geqslant \cdots \geqslant \lambda_n \geqslant 0 \tag{1} $$

假设 $\mathbf{v}_1$, $\mathbf{v}_2$, $\cdots$, $\mathbf{v}_n$ 是 $\mathbf{A}^T\mathbf{A}$ 的对应于 $\lambda_1$, $\lambda_2$, $\cdots$, $\lambda_n$ 的标准正交特征向量。则对于 $1 \leqslant i \leqslant n$,有:

$$ \mathbf{A}^T \mathbf{A} \mathbf{v}_i = \lambda_i \mathbf{v}_i $$

两边左乘 $\mathbf{v}_i^T$:

$$ \mathbf{v}_i^T \mathbf{A}^T \mathbf{A} \mathbf{v}_i =\mathbf{v}_i^T \lambda_i \mathbf{v}_i $$

整理:

$$ (\mathbf{A} \mathbf{v}_i)^T(\mathbf{A} \mathbf{v}_i) = \lambda_i \mathbf{v}_i^T \mathbf{v}_i \tag{2} $$

由于 $\mathbf{v}_i$ 是单位向量,因此 $\mathbf{v}_i^T \mathbf{v}_i = 1$,上式化简为:

$$ \left\| \mathbf{A} \mathbf{v}_i \right\|^2 = \lambda_i $$

进而:

$$ \left\| \mathbf{A} \mathbf{v}_i \right\| = \sqrt{\lambda_i} \tag{3} $$

上式的 $\sqrt{\lambda_i}$ 称为 $\mathbf{A}$ 的奇异值Singular Value)。

假设 $\mathbf{A}^T\mathbf{A}$ 的特征值为 $\lambda$,那么 $\sqrt{\lambda}$ 称为 $\mathbf{A}$ 的奇异值,记为 $\sigma$,即:$ \sigma = \sqrt{\lambda} $

结论 1 根据 $(3)$ 式,$\mathbf{A}$ 的奇异值就是向量 $\mathbf{A}\mathbf{v}_i$ 的长度。当奇异值 $\sigma$ 为 $0$ 时,有 $\mathbf{A}\mathbf{v} = \mathbf{0}$。

假设 $\sigma_1$, $\sigma_2$, $\cdots$, $\sigma_n$ 是 $\mathbf{A}$ 的奇异值,则 $\sigma_1=\sqrt{\lambda_1}$, $\sigma_2=\sqrt{\lambda_2}$, $\cdots$, $\sigma_n=\sqrt{\lambda_n}$,根据 $(1)$ 式,有:

$$ \sigma_1 \geqslant \sigma_2 \geqslant \cdots \geqslant \sigma_n \geqslant 0 \tag{4} $$

$(2)$ 式研究的是两个相同的向量 $\mathbf{A}\mathbf{v}_i$ 与它自身的内积,现在我们研究两个不同的向量 $\mathbf{A}\mathbf{v}_i$ 与 $\mathbf{A}\mathbf{v}_j$($i \ne j$)的内积:

\begin{align*} (\mathbf{A}\mathbf{v}_i)^T (\mathbf{A}\mathbf{v}_j) &= \mathbf{v}_i^T \mathbf{A}^T \mathbf{A} \mathbf{v}_j \\ &= \mathbf{v}_i^T \lambda_j \mathbf{v}_j \\ &= \lambda_j \mathbf{v}_i^T \mathbf{v}_j \\ &= 0 \quad\quad \color{blue}{(\ \because \ \mathbf{v}_i \perp \mathbf{v}_j \quad \therefore \ \mathbf{v}_i^T \mathbf{v}_j = 0\ )} \end{align*}

由此可知:

结论 2    $\{ \mathbf{A}\mathbf{v}_1, \mathbf{A}\mathbf{v}_2, \cdots, \mathbf{A}\mathbf{v}_n \}$ 是一组正交向量集。

假设 $\mathbf{A}$ 有 $r$($r \leqslant n$)个不等于 $0$ 的奇异值,根据 $(4)$ 式,有:

$$ \sigma_1 \geqslant \sigma_2 \geqslant \cdots \geqslant \sigma_r \gt \sigma_{r+1} = \sigma_{r+2} = \cdots = \sigma_{n} = 0 $$

即:

$$ \lambda_1 \geqslant \lambda_2 \geqslant \cdots \geqslant \lambda_r \gt \lambda_{r+1} = \lambda_{r+2} = \cdots = \lambda_{n} = 0 \tag{5} $$

根据上面的 结论 1,有:

$$ \left\{ \begin{array}{l} \mathbf{A}\mathbf{v}_i \ne \mathbf{0} \quad (1 \leqslant i \leqslant r) \\ \mathbf{A}\mathbf{v}_i = \mathbf{0} \quad (r \lt i \leqslant n) \end{array} \right. \tag{6} $$

结论 2$(6)$ 式,得:

结论 4    $\{ \mathbf{A}\mathbf{v}_1, \mathbf{A}\mathbf{v}_2, \cdots, \mathbf{A}\mathbf{v}_r \}$ 是一组线性无关的正交向量集。

因为 $\mathbf{A}\mathbf{v}_1$, $\mathbf{A}\mathbf{v}_2$, $\cdots$, $\mathbf{A}\mathbf{v}_r$ 都是 $\mathbf{A}$ 的列向量的线性组合,所以 $\mathbf{A}\mathbf{v}_1$, $\mathbf{A}\mathbf{v}_2$, $\cdots$, $\mathbf{A}\mathbf{v}_r$ 都在 $\mathbf{A}$ 的列空间 $C(\mathbf{A})$ 中。

下面我们考虑 $\mathbf{A}$ 的列空间 $C(\mathbf{A})$ 中的任一向量 $\mathbf{y}$。根据列空间的定义,有:

$$ \mathbf{y} = \mathbf{A} \mathbf{x} \tag{7} $$

其中 $\mathbf{x}$ 是 $\mathbb{R}^n$ 中的任一向量,即:$\mathbf{x} \in \mathbb{R}^n $。

因为 $\mathbf{v}_1$, $\mathbf{v}_2$, $\cdots$, $\mathbf{v}_n$ 是 $\mathbf{A}^T\mathbf{A}$ 的标准正交特征向量,因此 $\{ \mathbf{v}_1, \mathbf{v}_2, \cdots, \mathbf{v}_n \}$ 是 $\mathbb{R}^n$ 的一个基。于是 $(7)$ 式的 $\mathbf{x}$ 可表示为:

$$\mathbf{x} = c_1 \mathbf{v}_1 + c_2 \mathbf{v}_2 + \cdots + c_n \mathbf{v}_n \tag{8} $$

结合 $(6)$ 式,$(7)$ 式,$(8)$ 式,有:

\begin{align*} \mathbf{y} &= \mathbf{A} \mathbf{x} \\ &= \mathbf{A} (c_1 \mathbf{v}_1 + c_2 \mathbf{v}_2 + \cdots + c_n \mathbf{v}_n) \\ &= c_1 \mathbf{A} \mathbf{v}_1 + c_2 \mathbf{A} \mathbf{v}_2 + \cdots + c_n \mathbf{A} \mathbf{v}_n \\ &= c_1 \mathbf{A} \mathbf{v}_1 + \cdots + c_r \mathbf{A} \mathbf{v}_r + c_{r+1} \mathbf{A} \mathbf{v}_{r+1} + \cdots + c_n \mathbf{A} \mathbf{v}_n \\ &= c_1 \mathbf{A} \mathbf{v}_1 + \cdots + c_r \mathbf{A} \mathbf{v}_r + 0 + \cdots + 0 \\ &= c_1 \mathbf{A} \mathbf{v}_1 + \cdots + c_r \mathbf{A} \mathbf{v}_r \end{align*}

因此 $\{ \mathbf{A}\mathbf{v}_1, \mathbf{A}\mathbf{v}_2, \cdots, \mathbf{A}\mathbf{v}_r \}$ 是 $C(\mathbf{A})$ 的一个正交基。由于这组基的向量个数为 $r$,因此 $C(\mathbf{A})$ 的维数 $\dim C(\mathbf{A})$ 也为 $r$,进而 $\mathbf{A}$ 的秩也为 $r$。于是得到结论:

结论 5 $$ \mathrm{rank}\ \mathbf{A} = \mathrm{dim}\ C(\mathbf{A}) = r $$

将 $\{ \mathbf{A}\mathbf{v}_1, \mathbf{A}\mathbf{v}_2, \cdots, \mathbf{A}\mathbf{v}_r \}$ 标准化:

$$ \mathbf{u}_i = \dfrac{\mathbf{A}\mathbf{v}_i}{\left\| \mathbf{A}\mathbf{v}_i \right\|} = \dfrac{1}{\sigma_i} \mathbf{A} \mathbf{v}_i \quad (1 \leqslant i \leqslant r) \tag{9} $$

即:

$$ \mathbf{A} \mathbf{v}_i = \sigma_i \mathbf{u}_i \quad (1 \leqslant i \leqslant r) \tag{10} $$

于是我们得到 $C(\mathbf{A})$ 下的一个标准正交基:$\{ \mathbf{u}_1, \mathbf{u}_2, \cdots, \mathbf{u}_r \}$。再从 $C(\mathbf{A})$ 的正交补,即 $\mathbf{A}$ 的左零空间 $N(\mathbf{A}^T)$ 中取 $m - r$ 个标准正交向量 $\mathbf{u}_{r+1}$, $\mathbf{u}_{r+2}$, $\cdots$, $\mathbf{u}_m$,并将它们合并到向量集 $\{ \mathbf{u}_1, \mathbf{u}_2, \cdots, \mathbf{u}_r \}$ 中,得到 $\mathbb{R}^m$ 下的一个标准正交基 $ \{ \mathbf{u}_1, \mathbf{u}_2, \cdots, \mathbf{u}_m \}$。

令 $\mathbf{U} = \begin{bmatrix} \mathbf{u}_1 & \mathbf{u}_2 & \cdots & \mathbf{u}_m \end{bmatrix}$,$\mathbf{V} = \begin{bmatrix} \mathbf{v}_1 & \mathbf{v}_2 \cdots \mathbf{v}_n \end{bmatrix}$,则 $\mathbf{U}$ 与 $\mathbf{V}$ 都是正交矩阵。

现在考虑 $\mathbf{A}$ 与 $\mathbf{V}$ 的乘积:

\begin{align*} \mathbf{A} \mathbf{V} &= \mathbf{A} \begin{bmatrix} \mathbf{v}_1 & \mathbf{v}_2 & \cdots & \mathbf{v}_n \end{bmatrix} \\ &= \begin{bmatrix} \mathbf{A} \mathbf{v}_1 & \mathbf{A} \mathbf{v}_2 & \cdots & \mathbf{A} \mathbf{v}_n \end{bmatrix} \end{align*}

根据 $(6)$ 式与 $(10)$ 式,有:

\begin{align*} \mathbf{A} \mathbf{V} &= \begin{bmatrix} \mathbf{A} \mathbf{v}_1 & \mathbf{A} \mathbf{v}_2 & \cdots & \mathbf{A} \mathbf{v}_n \end{bmatrix} \\ &= \begin{bmatrix} \mathbf{A} \mathbf{v}_1 & \cdots & \mathbf{A} \mathbf{v}_r & \mathbf{0} & \cdots & \mathbf{0} \end{bmatrix} \\ &= \begin{bmatrix} \sigma_1 \mathbf{u}_1 & \cdots & \sigma_r \mathbf{u}_r & \mathbf{0} & \cdots & \mathbf{0} \end{bmatrix} \end{align*} 令 $\mathbf{D}_{r \times r} = \begin{bmatrix} \sigma_1 & 0 & \cdots & 0 \\ 0 & \sigma_2 & \cdots & 0 \\ \vdots & \vdots & \ddots &\vdots \\ 0 & 0 & \cdots & \sigma_r \end{bmatrix}$,$\mathbf{U}_{m \times r} = \begin{bmatrix} \mathbf{u}_1 & \mathbf{u}_2 & \cdots & \mathbf{u}_r \end{bmatrix}$,$\mathbf{O}_{a \times b}$ 为元素全为 $0$ 的 $a \times b$ 矩阵,则: \begin{align*} \mathbf{A} \mathbf{V} &= \begin{bmatrix} \sigma_1 \mathbf{u}_1 & \cdots & \sigma_r \mathbf{u}_r & \mathbf{0} & \cdots & \mathbf{0} \end{bmatrix} \\ &= \begin{bmatrix} \mathbf{U}_{m \times r} \mathbf{D}_{r \times r} & \mathbf{O}_{m \times (n - r)} \end{bmatrix} \end{align*} 令 $\mathbf{U}_{m \times (m-r)} = \begin{bmatrix} \mathbf{u}_{r+1} & \mathbf{u}_{r+2} & \cdots & \mathbf{u}_m \end{bmatrix}$,则: \begin{align*} \mathbf{A} \mathbf{V} &= \begin{bmatrix} \mathbf{U}_{m \times r} \mathbf{D}_{r \times r} & \mathbf{O}_{m \times (n - r)} \end{bmatrix} \\ &= \begin{bmatrix} \mathbf{U}_{m \times r} \mathbf{D}_{r \times r} + \mathbf{O}_{m \times r} & \mathbf{O}_{m \times (n - r)} + \mathbf{O}_{m \times (n - r)} \end{bmatrix} \\ &= \begin{bmatrix} \mathbf{U}_{m \times r} \mathbf{D}_{r \times r} + \mathbf{U}_{m \times (m-r)} \mathbf{O}_{(m-r) \times r} & \mathbf{U}_{m \times r} \mathbf{O}_{r \times (n - r)} + \mathbf{U}_{m \times (m-r)} \mathbf{O}_{(m-r) \times (n-r)} \end{bmatrix} \\ &= \begin{bmatrix} \mathbf{U}_{m \times r} & \mathbf{U}_{m \times (m - r)} \end{bmatrix} \begin{bmatrix} \mathbf{D}_{r \times r} & \mathbf{O}_{r \times (n - r)} \\ \mathbf{O}_{(m - r) \times r} & \mathbf{O}_{(m - r) \times (n - r)} \end{bmatrix} \end{align*}

上式中的 $\begin{bmatrix} \mathbf{U}_{m \times r} & \mathbf{U}_{m \times (m - r)} \end{bmatrix} = \begin{bmatrix} \mathbf{u}_1 & \cdots & \mathbf{u}_r & \mathbf{u}_{r+1} & \cdots & \mathbf{u}_m \end{bmatrix} = \mathbf{U}$。

令:

$$\boldsymbol{\Sigma} = \begin{bmatrix} \mathbf{D}_{r \times r} & \mathbf{O}_{r \times (n - r)} \\ \mathbf{O}_{(m - r) \times r} & \mathbf{O}_{(m - r) \times (n - r)} \end{bmatrix}$$

则:

$$ \mathbf{A} \mathbf{V} = \mathbf{U} \boldsymbol{\Sigma} \tag{11} $$

由于 $\mathbf{V}$ 是正交矩阵,因此 $\mathbf{V}$ 可逆,且 $\mathbf{V}^{-1} = \mathbf{V}^T$,于是:

$$ \mathbf{A} = \mathbf{U} \boldsymbol{\Sigma} \mathbf{V}^{-1} = \mathbf{U} \boldsymbol{\Sigma} \mathbf{V}^T \tag{12} $$

上式就称为 $\mathbf{A}$ 的奇异值分解Singular Value Decomposition),简称 SVD。其中 $\mathbf{U}$ 的列向量称为 $\mathbf{A}$ 的左奇异向量Left Singular Vector),$\mathbf{V}$ 的列向量称为 $\mathbf{A}$ 的右奇异向量Right Singular Vector)。

从上面的推演中,我们知道 $\mathbf{V}$ 是 $\mathbf{A}^T\mathbf{A}$ 的特征向量矩阵,那么 $\mathbf{U}$ 又是什么呢?

根据 $(9)$ 式,当 $1 \leqslant i \leqslant r$ 时,有:

\begin{align*} \mathbf{A} \mathbf{A}^T \mathbf{u}_i &= \mathbf{A} \mathbf{A}^T \dfrac{1}{\sigma_i} \mathbf{A} \mathbf{v}_i \\ &= \dfrac{1}{\sigma_i} \mathbf{A} (\mathbf{A}^T \mathbf{A} \mathbf{v}_i) \\ &= \dfrac{1}{\sigma_i} \mathbf{A} \lambda_i \mathbf{v}_i \\ &= \dfrac{\lambda_i}{\sigma_i} \mathbf{A} \mathbf{v}_i \end{align*}

根据 $(10)$ 式,当 $1 \leqslant i \leqslant r$ 时,有:

\begin{align*} \mathbf{A} \mathbf{A}^T \mathbf{u}_i &= \dfrac{\lambda_i}{\sigma_i} \mathbf{A} \mathbf{v}_i \\ &= \dfrac{\lambda_i}{\sigma_i} \sigma_i \mathbf{u}_i \\ &= \lambda_i \mathbf{u}_i \end{align*}

于是:

$$ \mathbf{A} \mathbf{A}^T \mathbf{u}_i = \lambda_i \mathbf{u}_i \quad (1 \leqslant i \leqslant r) \tag{13} $$

再考虑 $r+1 \leqslant i \leqslant m$ 时的情况,由于当 $r+1 \leqslant i \leqslant m$ 时,$\mathbf{u}_i \in N(\mathbf{A}^T) $,因此:

$$ \mathbf{u}_i^T \mathbf{A} = \mathbf{0} $$

两边转置:

$$ \mathbf{A}^T \mathbf{u}_i = \mathbf{0} $$

两边左乘 $\mathbf{A}$:

\begin{align*} \mathbf{A} \mathbf{A}^T \mathbf{u}_i &= \mathbf{A} \mathbf{0} \\ &= \mathbf{0} \\ &= 0 \mathbf{u}_i \end{align*}

令 $\lambda_i’=0 \ (r+1 \leqslant i \leqslant m)$,有:

$$ \mathbf{A} \mathbf{A}^T \mathbf{u}_i = \lambda_i’ \mathbf{u}_i \quad (r+1 \leqslant i \leqslant m) \tag{14} $$

根据 $(13)$ 式与 $(14)$ 式,有:

$$ \left\{ \begin{array}{l} \mathbf{A} \mathbf{A}^T \mathbf{u}_i = \lambda_i \mathbf{u}_i \quad (1 \leqslant i \leqslant r) \\ \mathbf{A} \mathbf{A}^T \mathbf{u}_i = \lambda_i’ \mathbf{u}_i \quad (r+1 \leqslant i \leqslant m) \end{array} \right. $$

这就说明 $\mathbf{u}_1, \mathbf{u}_2, \cdots, \mathbf{u}_m$ 是 $\mathbf{A} \mathbf{A}^T$ 的特征向量,$\lambda_1, \cdots, \lambda_r, \lambda_{r+1}’, \cdots, \lambda_m’$ 是对应的特征值。

因此 $\mathbf{U} = \begin{bmatrix} \mathbf{u}_1, \mathbf{u}_2, \cdots, \mathbf{u}_m \end{bmatrix}$ 是 $\mathbf{A} \mathbf{A}^T$ 的特征向量矩阵($\mathbf{U}$ 同时也是正交矩阵)。

到这里我们也可以得出关于 $\mathbf{A}^T \mathbf{A}$ 与 $\mathbf{A} \mathbf{A}^T$ 特征值的关系。$\mathbf{A}^T \mathbf{A}$ 与 $\mathbf{A} \mathbf{A}^T$ 的前 $r$ 个特征值都是 $\lambda_1, \lambda_2, \cdots, \lambda_r$,即 $\mathbf{A}^T \mathbf{A}$ 与 $\mathbf{A} \mathbf{A}^T$ 的前 $r$ 个特征值相同。而根据 $(5)$ 式,$\mathbf{A}^T \mathbf{A}$ 的后 $n-r$ 个特征值 $\lambda_{r+1}, \lambda_{r+2}, \cdots, \lambda_n$ 都为 $0$,$\mathbf{A} \mathbf{A}^T$ 的后 $m-r$ 个特征值 $\lambda_{r+1}’, \lambda_{r+2}’, \cdots, \lambda_m’$ 同样也为 $0$。

以上就是奇异值分解的原理,我们来做一个总结:

奇异值分解

假设 $\mathbf{A}$ 是一个 $m \times n$ 的矩阵,并且 $\mathbf{A}$ 的秩为 $r$,那么一定存在一个 $m \times m$ 的矩阵 $\mathbf{U}$,一个 $m \times n$ 的矩阵 $\boldsymbol{\Sigma}$,一个 $n \times n$ 的矩阵 $\mathbf{V}$,使得:$$ \mathbf{A} = \mathbf{U} \boldsymbol{\Sigma} \mathbf{V}^T $$其中,$\mathbf{U}$ 是 $\mathbf{A}\mathbf{A}^T$ 的正交特征向量矩阵,$\mathbf{V}$ 是 $\mathbf{A}^T\mathbf{A}$ 的正交特征向量矩阵。$\boldsymbol{\Sigma}$ 的形式如下:$$\boldsymbol{\Sigma} = \begin{bmatrix} \mathbf{D}_{r \times r} & \mathbf{O}_{r \times (n - r)} \\ \mathbf{O}_{(m - r) \times r} & \mathbf{O}_{(m - r) \times (n - r)} \end{bmatrix}$$其中 $\mathbf{D}_{r \times r}$ 是由 $\mathbf{A}$ 的奇异值组成的对角矩阵,$\mathbf{O}_{a \times b}$ 表示元素全部为 $0$ 的 $a \times b$ 矩阵。

根据以上介绍的奇异值分解原理,容易得到 $\mathbf{A}$ 的奇异值分解步骤:


奇异值分解步骤
  1. 计算对角矩阵 $\mathbf{A}^T\mathbf{A}$ 的特征值与特征向量。
  2. 将特征值排列为 $\lambda_1 \geqslant \lambda_2 \geqslant \cdots \geqslant \lambda_n $,取不为 $0$ 的特征值(假设前 $r$ 个特征值不为 $0$)构造由 $\mathbf{A}$ 的奇异值组成的对角矩阵 $\mathbf{D}_{r \times r}$:$$\mathbf{D}_{r \times r} = \begin{bmatrix} \sigma_1 & 0 & \cdots & 0 \\ 0 & \sigma_2 & \cdots & 0 \\ \vdots & \vdots & \ddots &\vdots \\ 0 & 0 & \cdots & \sigma_r \end{bmatrix} = \begin{bmatrix} \sqrt{\lambda_1} & 0 & \cdots & 0 \\ 0 & \sqrt{\lambda_2} & \cdots & 0 \\ \vdots & \vdots & \ddots &\vdots \\ 0 & 0 & \cdots & \sqrt{\lambda_r} \end{bmatrix}$$进而构造 $\boldsymbol{\Sigma}$:$$ \boldsymbol{\Sigma} = \begin{bmatrix} \mathbf{D}_{r \times r} & \mathbf{O}_{r \times (n - r)} \\ \mathbf{O}_{(m - r) \times r} & \mathbf{O}_{(m - r) \times (n - r)} \end{bmatrix} $$然后构造 $\mathbf{V}$,假设对应于 $\lambda_1, \lambda_2, \cdots, \lambda_n$ 的标准正交特征向量为 $\mathbf{v}_1, \mathbf{v}_2, \cdots, \mathbf{v}_n$,则:$$\mathbf{V} = \begin{bmatrix} \mathbf{v}_1 & \mathbf{v}_2 & \cdots & \mathbf{v}_n \end{bmatrix}$$
  3. 根据 $(9)$ 式计算出前 $r$ 个 $\mathbf{u}_i\ (1 \leqslant i \leqslant r)$:$$ \mathbf{u}_i = \dfrac{1}{\sigma_i} \mathbf{A} \mathbf{v}_i\quad(1 \leqslant i \leqslant r) $$再根据 $\mathbf{A}^T \mathbf{u} = \mathbf{0}$ 找到 $N(\mathbf{A}^T)$ 的 $m-r$ 个基向量,将它们正交化,标准化,得到 $m-r$ 个标准正交向量 $\mathbf{u}_i\ (r+1 \leqslant i \leqslant m)$。
    构造 $\mathbf{U}$:$$\mathbf{U} = \begin{bmatrix} \mathbf{u}_1 & \mathbf{u}_2 & \cdots & \mathbf{u}_m \end{bmatrix} $$
  4. 写出 $\mathbf{A} = \mathbf{U} \boldsymbol{\Sigma} \mathbf{V}^T$。


    分解 $\mathbf{A} = \begin{bmatrix} -1 & 2 \\ 5 & -2 \end{bmatrix}$

计算 $\mathbf{A}^T\mathbf{A} = \begin{bmatrix} 26 & -12 \\ -12 & 8 \end{bmatrix}$ 的特征值并降序排列:$ \lambda_1 = 32,\ \lambda_2 = 2 $,对应的单位特征向量为 $$ \mathbf{v}_1 = \dfrac{1}{\sqrt{5}}\begin{bmatrix} 2 \\ -1 \end{bmatrix}, \quad \mathbf{v}_2 = \dfrac{1}{\sqrt{5}}\begin{bmatrix} 1 \\ 2 \end{bmatrix} $$ 计算非零奇异值:$$\sigma_1 = \sqrt{\lambda_1} = 4\sqrt{2},\quad \sigma_2 = \sqrt{\lambda_2} = \sqrt{2}$$ 根据非零奇异值构造 $\boldsymbol{\Sigma}$,得:$$ \boldsymbol{\Sigma} = \begin{bmatrix} 4\sqrt{2} & 0 \\ 0 & \sqrt{2} \end{bmatrix} $$ 根据特征向量构造 $\mathbf{V}$,得:$$ \mathbf{V} = \begin{bmatrix} \dfrac{2}{\sqrt{5}} & \dfrac{1}{\sqrt{5}} \\ -\dfrac{1}{\sqrt{5}} & \dfrac{2}{\sqrt{5}} \end{bmatrix} $$ 计算 $\mathbf{u}_1$ 与 $\mathbf{u}_2$:\begin{align*} \mathbf{u}_1 &= \dfrac{1}{\sigma_1} \mathbf{A} \mathbf{v}_1 = \dfrac{1}{\sqrt{10}} \begin{bmatrix} -1 \\ 3 \end{bmatrix} \\ \mathbf{u}_2 &= \dfrac{1}{\sigma_2} \mathbf{A} \mathbf{v}_2 = \dfrac{1}{\sqrt{10}} \begin{bmatrix} 3 \\ 1 \end{bmatrix} \end{align*} 根据 $\mathbf{u}_1$ 与 $\mathbf{u}_2$ 构造 $\mathbf{U}$:$$ \mathbf{U} = \begin{bmatrix} -\dfrac{1}{\sqrt{10}} & \dfrac{3}{\sqrt{10}} \\ \dfrac{3}{\sqrt{10}} & \dfrac{1}{\sqrt{10}} \end{bmatrix} $$ 于是:\begin{align*} \mathbf{A} &= \mathbf{U} \boldsymbol{\Sigma} \mathbf{V}^T \\ &= \begin{bmatrix} -\dfrac{1}{\sqrt{10}} & \dfrac{3}{\sqrt{10}} \\ \dfrac{3}{\sqrt{10}} & \dfrac{1}{\sqrt{10}} \end{bmatrix} \begin{bmatrix} 4\sqrt{2} & 0 \\ 0 & \sqrt{2} \end{bmatrix} \begin{bmatrix} \dfrac{2}{\sqrt{5}} & -\dfrac{1}{\sqrt{5}} \\ \dfrac{1}{\sqrt{5}} & \dfrac{2}{\sqrt{5}} \end{bmatrix} \end{align*}


    分解 $\mathbf{A} = \begin{bmatrix} 1 & 2 & 1 \\ -1 & 3 & -2 \end{bmatrix}$

计算 $\mathbf{A}^T\mathbf{A} = \begin{bmatrix} 2 & -1 & 3 \\ -1 & 13 & -4 \\ 3 & -4 & 5 \end{bmatrix}$ 的特征值并降序排列:$ \lambda_1 = 15,\ \lambda_2 = 5,\ \lambda_3 = 0 $,对应的单位特征向量为 $$ \mathbf{v}_1 = \dfrac{1}{5\sqrt{6}}\begin{bmatrix} 2 \\ -11 \\ 5 \end{bmatrix}, \quad \mathbf{v}_2 = \dfrac{1}{5\sqrt{2}}\begin{bmatrix} 4 \\ 3 \\ 5 \end{bmatrix}, \quad \mathbf{v}_3 = \dfrac{1}{5\sqrt{3}}\begin{bmatrix} -7 \\ 1 \\ 5 \end{bmatrix} $$ 计算非零奇异值:$$\sigma_1 = \sqrt{\lambda_1} = \sqrt{15},\quad \sigma_2 = \sqrt{\lambda_2} = \sqrt{5}$$ 根据非零奇异值构造 $\boldsymbol{\Sigma}$,得:$$ \boldsymbol{\Sigma} = \begin{bmatrix} \sqrt{15} & 0 & 0 \\ 0 & \sqrt{5} & 0 \end{bmatrix} $$ 根据特征向量构造 $\mathbf{V}$,得:$$ \mathbf{V} = \begin{bmatrix} \dfrac{2}{5\sqrt{6}} & \dfrac{4}{5\sqrt{2}} & -\dfrac{7}{5\sqrt{3}} \\ -\dfrac{11}{5\sqrt{6}} & \dfrac{3}{5\sqrt{2}} & \dfrac{1}{5\sqrt{3}} \\ \dfrac{5}{5\sqrt{6}} & \dfrac{5}{5\sqrt{2}} & \dfrac{5}{5\sqrt{3}} \end{bmatrix} $$ 计算 $\mathbf{u}_1$ 与 $\mathbf{u}_2$:\begin{align*} \mathbf{u}_1 = \dfrac{1}{\sigma_1} \mathbf{A} \mathbf{v}_1 = \dfrac{1}{\sqrt{10}} \begin{bmatrix} -1 \\ -3 \end{bmatrix} \\ \mathbf{u}_2 = \dfrac{1}{\sigma_2} \mathbf{A} \mathbf{v}_2 = \dfrac{1}{\sqrt{10}} \begin{bmatrix} 3 \\ -1 \end{bmatrix} \end{align*} 根据 $\mathbf{u}_1$ 与 $\mathbf{u}_2$ 构造 $\mathbf{U}$:$$ \mathbf{U} = \begin{bmatrix} -\dfrac{1}{\sqrt{10}} & \dfrac{3}{\sqrt{10}} \\ -\dfrac{3}{\sqrt{10}} & -\dfrac{1}{\sqrt{10}} \end{bmatrix} $$ 于是:\begin{align*} \mathbf{A} &= \mathbf{U} \boldsymbol{\Sigma} \mathbf{V}^T \\ &= \begin{bmatrix} -\dfrac{1}{\sqrt{10}} & \dfrac{3}{\sqrt{10}} \\ -\dfrac{3}{\sqrt{10}} & -\dfrac{1}{\sqrt{10}} \end{bmatrix} \begin{bmatrix} \sqrt{15} & 0 & 0 \\ 0 & \sqrt{5} & 0 \end{bmatrix} \begin{bmatrix} \dfrac{2}{5\sqrt{6}} & -\dfrac{11}{5\sqrt{6}} & \dfrac{5}{5\sqrt{6}} \\ \dfrac{4}{5\sqrt{2}} & \dfrac{3}{5\sqrt{2}} & \dfrac{5}{5\sqrt{2}} \\ -\dfrac{7}{5\sqrt{3}} & \dfrac{1}{5\sqrt{3}} & \dfrac{5}{5\sqrt{3}} \end{bmatrix} \end{align*}


    分解 $\mathbf{A} = \begin{bmatrix} 1 & -1 \\ 1 & 1 \\ 2 & 1 \end{bmatrix}$

计算 $\mathbf{A}^T\mathbf{A} = \begin{bmatrix} 6 & 2 \\ 2 & 3 \end{bmatrix}$ 的特征值并降序排列:$ \lambda_1 = 7,\ \lambda_2 = 2 $,对应的单位特征向量为 $$ \mathbf{v}_1 = \dfrac{1}{\sqrt{5}}\begin{bmatrix} 2 \\ 1 \end{bmatrix}, \quad \mathbf{v}_2 = \dfrac{1}{\sqrt{5}}\begin{bmatrix} 1 \\ -2 \end{bmatrix} $$ 计算非零奇异值:$$\sigma_1 = \sqrt{\lambda_1} = \sqrt{7},\quad \sigma_2 = \sqrt{\lambda_2} = \sqrt{2}$$ 根据非零奇异值构造 $\boldsymbol{\Sigma}$,得:$$ \boldsymbol{\Sigma} = \begin{bmatrix} \sqrt{7} & 0 \\ 0 & \sqrt{2} \\ 0 & 0 \end{bmatrix} $$ 根据特征向量构造 $\mathbf{V}$,得:$$ \mathbf{V} = \begin{bmatrix} \dfrac{2}{\sqrt{5}} & \dfrac{1}{\sqrt{5}} \\ \dfrac{1}{\sqrt{5}} & -\dfrac{2}{\sqrt{5}} \end{bmatrix} $$ 计算 $\mathbf{u}_1$ 与 $\mathbf{u}_2$:\begin{align*} \mathbf{u}_1 &= \dfrac{1}{\sigma_1} \mathbf{A} \mathbf{v}_1 = \dfrac{1}{\sqrt{35}} \begin{bmatrix} 1 \\ 3 \\ 5 \end{bmatrix} \\ \mathbf{u}_2 &= \dfrac{1}{\sigma_2} \mathbf{A} \mathbf{v}_2 = \dfrac{1}{\sqrt{10}} \begin{bmatrix} 3 \\ -1 \\ 0 \end{bmatrix} \end{align*} 根据 $\mathbf{A}^T\mathbf{u} = \mathbf{0}$ 解得:$$ \mathbf{u}_3 = \dfrac{1}{\sqrt{14}} \begin{bmatrix} -1 \\ -3 \\ 2 \end{bmatrix} $$ 根据 $\mathbf{u}_1$, $\mathbf{u}_2$, $\mathbf{u}_3$ 构造 $\mathbf{U}$:$$ \mathbf{U} = \begin{bmatrix} \dfrac{1}{\sqrt{35}} & \dfrac{3}{\sqrt{10}} & -\dfrac{1}{\sqrt{14}} \\ \dfrac{3}{\sqrt{35}} & -\dfrac{1}{\sqrt{10}} & -\dfrac{3}{\sqrt{14}} \\ \dfrac{5}{\sqrt{35}} & 0 & \dfrac{2}{\sqrt{14}} \end{bmatrix} $$ 于是:\begin{align*} \mathbf{A} &= \mathbf{U} \boldsymbol{\Sigma} \mathbf{V}^T \\ &= \begin{bmatrix} \dfrac{1}{\sqrt{35}} & \dfrac{3}{\sqrt{10}} & -\dfrac{1}{\sqrt{14}} \\ \dfrac{3}{\sqrt{35}} & -\dfrac{1}{\sqrt{10}} & -\dfrac{3}{\sqrt{14}} \\ \dfrac{5}{\sqrt{35}} & 0 & \dfrac{2}{\sqrt{14}} \end{bmatrix} \begin{bmatrix} \sqrt{7} & 0 \\ 0 & \sqrt{2} \\ 0 & 0 \end{bmatrix} \begin{bmatrix} \dfrac{2}{\sqrt{5}} & \dfrac{1}{\sqrt{5}} \\ \dfrac{1}{\sqrt{5}} & -\dfrac{2}{\sqrt{5}} \end{bmatrix} \end{align*}

奇异值分解的几何意义

下面我们讨论奇异值分解的几何意义。

考虑 $m \times n$ 的矩阵 $\mathbf{A}$ 对 $n$ 维向量 $\mathbf{x}$ 的变换:

$$ \mathbf{y} = \mathbf{A} \mathbf{x} $$

其中 $\mathbf{y}$ 表示变换结果,显然 $\mathbf{y}$ 是一个 $m$ 维向量。

为了研究上述变换的几何意义,不妨令:

$$ \left\| \mathbf{x} \right\| = 1 $$

这样一来,我们研究的向量集为 $X = \{ \mathbf{x} \mid \left\| \mathbf{x} \right\| = 1,\ \mathbf{x} \in \mathbb{R}^n \}$

在 $\mathbb{R}^n$ 中,$X$ 表示单位球面,如下图所示:

图1 - 单位球面

根据奇异值分解:

$$ \mathbf{y} = \mathbf{A} \mathbf{x} = \mathbf{U} \boldsymbol{\Sigma} \mathbf{V}^T \mathbf{x} $$

上式可以看成三次变换的叠加,每次变换都是在前一次变换的结果上进行。这三次变换分别为:

第一次变换是将 $\mathbf{V}^T$ 作用于 $\mathbf{x}$,即:$\mathbf{p} = \mathbf{V}^T \mathbf{x}$,其中 $\mathbf{p} \in \mathbb{R}^n$ 表示变换的结果。
第二次变换是将 $\boldsymbol{\Sigma}$ 作用于第一次变换的结果 $\mathbf{p}$,即:$\mathbf{q} = \boldsymbol{\Sigma} \mathbf{p} = \boldsymbol{\Sigma} \mathbf{V}^T \mathbf{x} $,其中 $\mathbf{q} \in \mathbb{R}^m$ 表示变换的结果。
第三次变换是将 $\mathbf{U}$ 作用于第二次变换的结果 $\mathbf{q}$,即:$\mathbf{y} = \mathbf{U} \mathbf{q} = \mathbf{U} \boldsymbol{\Sigma} \mathbf{V}^T \mathbf{x}$,这里的 $\mathbf{y} \in \mathbb{R}^m$ 就是变换的最终结果。

下面我们依次分析这三次变换。

首先是第一次变换:

$$ \mathbf{p} = \mathbf{V}^T \mathbf{x} $$

考察 $\mathbf{p}$ 的长度:

\begin{align*} \left\| \mathbf{p} \right\|^2 = \mathbf{p}^T \mathbf{p} = \mathbf{x}^T \mathbf{V} \mathbf{V}^T \mathbf{x} = \left\| \mathbf{x} \right\|^2 = 1\end{align*}

这说明 $\mathbf{p}$ 的长度与 $\mathbf{x}$ 相同,又由于 $\mathbf{p} \ne \mathbf{x}$(除非 $\mathbf{V}^T$ 是单位矩阵),因此说明 $\mathbf{p}$ 与 $\mathbf{x}$ 的方向不同。也就是说 $\mathbf{V}^T$ 对 $\mathbf{x}$ 的变换仅仅是将 $\mathbf{x}$ 进行旋转。假设 $P$ 是 $\mathbf{V}^T$ 对所有 $\mathbf{x} \in X$ 的变换所组成的结果集,则 $P = \{ \mathbf{p} \mid \mathbf{p} = \mathbf{V}^T\mathbf{x},\ \left\| \mathbf{p} \right\| = 1,\ \mathbf{p} \in \mathbb{R}^n \}$。$P$ 的形状仍然是单位球面。

顺带一提,任何正交矩阵都是 旋转矩阵(包括反射)。旋转矩阵作用于向量时,并不改变向量的长度,仅仅是将向量旋转一个角度(有时会改变坐标系手性,比如右手坐标系变为左手坐标系)。

第一次变换可以用下图说明:

图2 - 第一次变换:旋转。<br>($m=3,n=r=2$)

接着来看第二次变换:

$$ \mathbf{q} = \boldsymbol{\Sigma} \mathbf{p} $$

展开,并整理:

\begin{align*} \mathbf{q} &= \boldsymbol{\Sigma} \mathbf{p} \\ &= \left[ \begin{array}{c|c} \begin{matrix} \sigma_1 \\ & \ddots \\ & & \sigma_r \end{matrix} & 0 \\ \hline 0 & 0 \end{array} \right] \begin{bmatrix} p_1 \\ \vdots \\ p_r \\ \hline p_{r+1} \\ \vdots \\ p_n \end{bmatrix} \\ &= \begin{bmatrix} \sigma_1 p_1 \\ \vdots \\ \sigma_r p_r \\ 0 \\ \vdots \\ 0 \end{bmatrix} \end{align*}

令 $q_i = \sigma_i p_i \ (1 \leqslant i \leqslant r)$,则:

$$ \mathbf{q} = \begin{bmatrix} q_1 \\ \vdots \\ q_r \\ 0 \\ \vdots \\ 0 \end{bmatrix} = \begin{bmatrix} \sigma_1 p_1 \\ \vdots \\ \sigma_r p_r \\ 0 \\ \vdots \\ 0 \end{bmatrix} $$

注意 $\mathbf{q}$ 的后 $m-r$ 个分量都为 $0$,现在仅考虑 $\mathbf{q}$ 的前 $r$ 个不为 $0$ 的分量,因为 $r \leqslant n$,所以:

\begin{align*} & \dfrac{q_1^2}{\sigma_1^2} + \cdots + \dfrac{q_r^2}{\sigma_r^2} \\ &= p_1^2 + \cdots + p_r^2 \\ & \leqslant p_1^2 + \cdots + p_r^2 + p_{r+1}^2 + \cdots + p_n^2 \\ &=1 \end{align*}

即:

$$ \dfrac{q_1^2}{\sigma_1^2} + \cdots + \dfrac{q_r^2}{\sigma_r^2} \leqslant 1 $$

这是一个以 $\sigma_1, \cdots, \sigma_r$ 为半轴的椭球体,该椭球体可表示为: $Q = \{ \mathbf{q} \mid \mathbf{q} = \boldsymbol{\Sigma} \mathbf{p} ,\ \dfrac{q_1^2}{\sigma_1^2} + \cdots + \dfrac{q_r^2}{\sigma_r^2} \leqslant 1,\ \mathbf{q} \in \mathbb{R}^m \} $。这个结果说明了 $\boldsymbol{\Sigma}$ 将球面 $P$ 上的一点 $\mathbf{p}$ 变换为(映射到)椭球体 $Q$ 内的一点 $\mathbf{q} $。注意 $\mathbf{p} \in P \subset \mathbb{R}^n$,而 $\mathbf{q} \in Q \subset \mathbb{R}^m$,因此这个变换不仅改变了形状(球面变为椭球体),而且还改变了向量空间(由 $\mathbb{R}^n$ 变为 $\mathbb{R}^m$)。另外需要注意的是由于只有 $\mathbf{q}$ 的前 $r$ 个分量不为 $0$,因此 $Q$ 实际上是 $\mathbf{R}^m$ 下的 $r$ 维子空间中的一个椭球体。

第二次变化可以用下图说明:

图3 - 第二次变换:压扁、拉伸。<br>($m=3,n=r=2$)

最后来看第三次变换:

$$ \mathbf{y} = \mathbf{U} \mathbf{q} $$

考察 $\mathbf{y}$ 的长度:

\begin{align*} \left\| \mathbf{y} \right\|^2 = \mathbf{y}^T \mathbf{y} = \mathbf{q}^T \mathbf{U}^T \mathbf{U} \mathbf{q} = \left\| \mathbf{q} \right\|^2\end{align*}

这说明 $\mathbf{y}$ 的长度与 $\mathbf{q}$ 相同,又由于 $\mathbf{y} \ne \mathbf{q}$(除非 $\mathbf{U}$ 是单位矩阵),因此说明 $\mathbf{y}$ 与 $\mathbf{q}$ 的方向不同。也就是说 $\mathbf{U}$ 对 $\mathbf{q}$ 的变换仅仅是将 $\mathbf{q}$ 进行旋转。假设 $Y$ 是 $\mathbf{U}$ 对所有 $\mathbf{q} \in Q$ 的变换所组成的结果集,则 $Y = \{ \mathbf{y} \mid \mathbf{y} = \mathbf{U}\mathbf{q},\ \dfrac{y_1^2}{\sigma_1^2} + \cdots + \dfrac{y_r^2}{\sigma_r^2} \leqslant 1,\ \mathbf{y} \in \mathbb{R}^m \}$。$Y$ 的形状仍然是椭球体。

这个变换也可以简单地描述为:由于 $\mathbf{U}$ 是正交矩阵,因此它也是一个旋转矩阵,该矩阵并不改变 $\mathbf{q}$ 的长度,而仅仅是改变 $\mathbf{q}$ 的方向。

第三次变换可以用下图说明:

图4 - 第三次变换:旋转。<br>($m=3,n=r=2$)

所有的变换步骤可以用下图说明:

图5 - 奇异值分解的几何意义

版权声明:本文为原创文章,转载请注明出处。http://cynhard.com/2018/10/15/LA-Singular-Value-Decomposition/

推荐文章