4 矩阵分解(Matrix Decompositions)

1.png

4.1 行列式和迹(Determinant and Trace)

方阵 $\boldsymbol{A} \in \mathbb{R}^{n \times n}$ 的行列式是一个将 $\boldsymbol{A}$ 映射为实数的函数,写作

$$ \operatorname{det}(\boldsymbol{A})=\left|\begin{array}{cccc}{a_{11}} & {a_{12}} & {\dots} & {a_{1 n}} \\ {a_{21}} & {a_{22}} & {\dots} & {a_{2 n}} \\ {\vdots} & {} & {\ddots} & {\vdots} \\ {a_{n 1}} & {a_{n 2}} & {\dots} & {a_{n n}}\end{array}\right| $$

通过判断矩阵的可逆性来引入行列式的概念。

  • 若 $\boldsymbol{A}$ 是 $1 \times 1$ 矩阵,则它是一个标量,$\boldsymbol{A}=a \Longrightarrow \boldsymbol{A}^{-1}=\frac{1}{a}$,$\boldsymbol{A}$ 可逆当且仅当 $a \neq 0$。
  • 若 $\boldsymbol{A}$ 是 $2 \times 2$ 矩阵,之前已经推导过:

$$ \boldsymbol{A}^{-1}=\frac{1}{a_{11} a_{22}-a_{12} a_{21}}\left[\begin{array}{cc}{a_{22}} & {-a_{12}} \\ {-a_{21}} & {a_{11}}\end{array}\right] $$

因此 $\boldsymbol{A}$ 可逆当且仅当 $a_{11} a_{22}-a_{12} a_{21} \neq 0$。

定理4.1

对任意方阵 $\boldsymbol{A} \in \mathbb{R}^{n \times n}$,$\boldsymbol{A}$ 是可逆的当且仅当 $\operatorname{det}(\boldsymbol{A}) \neq 0$。

$n=1$:

$$ \operatorname{det}(\boldsymbol{A})=\operatorname{det}\left(a_{11}\right)=a_{11} $$

$n=2$:

$$ \operatorname{det}(\boldsymbol{A})=\left|\begin{array}{cc}{a_{11}} & {a_{12}} \\ {a_{21}} & {a_{22}}\end{array}\right|=a_{11} a_{22}-a_{12} a_{21} $$

$n=3$ (萨鲁斯法则,Sarrus’ rule):

$$ \operatorname{det}(\boldsymbol{A})=\left|\begin{array}{lll}{a_{11}} & {a_{12}} & {a_{13}} \\ {a_{21}} & {a_{22}} & {a_{23}} \\ {a_{31}} & {a_{32}} & {a_{33}}\end{array}\right|=a_{11} a_{22} a_{33}+a_{21} a_{32} a_{13}+a_{31} a_{12} a_{23}-a_{31} a_{22} a_{13}-a_{11} a_{32} a_{23}-a_{21} a_{12} a_{33} $$

对于上三角矩阵和下三角矩阵 $T \in \mathbb{R}^{n \times n}$:

$$ \operatorname{det}(\boldsymbol{T})=\prod_{i=1}^{n} T_{i i} $$

行列式的几何意义:方阵 $\boldsymbol{A}$ 的行列式 $\operatorname{det}(\boldsymbol{A})$ 表示由 $\boldsymbol{A}$ 的列向量组成的平行多面体的带符号体积。

定理4.2 拉普拉斯展开(Laplace Expansion)

考虑矩阵 $\boldsymbol{A} \in \mathbb{R}^{n \times n}$,则对所有 $j=1, \ldots, n$:

  • 沿列 $j$ 展开

$$ \operatorname{det}(\boldsymbol{A})=\sum_{k=1}^{n}(-1)^{k+j} a_{k j} \operatorname{det}\left(\boldsymbol{A}_{k, j}\right) $$

  • 沿行 $i$ 展开

$$ \operatorname{det}(\boldsymbol{A})=\sum_{k=1}^{n}(-1)^{k+j} a_{j k} \operatorname{det}\left(\boldsymbol{A}_{j, k}\right) $$

其中 $\boldsymbol{A}_{k, j} \in \mathbb{R}^{(n-1) \times(n-1)}$ 是 $\boldsymbol{A}$ 删除第 $k$ 行和第 $j$ 列后的子矩阵。

对于矩阵 $A \in \mathbb{R}^{n \times n}$,其行列式具有以下性质:

  • $\operatorname{det}(\boldsymbol{A} \boldsymbol{B})=\operatorname{det}(\boldsymbol{A}) \operatorname{det}(\boldsymbol{B})$
  • $\operatorname{det}(\boldsymbol{A})=\operatorname{det}\left(\boldsymbol{A}^{\top}\right)$
  • $\operatorname{det}\left(\boldsymbol{A}^{-1}\right)=\frac{1}{\operatorname{det}(\boldsymbol{A})}$
  • 相似矩阵具有相同的行列式值,对于线性映射 $\Phi : V \rightarrow V$,所有变换矩阵 $\boldsymbol{A}_{\Phi}$ 行列式相等,因此行列式的值与线性映射的基向量的选择无关
  • 将一行(或列)的倍数加到另一行(或列)上不会改变 $\operatorname{det}(\boldsymbol{A})$
  • 将一行(列)乘以 $\lambda \in \mathbb{R}$,行列式变为原来的 $\lambda$ 倍,特别地 $\operatorname{det}(\lambda \boldsymbol{A})=\lambda^{n} \operatorname{det}(\boldsymbol{A})$
  • 交换矩阵的两行(或两列),行列式变号

定理4.3

方阵 $\boldsymbol{A} \in \mathbb{R}^{n \times n}$ 的行列式 $\operatorname{det}(\boldsymbol{A}) \neq 0$ 当且仅当 $\operatorname{rk}(\boldsymbol{A})=n$($\boldsymbol{A}$ 可逆)

