线性代数的本质(十)——矩阵分解

矩阵分解

矩阵的因式分解是把矩阵表示为多个矩阵的乘积，这种结构更便于理解和计算。

LU分解

设 $A$ 是 $m\times n$ 矩阵，若 $A$ 可以写成乘积
$$A=LU$$
其中，$L$ 为 $m$ 阶下三角方阵，主对角线元素全是1。$U$ 为 $A$ 得到一个行阶梯形矩阵。这样一个分解称为LU分解。 $L$ 称为单位下三角方阵。

我们先来看看，LU分解的一个应用。当 $A=LU$ 时，方程 $A\mathbf{x}=\mathbf{b}$ 可写成 $L(U\mathbf{x})=\mathbf{b}$，于是分解为下面两个方程
$$\begin{gathered} L\mathbf{y}=\mathbf{b} \\ U\mathbf{x}=\mathbf{y} \end{gathered}$$
因为 $L$ 和 $U$ 都是三角矩阵，每个方程都比较容易解。

LU 分解算法：本节只讲述仅用行倍加变换求解。可以证明，单位下三角矩阵的乘积和逆也是单位下三角矩阵 。此时，可以用行倍加变换寻找 $L$ 和 $U$ 。假设存在单位下三角初等矩阵 $P_1,\cdots ,P_s$ 使
$$P_1\cdots P_{s}A=U$$
于是便得到了 $U$ 和 $L$
$$L=(P_1,\cdots ,P_s{)}^{-1}$$

QR分解

如果 $m\times n$ 矩阵 $A$ 的列向量线性无关，那么 $A$ 可以分解为 $A=QR$，其中 $Q$ 是一个 $m\times n$ 正交矩阵，其列为 $\text{col }A$ 的一组标准正交基，$R$ 是一个上 $n\times n$ 三角可逆矩阵，且其对角线上的元素全为正数。

证：矩阵 $A=({\mathbf{x}}_1,{\mathbf{x}}_2,\cdots ,{\mathbf{x}}_n)$ 的列向量是 $\text{col }A$ 的一组基，使用施密特正交化方法可以构造一组标准正交基 ${\mathbf{u}}_1,{\mathbf{u}}_2,\cdots ,{\mathbf{u}}_n$ ，取
$$Q=({\mathbf{u}}_1,{\mathbf{u}}_2,\cdots ,{\mathbf{u}}_n)$$
因为在正交化过程中 x k ∈ span { x 1 , ⋯ , x k } = span { u 1 , ⋯ , u k } , k = 1 , 2 , ⋯ , n \mathbf x_k\in\text{span}\{\mathbf x_1,\cdots,\mathbf x_k\}=\text{span}\{\mathbf u_1,\cdots,\mathbf u_k\},\quad k=1,2,\cdots,n xk​∈span{x1​,⋯,xk​}=span{u1​,⋯,uk​},k=1,2,⋯,n 。所以 ${\mathbf{x}}_k$ 可线性表示为
$${\mathbf{x}}_k=r_{1k}{\mathbf{u}}_1+\cdots +r_{kk}{\mathbf{u}}_k+0\cdot {\mathbf{u}}_{k+1}+\cdots +0\cdot {\mathbf{u}}_n$$
于是
$${\mathbf{x}}_k=Q{\mathbf{r}}_k$$
其中 ${\mathbf{r}}_k=(r_{1k},\cdots ,r_{kk},0,\cdots ,0{)}^T$ ，且 $r_{kk}⩾0$ (在正交化过程中，若 $r_{kk}<0$ ，则$r_{kk}$ 和 ${\mathbf{u}}_k$ 同乘-1)。取 $R=({\mathbf{r}}_1,{\mathbf{r}}_2,\cdots ,{\mathbf{r}}_n)$ ，则
$$A=(Q{\mathbf{r}}_1,Q{\mathbf{r}}_2,\cdots ,Q{\mathbf{r}}_n)=QR$$
例：求 $A=\left[\begin{array}{ccc}1& 0& 0\\ 1& 1& 0\\ 1& 1& 1\\ 1& 1& 1\end{array}\right]$ 的一个 QR 分解

解：通过施密特正交化方法我们可以得到 $\text{col }A$ 的一组标准正交基，将这些向量组成矩阵
$$Q=\left[\begin{array}{ccc}1/2& -3/\sqrt{12}& 0\\ 1/2& 1/\sqrt{12}& -2/\sqrt{6}\\ 1/2& 1/\sqrt{12}& 1/\sqrt{6}\\ 1/2& 1/\sqrt{12}& 1/\sqrt{6}\end{array}\right]$$
注意到 $Q$ 是正交矩阵，$Q^T=Q^{-1}$ 。所以 $R=Q^{-1}A=Q^{T}A$
$$R=\left[\begin{array}{cccc}1/2& 1/2& 1/2& 1/2\\ -3/\sqrt{12}& 1/\sqrt{12}& 1/\sqrt{12}& 1/\sqrt{12}\\ 0& -2/\sqrt{6}& 1/\sqrt{6}& 1/\sqrt{6}\end{array}\right]\left[\begin{array}{ccc}1& 0& 0\\ 1& 1& 0\\ 1& 1& 1\\ 1& 1& 1\end{array}\right]=\left[\begin{array}{ccc}2& 3/2& 1\\ 0& 3/\sqrt{12}& 2/\sqrt{12}\\ 0& 0& 2/\sqrt{6}\end{array}\right]$$

特征值分解

特征值分解是将矩阵分解成特征值和特征向量形式：
$$A=Q\Sigma Q^{-1}$$
其中，$\Sigma =\text{diag}({\lambda }_1,{\lambda }_2,\cdots ,{\lambda }_n)$ 是一个对角阵，其对角线元素是矩阵 $A$ 的特征值按降序排列 ${\lambda }_1⩾{\lambda }_2⩾\cdots ⩾{\lambda }_n$，$Q=({\mathbf{u}}_1,{\mathbf{u}}_2,\dots ,{\mathbf{u}}_n)$ 是特征值对应的特征向量组成的矩阵。

特征值分解后，方阵的幂变得更容易计算
$$A^t=Q{\Sigma }^t{Q}^{-1}=Q\left[\begin{array}{ccc}{\lambda }_1^t& & \\ & \ddots & \\ & & {\lambda }_n^t\end{array}\right]Q^{-1}$$
特征值分解可以理解为：先切换基向量，然后伸缩变换，最后再切换回原来的基向量。其中，$\Sigma$ 中的特征向量描述伸缩变换的程度，特征向量描述变换的方向。

特征值分解有一定的局限性，因为它只适用于满秩的方阵。

例：求矩阵 $A=\left[\begin{array}{ccc}-2& 1& 1\\ 0& 2& 0\\ -4& 1& 3\end{array}\right]$ 的特征值分解。

解：矩阵 $A$ 的特征多项式为 $\det (A-\lambda I)=-(\lambda -2{)}^2(\lambda +1)$ 。特征值和特征向量分别为
$${\lambda }_1=-1:{\mathbf{u}}_1=\left[\begin{array}{c}1\\ 0\\ 1\end{array}\right];{\lambda }_2=2:{\mathbf{u}}_2=\left[\begin{array}{c}0\\ 1\\ -1\end{array}\right],{\mathbf{u}}_3=\left[\begin{array}{c}1\\ 0\\ 4\end{array}\right]$$
可通过行变换计算逆矩阵
$$(Q,I)=\left[\begin{array}{c}\begin{array}{cccccc}0& 1& 1& 1& 0& 0\\ 1& 0& 0& 0& 1& 0\\ -1& 4& 1& 0& 0& 1\end{array}\end{array}\right]\to \left[\begin{array}{c}\begin{array}{cccccc}1& 0& 0& 0& 1& 0\\ 0& 1& 0& -1/3& 1/3& 1/3\\ 0& 0& 1& 4/3& -1/3& -1/3\end{array}\end{array}\right]=(I,Q^{-1})$$
所以
$$A=\left[\begin{array}{ccc}0& 1& 1\\ 1& 0& 0\\ -1& 4& 1\end{array}\right]\left[\begin{array}{ccc}2& 0& 0\\ 0& 2& 0\\ 0& 0& -1\end{array}\right]\left[\begin{array}{ccc}0& 1& 0\\ -1/3& 1/3& 1/3\\ 4/3& -1/3& -1/3\end{array}\right]$$