定义4.4 迹(trace)

方阵 $\boldsymbol{A} \in \mathbb{R}^{n \times n}$ 的迹定义为:

$$ \operatorname{tr}(\boldsymbol{A}) :=\sum_{i=1}^{n} a_{i i} $$

即对角线元素之和。

矩阵的迹满足以下性质:

  • $\operatorname{tr}(\boldsymbol{A}+\boldsymbol{B})=\operatorname{tr}(\boldsymbol{A})+\operatorname{tr}(\boldsymbol{B})$
  • $\operatorname{tr}(\alpha \boldsymbol{A})=\alpha \operatorname{tr}(\boldsymbol{A}), \alpha \in \mathbb{R}$
  • $\operatorname{tr}\left(\boldsymbol{I}_{n}\right)=n$
  • $\operatorname{tr}(\boldsymbol{A} \boldsymbol{B})=\operatorname{tr}(\boldsymbol{B} \boldsymbol{A})$,$\boldsymbol{A} \in \mathbb{R}^{n \times k}, \boldsymbol{B} \in \mathbb{R}^{k \times n}$

性质4可以推广为迹在循环排列下保持不变:

$$ \operatorname{tr}(\boldsymbol{A} \boldsymbol{K} \boldsymbol{L})=\operatorname{tr}(\boldsymbol{K} \boldsymbol{L} \boldsymbol{A})=\operatorname{tr}(\boldsymbol{L} \boldsymbol{A} \boldsymbol{K}) \quad \boldsymbol{A} \in \mathbb{R}^{a \times k}, \boldsymbol{K} \in \mathbb{R}^{k \times l}, \boldsymbol{L} \in \mathbb{R}^{l \times a} $$

对于线性映射 $\Phi : V \rightarrow V$,所有变换矩阵 $\boldsymbol{A}_{\Phi}$ 的迹相等:

$$ \operatorname{tr}(\boldsymbol{B})=\operatorname{tr}\left(\boldsymbol{S}^{-1} \boldsymbol{A} \boldsymbol{S}\right)=\operatorname{tr}\left(\boldsymbol{A} \boldsymbol{S} \boldsymbol{S}^{-1}\right)=\operatorname{tr}(\boldsymbol{A}) $$

因此迹的值与线性映射的基向量的选择无关。

定义4.5 特征多项式(Characteristic Polynomial)

对于 $\lambda \in \mathbb{R},\boldsymbol{A} \in \mathbb{R}^{n \times n}$,多项式

$$ \begin{aligned} p_{\boldsymbol{A}}(\lambda) & :=\operatorname{det}(\boldsymbol{A}-\lambda \boldsymbol{I}) \\ &=c_{0}+c_{1} \lambda+c_{2} \lambda^{2}+\cdots+c_{n-1} \lambda^{n-1}+(-1)^{n} \lambda^{n} \end{aligned} $$

$c_{0}, \ldots, c_{n-1} \in \mathbb{R}$,被称为矩阵 $\boldsymbol{A}$ 的特征多项式。特别地:

$$ \begin{aligned} c_{0} &=\operatorname{det}(\boldsymbol{A}) \\ c_{n-1} &=(-1)^{n-1} \operatorname{tr}(\boldsymbol{A}) \end{aligned} $$

4.2 特征值和特征向量(Eigenvalues and Eigenvectors)

定义4.6 特征方程(eigenvalue equation)

对于方阵 $\boldsymbol{A} \in \mathbb{R}^{n \times n}$,如果:

$$ \boldsymbol{A} \boldsymbol{x}=\lambda \boldsymbol{x} $$

则 $\lambda \in \mathbb{R}$ 是 $\boldsymbol{A}$ 的一个特征值,$\boldsymbol{x} \in \mathbb{R}^{n} \backslash\{\mathbf{0}\}$ 是相应的特征向量。该方程称为特征方程。

以下说法等价:

  • $\lambda$ 是 $\boldsymbol{A} \in \mathbb{R}^{n \times n}$ 的特征值
  • 存在 $\boldsymbol{x} \in \mathbb{R}^{n} \backslash\{\mathbf{0}\}$ 使得 $\boldsymbol{A} \boldsymbol{x}=\lambda \boldsymbol{x}$,或者说 $(\boldsymbol{A}-\lambda \boldsymbol{I}_{n} ) \boldsymbol{x}=\mathbf{0}$ 有平凡解
  • $\operatorname{rk}\left(\boldsymbol{A}-\lambda \boldsymbol{I}_{n}\right)<n$
  • $\operatorname{det}\left(\boldsymbol{A}-\lambda \boldsymbol{I}_{n}\right)=0$

定义4.7 共线性和共向性(Collinearity and Codirection)

两个方向相同的向量被称为共向的,两个方向相同或相反的向量被称为共线的。

特征向量不唯一,任何与特征向量共线的向量都是特征向量。

定理4.8

$\lambda \in \mathbb{R}$ 是 $\boldsymbol{A} \in \mathbb{R}^{n \times n}$ 的特征值当且仅当 $\lambda$ 是 $\boldsymbol{A}$ 的特征多项式 $p_{A}(\lambda)$ 的根。

定义4.9 代数重数(algebraic multiplicity)

设 $\boldsymbol{A}$ 有一个特征值 $\lambda_i$,$\lambda_i$ 的代数重数是指这个根在特征多项式中出现的次数。

定义4.10 特征空间和特征谱(Eigenspace and Eigenspectrum)

对于矩阵 $\boldsymbol{A} \in \mathbb{R}^{n \times n}$,与特征值 $\lambda$ 相关的所有特征向量的集合组成了一个 $\mathbb{R}^{n}$ 的子空间,称为 $\boldsymbol{A}$ 关于 $\lambda$ 的特征空间,表示为 $E_{\lambda}$。$\boldsymbol{A}$ 的所有特征值的集合称为特征谱,或谱。

方阵 $\boldsymbol{A}$ 关于特征值 $\lambda$ 的特征空间 $E_{\lambda}$ 是齐次线性方程组 $(\boldsymbol{A}-\lambda \boldsymbol{I}) \boldsymbol{x}=\mathbf{0}$ 的解空间。几何上,关于一个非零特征值的特征向量表示该矩阵表示的线性映射的一个拉伸(stretch)方向,特征值表示拉伸因子。特征值为负表示拉伸方向相反。

特征值和特征向量有以下有用的性质:

  • 方阵 $\boldsymbol{A}$ 和它的转置 $\boldsymbol{A}^{\top}$ 具有相同的特征值,但特征向量不一定相同。
  • 特征空间 $E_{\lambda}$ 是 $\boldsymbol{A}-\lambda \boldsymbol{I}$ 的零空间。
  • 相似矩阵具有相同的特征值。特征值、行列式和迹是一个线性映射的主要特征参数,因为它们都与基变换无关。
  • 正定矩阵的特征值永远为正实数。

定义4.11 几何重数(geometric multiplicity)

设 $\lambda_i$ 是方阵 $\boldsymbol{A}$ 的一个特征值,则 $\lambda_i$ 的几何重数是与 $\lambda_i$ 相关的线性无关的特征向量的个数,即关于 $\lambda_i$ 的特征空间的维数。

特征值的几何重数 $\le$ 代数重数。

在二维向量空间上使用不同的线性映射对行列式、特征向量、特征值建立一些几何直觉:

  • $\boldsymbol{A}_{1}=\left[\begin{array}{cc}{\frac{1}{2}} & {0} \\ {0} & {2}\end{array}\right]$,表示一个拉伸(strech)变换,特征值为 $\lambda_{1}=2, \lambda_2=\frac{1}{2}$,两个特征向量的方向分别与两个基向量相同。该变换保持面积不变,即 $\operatorname{det}\left(\boldsymbol{A}_{1}\right)=1=2 \cdot \frac{1}{2}$。

2.png

一般地,容易看出此类变换的拉伸性:

$$ \left[\begin{array}{cc}{m} & {0} \\ {0} & {n}\end{array}\right] \left[\begin{array}{c}{x} \\ {y}\end{array}\right]= \left[\begin{array}{c}{mx} \\ {ny}\end{array}\right] $$

  • $\boldsymbol{A}_{2}=\left[\begin{array}{cc}{1} & {\frac{1}{2}} \\ {0} & {1}\end{array}\right]$,表示一个剪切变换(shearing mapping),特征值为 $\lambda_1=\lambda_2=1$,两个特征向量共线。

3.png

对于上三角矩阵,$\left[\begin{array}{cc}{1} & {m} \\ {0} & {1}\end{array}\right]\left[\begin{array}{l}{x} \\ {y}\end{array}\right]=\left[\begin{array}{c}{x+my} \\ {y}\end{array}\right]$,即将直线 $x=a$ 映射为直线 $x=my+a$。

对于下三角矩阵,$\left[\begin{array}{cc}{1} & {0} \\ {m} & {1}\end{array}\right]\left[\begin{array}{l}{x} \\ {y}\end{array}\right]=\left[\begin{array}{c}{x} \\ {mx+y}\end{array}\right]$,即将直线 $y=b$ 映射为直线 $y=mx+b$。

  • $\boldsymbol{A}_{3}=\left[\begin{array}{cc}{\cos \left(\frac{\pi}{6}\right)} & {-\sin \left(\frac{\pi}{6}\right)} \\ {\sin \left(\frac{\pi}{6}\right)} & {\cos \left(\frac{\pi}{6}\right)}\end{array}\right]=\frac{1}{2}\left[\begin{array}{cc}{\sqrt{3}} & {-1} \\ {1} & {\sqrt{3}}\end{array}\right]$,两个特征值为复数,说明该变换是一个旋转变换。

4.png

  • $\boldsymbol{A}_{4}=\left[\begin{array}{cc}{1} & {-1} \\ {-1} & {1}\end{array}\right]$,特征值为 $\lambda_{1}=0, \lambda_{2}=2$,因此有一个维度消失,在关于 $\lambda_2$ 的特征向量方向上拉伸2倍。

5.png

  • $A_{5}=\left[\begin{array}{ll}{1} & {\frac{1}{2}} \\ {\frac{1}{2}} & {1}\end{array}\right]$,特征值为 $\lambda_{1}=\frac{1}{2}, \lambda_{2}=\frac{3}{2}$,表示一个剪切拉伸变换,将空间区域面积变为原来的 $75\%$,因为 $\left|\operatorname{det}\left(\boldsymbol{A}_{5}\right)\right|=\frac{3}{4}$。

6.png

定理4.12

具有 $n$ 个不同特征值的矩阵 $\boldsymbol{A} \in \mathbb{R}^{n \times n}$ 的特征向量 $\boldsymbol{x}_{1}, \dots, \boldsymbol{x}_{n}$ 线性无关。

定义4.13

若方阵 $\boldsymbol{A} \in \mathbb{R}^{n \times n}$ 具有少于 $n$ 个线性无关的特征向量,则称它是亏损的(defective)。

非亏损矩阵 $\boldsymbol{A} \in \mathbb{R}^{n \times n}$ 不一定具有 $n$ 个不同的特征值,但它需要它的特征向量能构成 $\mathbb{R}^n$ 空间的一组基。

定理4.14

给定矩阵 $\boldsymbol{A} \in \mathbb{R}^{m \times n}$,我们总是可以通过如下方式获得一个半正定矩阵 $\boldsymbol{S} \in \mathbb{R}^{n \times n}$:

$$ \boldsymbol{S} :=\boldsymbol{A}^{\top} \boldsymbol{A} $$

如果 $\operatorname{rk}(\boldsymbol{A})=n$,则 $\boldsymbol{S} :=\boldsymbol{A}^{\top} \boldsymbol{A}$ 是正定的。

证明:

  • 对称性:

$$ \boldsymbol{S}=\boldsymbol{A}^{\top} \boldsymbol{A}=\boldsymbol{A}^{\top}\left(\boldsymbol{A}^{\top}\right)^{\top}=\left(\boldsymbol{A}^{\top} \boldsymbol{A}\right)^{\top}=\boldsymbol{S}^{\top} $$

  • 半正定性:

$$ (\boldsymbol{A} \boldsymbol{x})^{\top}(\boldsymbol{A} \boldsymbol{x}) \geqslant 0 $$

定理4.15 谱定理(spectral theorem)

如果 $\boldsymbol{A} \in \mathbb{R}^{n \times n}$ 是对称的,则存在一组向量空间 $V$ 的标准正交基由 $\boldsymbol{A}$ 的特征向量组成,并且每个特征值都是实数。

谱定理说明对称矩阵 $\boldsymbol{A}$ 存在特征分解,且可以找到标准正交的特征向量使得 $\boldsymbol{A}=\boldsymbol{P} \boldsymbol{D} \boldsymbol{P}^{\top}$,其中 $\boldsymbol{D}$ 是对角矩阵,$\boldsymbol{P}$ 的列包含特征向量。

定理4.16

矩阵 $\boldsymbol{A} \in \mathbb{R}^{n \times n}$ 的行列式是其 $n$ 个特征值的积,即:

$$ \operatorname{det}(\boldsymbol{A})=\prod_{i=1}^{n} \lambda_{i} $$

定理4.17

矩阵 $\boldsymbol{A} \in \mathbb{R}^{n \times n}$ 的迹是其 $n$ 个特征值的和,即:

$$ \operatorname{tr}(\boldsymbol{A})=\sum_{i=1}^{n} \lambda_{i} $$

4.3 楚列斯基分解(Cholesky Decomposition)

定理4.18 楚列斯基分解

正定矩阵 $\boldsymbol{A}$ 可以被分解为 $\boldsymbol{A}=\boldsymbol{L} \boldsymbol{L}^{\top}$,其中 $\boldsymbol{L}$ 是对角线元素为正的下三角矩阵:

$$ \left[\begin{array}{ccc}{a_{11}} & {\cdots} & {a_{1 n}} \\ {\vdots} & {\ddots} & {\vdots} \\ {a_{n 1}} & {\cdots} & {a_{n n}}\end{array}\right]=\left[\begin{array}{ccc}{l_{11}} & {\cdots} & {0} \\ {\vdots} & {\ddots} & {\vdots} \\ {l_{n 1}} & {\cdots} & {l_{n n}}\end{array}\right]\left[\begin{array}{ccc}{l_{11}} & {\cdots} & {l_{n 1}} \\ {\vdots} & {\ddots} & {\vdots} \\ {0} & {\cdots} & {l_{n n}}\end{array}\right] $$

$\boldsymbol{L}$ 被称为 $\boldsymbol{A}$ 的楚列斯基因子,且 $\boldsymbol{L}$ 是唯一的。

对于矩阵 $A \in \mathbb{R}^{3 \times 3}$,其楚列斯基分解为 $\boldsymbol{A}=\boldsymbol{L} \boldsymbol{L}^{\top}$,即:

$$ \boldsymbol{A}=\left[\begin{array}{ccc}{a_{11}} & {a_{21}} & {a_{31}} \\ {a_{21}} & {a_{22}} & {a_{32}} \\ {a_{31}} & {a_{32}} & {a_{33}}\end{array}\right]=\boldsymbol{L} \boldsymbol{L}^{\top}=\left[\begin{array}{ccc}{l_{11}} & {0} & {0} \\ {l_{21}} & {l_{22}} & {0} \\ {l_{31}} & {l_{32}} & {l_{33}}\end{array}\right]\left[\begin{array}{ccc}{l_{11}} & {l_{21}} & {l_{31}} \\ {0} & {l_{22}} & {l_{32}} \\ {0} & {0} & {l_{33}}\end{array}\right] $$

等式右边相乘得:

$$ \boldsymbol{A}=\left[\begin{array}{ccc}{l_{11}^{2}} & {l_{21} l_{11}} & {l_{31} l_{11}} \\ {l_{21} l_{11}} & {l_{21}^{2}+l_{22}^{2}} & {l_{31} l_{21}+l_{32} l_{22}} \\ {l_{31} l_{11}} & {l_{31} l_{21}+l_{32} l_{22}} & {l_{31}^{2}+l_{32}^{2}+l_{33}^{2}}\end{array}\right] $$

比较对应元素可得:

$$ \boldsymbol{L}=\left[\begin{array}{ccc}{\sqrt{a_{11}}} & {0} & {0} \\ {\frac{a_{21}}{l_{11}}} & {\sqrt{a_{22}-l_{21}^{2}}} & {0} \\ {\frac{a_{31}}{l_{11}}} & {\frac{a_{32}-l_{31} l_{21}}{l_{22}}} & {\sqrt{a_{33}-\left(l_{31}^{2}+l_{32}^{2}\right)}}\end{array}\right] $$

4.4 特征分解和对角化(Eigendecomposition and Diagonalization)

定义4.19 可对角化(Diagonalizable)

如果矩阵 $\boldsymbol{A} \in \mathbb{R}^{n \times n}$ 与一个对角矩阵相似,即存在可逆矩阵 $\boldsymbol{P}$ 使得 $\boldsymbol{D}=\boldsymbol{P}^{-1} \boldsymbol{A} \boldsymbol{P}$,则称它是可对角化的。