奇异值分解

奇异值分解

奇异值分解(Singular Value Decomposition, SVD)是线性代数中一种重要的矩阵分解，在生物信息学、信号处理、金融学、统计学等领域有重要应用。

SVD 可以理解为同一线性变换 $T:{\mathbb{R}}^n\mapsto {\mathbb{R}}^m$ 在不同基下的矩阵表示。假设 Grant 选用标准基，对应的矩阵为 $A_{m\times n}$ 。类似于特征值分解， Jennifer 通过选择合适的基向量，对应的矩阵变为简单的长方形对角矩阵 ${\Sigma }_{m\times n}$，即只有伸缩变换。

假定 Jennifer 使用矩阵 $V_n=({\mathbf{v}}_1,\cdots ,{\mathbf{v}}_n)$ 的列向量作为 $R^n$ 的基，使用矩阵 $U_n=({\mathbf{u}}_1,\cdots ,{\mathbf{u}}_m)$的列向量作为 $R^m$ 的基 。那么，对于 Jennifer 视角下的向量 $\mathbf{x}\in R^n$

1. 同样的向量，用 Grant 的坐标系表示为 $V\mathbf{x}$
2. 用 Grant 的语言描述变换后的向量 $AV\mathbf{x}$
3. 将变换后的结果变回 Jennifer 的坐标系 $U^{-1}AV\mathbf{x}$

于是，我们得到同一个线性变换 $T$ 在 Jennifer 的坐标系下对应的矩阵 $\Sigma =U^{-1}AV$ ，也可理解为矩阵 $A$ 分解为 $A_{m\times n}=U_m{\Sigma }_{m\times n}{V}_n^{-1}$ 。

接下来，自然是探讨上述矩阵分解的适用条件。

注意到
$$A^{T}A=(U\Sigma V^{-1}{)}^T(U\Sigma V^{-1})=V^{-T}{\Sigma }^T{U}^{T}U\Sigma V^{-1}$$
不妨取 $U,V$ 为单位正交基，即$U,V$ 为正交矩阵 $U^{T}U=I,V^{T}V=I$ ，则
$$A^{T}A=V{\Sigma }^T\Sigma V^T$$
于是，可知 $V$ 的列向量为 $A^{T}A$ 的特征向量，${\Sigma }^T\Sigma$ 为$n$ 阶对角阵，其对角元素为$A^{T}A$ 的特征值。事实上 $A^{T}A$ 为对称阵，必定存在正交矩阵 $V$ 相似对角化。

同理
$$A{A}^T=U\Sigma {\Sigma }^T{U}^T$$
可知 $U$ 的列向量为 $A{A}^T$ 的特征向量，$\Sigma {\Sigma }^T$ 为$m$ 阶对角阵，其对角元素为$A{A}^T$ 的特征值。矩阵 $A^{T}A$ 为对称阵，必定存在正交矩阵 $U$ 相似对角化。

目前 $U,V$ 我们都求出来了，只剩下求出长方形对角矩阵 $\Sigma$ 。根据 Sylvester降幂公式， $A^{T}A$ 和 $A{A}^T$ 有相同的非零特征值。

令 $\Sigma =\left[\begin{array}{cc}{\Lambda }_r& O\\ O& O\end{array}\right]$ ，其中 ${\Lambda }_r=\text{diag}({\sigma }_1,\cdots ,{\sigma }_r)$ 。则
$${\Sigma }^T\Sigma ={\left[\begin{array}{cc}{\Lambda }_r^2& O\\ O& O\end{array}\right]}_n,\Sigma {\Sigma }^T={\left[\begin{array}{cc}{\Lambda }_r^2& O\\ O& O\end{array}\right]}_m$$
其中 ${\Lambda }_r^2=\text{diag}({\sigma }_1^2,\cdots ,{\sigma }_r^2)$ 。因此，矩阵 $\Sigma$ 的对角元素是 $A^{T}A$ 和 $A{A}^T$ 的特征值 ${\lambda }_j$ 的平方根
$${\sigma }_j=\sqrt{{\lambda }_j}$$
综上，任意矩阵均可奇异值分解。