令矩阵 $\boldsymbol{A} \in \mathbb{R}^{n \times n}$,$\lambda_{1}, \ldots, \lambda_{n}$ 是一系列数值,$\boldsymbol{p}_{1}, \dots, \boldsymbol{p}_{n}$ 是 $\mathbb{R}^n$ 空间中的向量集合。定义 $\boldsymbol{P} :=\left[\boldsymbol{p}_{1}, \dots, \boldsymbol{p}_{n}\right]$,$\boldsymbol{D} \in \mathbb{R}^{n \times n}$ 的对角线元素为 $\lambda_{1}, \ldots, \lambda_{n}$,则

$$ \boldsymbol{A} \boldsymbol{P}=\boldsymbol{P} \boldsymbol{D} $$

当且仅当 $\lambda_{1}, \ldots, \lambda_{n}$ 是 $\boldsymbol{A}$ 的特征值,$\boldsymbol{p}_{1}, \dots, \boldsymbol{p}_{n}$ 是相应的特征向量。

$$ \begin{array}{l}{\boldsymbol{A} \boldsymbol{P}=\boldsymbol{A}\left[\boldsymbol{p}_{1}, \ldots, \boldsymbol{p}_{n}\right]=\left[\boldsymbol{A} \boldsymbol{p}_{1}, \ldots, \boldsymbol{A} \boldsymbol{p}_{n}\right]} \\ {\boldsymbol{P} \boldsymbol{D}=\left[\boldsymbol{p}_{1}, \ldots, \boldsymbol{p}_{n}\right]\left[\begin{array}{ccc}{\lambda_{1}} & {} & {0} \\ {} & {\ddots} & {} \\ {0} & {} & {\lambda_{n}}\end{array}\right]=\left[\lambda_{1} \boldsymbol{p}_{1}, \ldots, \lambda_{n} \boldsymbol{p}_{n}\right]}\end{array} $$

因此

$$ \begin{aligned} \boldsymbol{A} \boldsymbol{p}_{1} &=\lambda_{1} \boldsymbol{p}_{1} \\ & \vdots \\ \boldsymbol{A} \boldsymbol{p}_{n} &=\lambda_{n} \boldsymbol{p}_{n} \end{aligned} $$

定理4.20 特征分解(Eigendecomposition)

方阵 $\boldsymbol{A} \in \mathbb{R}^{n \times n}$ 能被分解为

$$ \boldsymbol{A}=\boldsymbol{P} \boldsymbol{D} \boldsymbol{P}^{-1} $$

其中 $\boldsymbol{P} \in \mathbb{R}^{n \times n}$,$\boldsymbol{D}$ 是对角线元素为 $\boldsymbol{A}$ 的特征值的对角矩阵,当且仅当 $\boldsymbol{A}$ 的特征向量组成 $\mathbb{R}^n$ 的一组基。

特征分解的几何解释:

7.png

定理4.21

对称矩阵 $\boldsymbol{S} \in \mathbb{R}^{n \times n}$ 一定是可对角化的。

特征分解的应用:

  • 求矩阵的幂

$$ \boldsymbol{A}^{k}=\left(\boldsymbol{P} \boldsymbol{D} \boldsymbol{P}^{-1}\right)^{k}=\boldsymbol{P} \boldsymbol{D}^{k} \boldsymbol{P}^{-1} $$

  • 求矩阵的行列式

$$ \operatorname{det}(\boldsymbol{A})=\operatorname{det}\left(\boldsymbol{P} \boldsymbol{D} \boldsymbol{P}^{-1}\right)=\operatorname{det}(\boldsymbol{P}) \operatorname{det}(\boldsymbol{D}) \operatorname{det}\left(\boldsymbol{P}^{-1}\right)==\operatorname{det}(\boldsymbol{D})=\prod_{i} d_{i i} $$

4.5 奇异值分解(Singular Value Decomposition)

定理4.22 SVD定理

设 $\boldsymbol{A}^{m \times n}$ 为秩等于 $r \in[0, \min (m, n)]$ 的矩阵,则 $\boldsymbol{A}$ 的奇异值分解具有以下形式:

$$ \boldsymbol{A}=\boldsymbol{U}\boldsymbol{\Sigma}\boldsymbol{V}^{\top} $$

其中正交矩阵 $\boldsymbol{U} \in \mathbb{R}^{m \times m}$,其列向量为 $\boldsymbol{u}_{i}, i=1, \ldots, m$;正交矩阵 $\boldsymbol{V} \in \mathbb{R}^{n \times n}$,其列向量为 $\boldsymbol{v}_{j}, j=1, \dots, n$;矩阵$\boldsymbol{\Sigma}\in\mathbb{R}^{m \times n}$,且 $\Sigma_{i i}=\sigma_{i} \geqslant 0,\Sigma_{i j}=0, i \neq j$。

$\boldsymbol{\Sigma}$ 的对角线元素 $\sigma_{i}, i=1, \dots, r$ 被称为奇异值,$\boldsymbol{u}_{i}$ 被称为左奇异向量(left-singular vectors),$\boldsymbol{v}_{j}$ 被称为右奇异向量(right-singular vectors)。为了方便起见,通常将奇异值按从大到小排序,即 $\sigma_{1} \geqslant \sigma_{2} \geqslant \sigma_{r} \geqslant 0$。

任何矩阵 $\boldsymbol{A} \in \mathbb{R}^{m \times n}$ 都存在SVD分解,且奇异值矩阵 $\boldsymbol{\Sigma}$ 是唯一的。

4.5.1 奇异值分解的几何解释

8.png