定义：SVD是指将秩为 $r$ 的 $m\times n$ 矩阵$A$分解为
$$A=U\Sigma V^T$$

其中 $U$ 为 $m$ 阶正交阵， $V$ 为 $n$ 阶正交阵，$\Sigma$ 为 $m\times n$ 维长方形对角矩阵，对角元素称为矩阵 $A$ 的奇异值，一般按降序排列 ${\sigma }_1⩾{\sigma }_2⩾\cdots ⩾{\sigma }_r>0$ ，这样 $\Sigma$ 就唯一确定了。矩阵 $U$ 的列向量称为左奇异向量(left singular vector)，矩阵 $V$ 的列向量称为右奇异向量(right singular vector)。

例：这里我们用一个简单的矩阵来说明奇异值分解的步骤。求矩阵 $A=\left[\begin{array}{cc}0& 1\\ 1& 1\\ 1& 0\end{array}\right]$ 的奇异值分解

解：首先求出对称阵 $A^{T}A$ 和 $A{A}^T$
$$\begin{gathered} A^{T}A=\left[\begin{array}{ccc}0& 1& 1\\ 1& 1& 0\end{array}\right]\left[\begin{array}{cc}0& 1\\ 1& 1\\ 1& 0\end{array}\right]=\left[\begin{array}{cc}2& 1\\ 1& 2\end{array}\right] \\ A{A}^T=\left[\begin{array}{cc}0& 1\\ 1& 1\\ 1& 0\end{array}\right]\left[\begin{array}{ccc}0& 1& 1\\ 1& 1& 0\end{array}\right]=\left[\begin{array}{ccc}1& 1& 0\\ 1& 2& 1\\ 0& 1& 1\end{array}\right] \end{gathered}$$
然后求出 $A^{T}A$ 的特征值和特征向量
$${\lambda }_1=3:{\mathbf{v}}_1=\left[\begin{array}{c}1/\sqrt{2}\\ 1/\sqrt{2}\end{array}\right];{\lambda }_2=1:{\mathbf{v}}_2=\left[\begin{array}{c}-1/\sqrt{2}\\ 1/\sqrt{2}\end{array}\right]$$
求出 $A{A}^T$ 的特征值和特征向量
$${\lambda }_1=3:{\mathbf{u}}_1=\left[\begin{array}{c}1/\sqrt{6}\\ 2/\sqrt{6}\\ 1/\sqrt{6}\end{array}\right];{\lambda }_2=1:{\mathbf{u}}_2=\left[\begin{array}{c}1/\sqrt{2}\\ 0\\ -1/\sqrt{2}\end{array}\right];{\lambda }_3=0:{\mathbf{u}}_3=\left[\begin{array}{c}1/\sqrt{3}\\ -1/\sqrt{3}\\ 1/\sqrt{3}\end{array}\right];$$
其次可以利用 ${\sigma }_i=\sqrt{{\lambda }_i}$ 求出奇异值 $\sqrt{3},1$

最终得到$A$的奇异值分解
$$A=U\Sigma V^T=\left[\begin{array}{ccc}1/\sqrt{6}& 1/\sqrt{2}& 1/\sqrt{3}\\ 2/\sqrt{6}& 0& -1/\sqrt{3}\\ 1/\sqrt{6}& -1/\sqrt{2}& 1/\sqrt{3}\end{array}\right]\left[\begin{array}{cc}\sqrt{3}& 0\\ 0& 1\\ 0& 0\end{array}\right]\left[\begin{array}{cc}1/\sqrt{2}& 1/\sqrt{2}\\ -1/\sqrt{2}& 1/\sqrt{2}\end{array}\right]$$