$$ A=\left[\begin{array}{cc}{1} & {-0.8} \\ {0} & {1} \\ {1} & {0}\end{array}\right]=U \Sigma V^{\top}=\left[\begin{array}{ccc}{-0.79} & {0} & {-0.62} \\ {0.38} & {-0.78} & {-0.49} \\ {-0.48} & {-0.62} & {0.62}\end{array}\right]\left[\begin{array}{cc}{1.62} & {0} \\ {0} & {1.0} \\ {0} & {0}\end{array}\right]\left[\begin{array}{cc}{-0.78} & {0.62} \\ {-0.62} & {-0.78}\end{array}\right] $$

为例:

9.png

4.5.2 奇异值分解的建立

正定矩阵(SPD Matrix)的SVD分解就是其特征分解:

$$ \boldsymbol{S}=\boldsymbol{S}^{\top}=\boldsymbol{P} \boldsymbol{D} \boldsymbol{P}^{\top} $$

对于任意矩阵 $\boldsymbol{A} \in \mathbb{R}^{m \times n}$,计算其SVD分解需要找到两组分别关于上域 $\mathbb{R}^{m}$ 和域 $\mathbb{R}^{n}$ 的标准正交基 $U=\left(\boldsymbol{u}_{1}, \ldots, \boldsymbol{u}_{m}\right)$和$V=\left(\boldsymbol{v}_{1}, \dots, \boldsymbol{v}_{n}\right)$。

根据谱定理,对称矩阵存在一组特征向量构成标准正交基,且一定能对角化。根据定理4.14,我们构造半正定矩阵 $\boldsymbol{A}^{\top} \boldsymbol{A} \in \mathbb{R}^{n \times n}$:

$$ \boldsymbol{A}^{\top} \boldsymbol{A}=\boldsymbol{P} \boldsymbol{D} \boldsymbol{P}^{\top}=\boldsymbol{P}\left[\begin{array}{ccc}{\lambda_{1}} & {\cdots} & {0} \\ {\vdots} & {\ddots} & {\vdots} \\ {0} & {\cdots} & {\lambda_{n}}\end{array}\right] \boldsymbol{P}^{\top} $$

其中 $\boldsymbol{P}$ 是正交矩阵,由标准正交的特征向量组成。假设 $\boldsymbol{A}$ 存在SVD分解,则

$$ \boldsymbol{A}^{\top} \boldsymbol{A}=\left(\boldsymbol{U} \boldsymbol{\Sigma} \boldsymbol{V}^{\top}\right)^{\top}\left(\boldsymbol{U} \boldsymbol{\Sigma} \boldsymbol{V}^{\top}\right)=\boldsymbol{V} \boldsymbol{\Sigma}^{\top} \boldsymbol{U}^{\top} \boldsymbol{U} \boldsymbol{\Sigma} \boldsymbol{V}^{\top}=\boldsymbol{V}\left[\begin{array}{ccc}{\sigma_{1}^{2}} & {0} & {0} \\ {0} & {\ddots} & {0} \\ {0} & {0} & {\sigma_{n}^{2}}\end{array}\right] \boldsymbol{V}^{\top} $$

比较可得

$$ \begin{aligned} \boldsymbol{V}^{\top} &=\boldsymbol{P}^{\top} \\ \sigma_{i}^{2} &=\lambda_{i} \end{aligned} $$

因此,$\boldsymbol{A}^{\top}\boldsymbol{A}$ 的特征向量 $\boldsymbol{P}$ 是 $\boldsymbol{A}$ 的右奇异向量 $\boldsymbol{V}$,$\boldsymbol{A}^{\top} \boldsymbol{A}$ 的特征值是 $\boldsymbol{A}$ 的奇异值 $\boldsymbol{\Sigma}$ 的平方。

使用类似过程求解左奇异向量:

$$ \boldsymbol{A} \boldsymbol{A}^{\top}=\left(\boldsymbol{U} \boldsymbol{\Sigma} \boldsymbol{V}^{\top}\right)\left(\boldsymbol{U} \boldsymbol{\Sigma} \boldsymbol{V}^{\top}\right)^{\top}=\boldsymbol{U} \boldsymbol{\Sigma} \boldsymbol{V}^{\top} \boldsymbol{V} \boldsymbol{\Sigma}^{\top} \boldsymbol{U}^{\top}=\boldsymbol{U}\left[\begin{array}{ccc}{\sigma_{1}^{2}} & {0} & {0} \\ {0} & {\ddots} & {0} \\ {0} & {0} & {\sigma_{m}^{2}}\end{array}\right] \boldsymbol{U}^{\top} $$

$\boldsymbol{A} \boldsymbol{A}^{\top}$ 的标准正交特征向量是 $\boldsymbol{A}$ 的左奇异向量 $\boldsymbol{U}$。

定理4.23

设 $\boldsymbol{A}\in \mathbb{R}^{m \times n}$,则 $\boldsymbol{A}^{\top}\boldsymbol{A}$ 与 $\boldsymbol{A}\boldsymbol{A}^{\top}$ 具有相同的非零特征值,且如果 $\boldsymbol{v}$ 是 $\boldsymbol{A}^{\top}\boldsymbol{A}$ 的特征向量,则 $\boldsymbol{A}\boldsymbol{v}$ 是 $\boldsymbol{A}\boldsymbol{A}^{\top}$ 的特征向量。

证明:令 $\lambda$ 是 $\boldsymbol{A}^{\top}\boldsymbol{A}$ 的非零特征值,$\boldsymbol{v}$ 是与 $\lambda$ 相关的特征向量,则 $\boldsymbol{A}^{\top}\boldsymbol{A}\boldsymbol{v}=\lambda\boldsymbol{v}$,由