矩阵的基本子空间

设矩阵 $A=U\Sigma V^T$ ，有$r$ 个不为零的奇异值，则可以得到矩阵 $A$ 的四个基本子空间：

1. 正交阵 $U$ 的前 $r$ 列是 $\text{col }A$ 的一组单位正交基
2. 正交阵 $U$ 的后 $m-r$ 列是 $\ker A^T$ 的一组单位正交基
3. 正交阵 $V$ 的前 $r$ 列是 $\text{col }{A}^T$ 的一组单位正交基
4. 正交阵 $V$ 的后 $n-r$ 列是 $\ker A$ 的一组单位正交基

$$A(\underset{\text{col }{A}^T}{\underbrace{{\mathbf{v}}_1,\cdots ,{\mathbf{v}}_r}},\underset{\ker A}{\underbrace{{\mathbf{v}}_{r+1}\cdots {\mathbf{v}}_n}})=(\underset{\text{col }A}{\underbrace{{\mathbf{u}}_1,\cdots ,{\mathbf{u}}_r}},\underset{\ker A^T}{\underbrace{{\mathbf{u}}_{r+1}\cdots {\mathbf{u}}_m}})\underset{{\Sigma }_{m\times n}}{\underbrace{\left[\begin{array}{cccc}{\sigma }_1& & & \\ & \ddots & & \\ & & {\sigma }_r& \\ & & & O\end{array}\right]}}$$