$$ \left(\boldsymbol{A}\boldsymbol{A}^{\top}\right)\left(\boldsymbol{A}\boldsymbol{v}\right)=\boldsymbol{A}\left(\boldsymbol{A}^{\top}\boldsymbol{A}\boldsymbol{v}\right)=\boldsymbol{A}\left(\lambda\boldsymbol{v}\right)=\lambda\left(\boldsymbol{A}\boldsymbol{v}\right) $$

可得 $\boldsymbol{A}\boldsymbol{v}$ 是 $\boldsymbol{A}\boldsymbol{A}^{\top}$ 关于特征值 $\lambda$ 的特征向量。

因此左奇异向量可以通过以下方式获得:

$$ \boldsymbol{u}_{i} :=\frac{\boldsymbol{A} \boldsymbol{v}_{i}}{\left\|\boldsymbol{A} \boldsymbol{v}_{i}\right\|}=\frac{1}{\sqrt{\lambda_{i}}} \boldsymbol{A} \boldsymbol{v}_{i}=\frac{1}{\sigma_{i}} \boldsymbol{A} \boldsymbol{v}_{i} $$

若 $m>n$,则对 $n < i \leqslant m$,有 $\boldsymbol{u}_{i}=\boldsymbol{0}$。

例如,对矩阵 $\boldsymbol{A}=\left[\begin{array}{ccc}{1} & {0} & {1} \\ {-2} & {1} & {0}\end{array}\right]$ 进行奇异值分解:

  • 求右奇异向量

$$ \boldsymbol{A}^{\top} \boldsymbol{A}=\left[\begin{array}{cc}{1} & {-2} \\ {0} & {1} \\ {1} & {0}\end{array}\right]\left[\begin{array}{ccc}{1} & {0} & {1} \\ {-2} & {1} & {0}\end{array}\right]=\left[\begin{array}{ccc}{5} & {-2} & {1} \\ {-2} & {1} & {0} \\ {1} & {0} & {1}\end{array}\right] $$

对 $\boldsymbol{A}^{\top}\boldsymbol{A}$ 进行特征分解:

$$ \boldsymbol{A}^{\top} \boldsymbol{A}=\left[\begin{array}{ccc}{\frac{5}{\sqrt{30}}} & {0} & {\frac{-1}{\sqrt{6}}} \\ {\frac{30}{\sqrt{30}}} & {\frac{1}{\sqrt{5}}} & {\frac{-2}{\sqrt{6}}} \\ {\frac{1}{\sqrt{30}}} & {\frac{2}{\sqrt{5}}} & {\frac{1}{\sqrt{6}}}\end{array}\right]\left[\begin{array}{ccc}{6} & {0} & {0} \\ {0} & {1} & {0} \\ {0} & {0} & {0}\end{array}\right]\left[\begin{array}{ccc}{\frac{5}{\sqrt{30}}} & {\frac{-2}{\sqrt{30}}} & {\frac{1}{\sqrt{30}}} \\ {0} & {\frac{1}{\sqrt{5}}} & {\frac{2}{\sqrt{5}}} \\ {\frac{-1}{\sqrt{6}}} & {\frac{-2}{\sqrt{6}}} & {\frac{1}{\sqrt{6}}}\end{array}\right]=\boldsymbol{P D P}^{\top} $$

因此右奇异向量为

$$ \boldsymbol{V}=\boldsymbol{P}=\left[\begin{array}{ccc}{\frac{5}{\sqrt{30}}} & {0} & {\frac{-1}{\sqrt{6}}} \\ {\frac{-2}{\sqrt{30}}} & {\frac{1}{\sqrt{5}}} & {\frac{-2}{\sqrt{6}}} \\ {\frac{1}{\sqrt{30}}} & {\frac{2}{\sqrt{5}}} & {\frac{1}{\sqrt{6}}}\end{array}\right] $$

  • 求奇异值矩阵

对 $\boldsymbol{A}^{\top}\boldsymbol{A}$ 的特征值进行开方得到 $\boldsymbol{A}$ 的奇异值为

$$ \boldsymbol{\Sigma}=\left[\begin{array}{ccc}{\sqrt{6}} & {0} & {0} \\ {0} & {1} & {0}\end{array}\right] $$

  • 求左奇异向量

$$ \begin{array}{l}{\boldsymbol{u}_{1}=\frac{1}{\sigma_{1}} \boldsymbol{A} \boldsymbol{v}_{1}=\frac{1}{\sqrt{6}}\left[\begin{array}{ccc}{1} & {0} & {1} \\ {-2} & {1} & {0}\end{array}\right]\left[\begin{array}{c}{\frac{5}{\sqrt{30}}} \\ {\frac{-2}{\sqrt{30}}} \\ {\frac{1}{\sqrt{30}}}\end{array}\right]=\left[\begin{array}{c}{\frac{1}{\sqrt{5}}} \\ {-\frac{2}{\sqrt{5}}}\end{array}\right]} \\ {\boldsymbol{u}_{2}=\frac{1}{\sigma_{2}} \boldsymbol{A} \boldsymbol{v}_{2}=\frac{1}{1}\left[\begin{array}{ccc}{1} & {0} & {1} \\ {-2} & {1} & {0}\end{array}\right]\left[\begin{array}{c}{0} \\ {\frac{1}{\sqrt{5}}} \\ {\frac{2}{\sqrt{5}}}\end{array}\right]=\left[\begin{array}{c}{\frac{2}{\sqrt{5}}} \\ {\frac{1}{\sqrt{5}}}\end{array}\right]}\end{array} $$

因此左奇异向量为

$$ \boldsymbol{U}=\left[\boldsymbol{u}_{1}, \boldsymbol{u}_{2}\right]=\left[\begin{array}{cc}{\frac{1}{\sqrt{5}}} & \frac{2}{\sqrt{5}} \\ {-\frac{2}{\sqrt{5}}} & \frac{1}{\sqrt{5}} \end{array}\right] $$