证：易知 $AV=U\Sigma$ ，即
$$\{\begin{array}{ll}A{\mathbf{v}}_i={\sigma }_i{\mathbf{u}}_i,& 1⩽i⩽r\\ A{\mathbf{v}}_i=0,& r<i⩽n\end{array}$$
取 ${\mathbf{v}}_1,\cdots ,{\mathbf{v}}_n$ 为 ${\mathbb{R}}^n$ 的单位正交基，对于 $\forall \mathbf{x}\in {\mathbb{R}}^n$ ，可以写出 $\mathbf{x}=c_1{\mathbf{v}}_1+\cdots +c_n{\mathbf{v}}_n$，于是
$$\begin{array}{rl}A\mathbf{x}& =c_{1}A{\mathbf{v}}_1+\cdots +c_{r}A{\mathbf{v}}_r+c_{r+1}A{\mathbf{v}}_{r+1}+\cdots +c_n{\mathbf{v}}_n\\ & =c_1{\sigma }_1{\mathbf{u}}_1+\cdots +c_r{\sigma }_1{\mathbf{u}}_r+0+\cdots +0\end{array}$$
所以 A x ∈ span { u 1 , ⋯ , u r } A\mathbf x\in\text{span}\{\mathbf u_1,\cdots,\mathbf u_r\} Ax∈span{u1​,⋯,ur​} ，这说明矩阵 $U$ 的前 $r$ 列是 $\text{col }A$ 的一组单位正交基，因此 $\text{rank }A=r$ 。同时可知，对于任意的 x ∈ span { v r + 1 , ⋯ , v n } ⟺ A x = 0 \mathbf x\in\text{span}\{\mathbf v_{r+1},\cdots,\mathbf v_n\}\iff A\mathbf x=0 x∈span{vr+1​,⋯,vn​}⟺Ax=0 ，于是 $V$ 的后 $n-r$ 列是 $\ker A$ 的一组单位正交基。

同样通过 $A^{T}U=V\Sigma$ 可说明 $V$ 的前 $r$ 列是 $\text{col }{A}^T$ 的一组单位正交基， $U$ 的后 $m-r$ 列是 $\ker A^T$ 的一组单位正交基。

奇异值分解的性质

设矩阵 $A=U\Sigma V^T$ ，秩 $\text{rank }A=r$ ，分别将 $U,\Sigma ,V$ 进行分块
$$\begin{gathered} U=(U_r,U_{m-r}) \\ V=(V_r,V_{n-r}) \\ \Sigma =\left[\begin{array}{cc}{\Lambda }_r& O\\ O& O\end{array}\right] \end{gathered}$$
其中 $U_r=({\mathbf{u}}_1,\cdots ,{\mathbf{u}}_r)$ 为 $m\times r$维矩阵， $V_r=({\mathbf{v}}_1,\cdots ,{\mathbf{v}}_r)$ 为 $n\times r$维矩阵，${\Lambda }_r=\text{diag}({\sigma }_1,\cdots ,{\sigma }_r)$ 为 $r$ 阶对角阵。应用矩阵乘法的性质，奇异值分解可以简化为
$$A=U_r{\Lambda }_r{V}_r^T$$
这个分解称为简化奇异值分解。

性质：

1. 奇异值分解可理解为将线性变换分解为三个简单的变换：正交变换 $V^T$，伸缩变换 $\Sigma$ 和正交变换 $U$ 。
2. 矩阵 $A$ 的奇异值分解中，奇异值是唯一的，但矩阵 $U,V$ 不是唯一的。
3. 令 $\lambda$ 为$A^{T}A$ 的一个特征值，$\mathbf{v}$ 是对应的特征向量，则
   $$\Vert A\mathbf{v}{\Vert }^2={\mathbf{v}}^T{A}^{T}A\mathbf{v}=\lambda {\mathbf{v}}^T\mathbf{v}=\lambda \Vert \mathbf{v}\Vert$$
4. 易知 $AV=U\Sigma$ 或 $A^{T}U=V{\Sigma }^T$，则左奇异向量和右奇异向量存在关系
   $$\begin{gathered} A{\mathbf{v}}_j={\sigma }_j{\mathbf{u}}_j \\ {A}^T{\mathbf{u}}_j={\sigma }_j{\mathbf{v}}_j \end{gathered}$$

矩阵的外积展开式

矩阵 $A=U\Sigma V^T$ 可展开为若干个秩为1的 $m\times n$矩阵之和
$$A={\sigma }_1{\mathbf{u}}_1{\mathbf{v}}_1^T+{\sigma }_2{\mathbf{u}}_2{\mathbf{v}}_2^T+\cdots +{\sigma }_r{\mathbf{u}}_r{\mathbf{v}}_r^T$$

上式称为矩阵 $A$ 的外积展开式。

在长方形对角矩阵 $\Sigma$ 中奇异值按从大到小的顺序排列 ${\sigma }_1⩾{\sigma }_2⩾\cdots ⩾{\sigma }_r>0$ 。在很多情况下，由于奇异值递减很快，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上。因此，我们可以用前面 $k$ 个大的奇异值来近似描述矩阵。

奇异值分解也是一种矩阵近似的方法，这个近似是在矩阵范数意义下的近似。矩阵范数是向量范数的直接推广。
$$\Vert A{\Vert }_2=(\sum _{j=1}^n\sum _{i=1}^m|a_{ij}{|}^2{)}^{1/2}$$
可以证明
$$\Vert A{\Vert }_2^2=\text{tr}(A^{T}A)=\sum _{i=1}^r{\sigma }_i^2$$
设矩阵
$$A_k=\sum _{i=1}^k{\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^T$$
则 $A_k$ 的秩为 $k$ ，矩阵 $A_k$ 称为 $A$ 的截断奇异值分解。并且 $A_k$ 是秩为 $k$ 时的最优近似，即 $A_k$ 为以下最优问题的解
$$\begin{gathered} \min \Vert A-X{\Vert }_2 \\ \text{s.t. rank }A=k \end{gathered}$$
上式称为低秩近似(low-rank approximation)。于是奇异值分解可近似为
$$A\approx \sum _{i=1}^k{\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^T=U_{m\times k}{\Sigma }_{k\times k}{V}_{n\times k}^T$$

其中 $k$ 是一个远远小于$m$和$n$的数，从计算机内存的角度来说，矩阵左(右)奇异向量和奇异值的存储要远远小于矩阵$A$的。所以，截断奇异值分解就是在计算精度和时间空间之间做选择。如果$k$越大，右边的三个矩阵相乘的结果越接近于$A$。

截断奇异值分解常用于图像压缩，如下图