因此 $\boldsymbol{A}$ 的SVD分解为

$$ \boldsymbol{A}=\boldsymbol{U\Sigma V^{\top}}=\left[\begin{array}{cc}{\frac{1}{\sqrt{5}}} & \frac{2}{\sqrt{5}} \\ {-\frac{2}{\sqrt{5}}} & \frac{1}{\sqrt{5}} \end{array}\right]\left[\begin{array}{ccc}{\sqrt{6}} & {0} & {0} \\ {0} & {1} & {0}\end{array}\right]\left[\begin{array}{ccc}{\frac{5}{\sqrt{30}}} & {\frac{-2}{\sqrt{30}}} & {\frac{1}{\sqrt{30}}} \\ {0} & {\frac{1}{\sqrt{5}}} & {\frac{2}{\sqrt{5}}} \\ {\frac{-1}{\sqrt{6}}} & {\frac{-2}{\sqrt{6}}} & {\frac{1}{\sqrt{6}}}\end{array}\right] $$

4.6 矩阵近似(Matrix Approximation)

对于矩阵 $\boldsymbol{A}=\boldsymbol{U} \boldsymbol{\Sigma} \boldsymbol{V}^{\top} \in \mathbb{R}^{m \times n}$,定义rank-1矩阵 $\boldsymbol{A}_{i} \in \mathbb{R}^{m \times n}$ 为:

$$ \boldsymbol{A}_{i} :=\boldsymbol{u}_{i} \boldsymbol{v}_{i}^{\top} $$

其中 $\boldsymbol{u}_{i},\boldsymbol{v}_{i}$ 分别是 $\boldsymbol{U}$ 和 $\boldsymbol{V}$ 的第 $i$ 个正交列向量,$\boldsymbol{A}_i$ 定义为它们的外积。下面展示了一些巨石阵图像 $\boldsymbol{A} \in \mathbb{R}^{1432 \times 1910}$ 的 $\boldsymbol{A}_i$:

10.png

秩为 $r$ 的矩阵 $\boldsymbol{A} \in \mathbb{R}^{m \times n}$ 可以写作rank-1矩阵之和:

$$ \boldsymbol{A}=\sum_{i=1}^{r} \sigma_{i} \boldsymbol{u}_{i} \boldsymbol{v}_{i}^{\top}=\sum_{i=1}^{r} \sigma_{i} \boldsymbol{A}_{i} $$

如果我们不计算所有 $r$ 个矩阵之和,而只计算 $k<r$ 个矩阵之和,则可以得到矩阵的rank-k近似:

$$ \widehat{\boldsymbol{A}}(k) :=\sum_{i=1}^{k} \sigma_{i} \boldsymbol{u}_{i} \boldsymbol{v}_{i}^{\top}=\sum_{i=1}^{k} \sigma_{i} \boldsymbol{A}_{i} $$

其中 $\operatorname{rk}(\widehat{\boldsymbol{A}}(k))=k$。下图展示了一些巨石阵图像 $\boldsymbol{A} \in \mathbb{R}^{1432 \times 1910}$ 的rank-k近似:

11.png

近似之前需要 $1,432 \cdot 1,910=2,735,120$ 个数字来表示图像,而近似之后只需要 $5 \cdot(1,432+1,910+1)=16,715$ 个数字,大约只有原来的 0.6%。

定义4.24 矩阵的谱范数(Spetral Norm)

对于向量 $\boldsymbol{x} \in \mathbb{R}^{n} \backslash\{\mathbf{0}\}$,矩阵 $\boldsymbol{A} \in \mathbb{R}^{m \times n}$ 的谱范数定义为

$$ \|\boldsymbol{A}\|_{2} :=\max _{\boldsymbol{x}} \frac{\|\boldsymbol{A} \boldsymbol{x}\|_{2}}{\|\boldsymbol{x}\|_{2}} $$

谱范数决定了任意向量 $\boldsymbol{x}$ 与 $\boldsymbol{A}$ 相乘后能变长的最大限度。

定理4.25

矩阵 $\boldsymbol{A}$ 的谱范数等于它的最大奇异值 $\sigma_1$。

定理4.26 Eckart-Young定理

对于秩为 $r$ 的矩阵 $\boldsymbol{A} \in \mathbb{R}^{m \times n}$,令 $\boldsymbol{B} \in \mathbb{R}^{m \times n}$ 是秩为 $k$ 的矩阵,则对于任意 $k \leqslant r$,$\widehat{A}(k)=\sum_{i=1}^{k} \sigma_{i} \boldsymbol{u}_{i} \boldsymbol{v}_{i}^{\top}$,以下结论成立:

$$ \widehat{\boldsymbol{A}}(k)=\operatorname{argmin}_{\mathrm{rk}(\boldsymbol{B}) \leqslant k}\|\boldsymbol{A}-\boldsymbol{B}\|_{2} \\ \|\boldsymbol{A}-\widehat{\boldsymbol{A}}(k)\|_{2}=\sigma_{k+1} $$

Eckart-Young定理告诉我们,当我们使用rank-k近似矩阵 $\boldsymbol{A}$ 时,引入的误差有多大。该定理表明,我们可以使用SVD将秩为 $r$ 的矩阵 $\boldsymbol{A}$ 降到秩为 $k$ 的矩阵 $\hat{\boldsymbol{A}}$,并且这种近似过程是最优(误差最小)的。

我们可以将低秩矩阵近似视为一种有损压缩,它在许多机器学习问题中有所应用,如图像处理、噪声过滤、不适定问题(ill-posed problem)的正则化等。除此之外,低秩矩阵近似在降维和主成分分析中起关键作用。

4.7 矩阵的种系(Matrix Phylogeny)

12.png

Last modification:September 15th, 2019 at 04:39 pm
如果觉得我的文章对你有用,请随意赞赏