[人工智能]常见的矩阵分解有**LU分解**、**QR分解**、**Cholesky分解**、**Schur分解**、**SVD奇异分解**

求解线性方程组：$Ax=b$，其解可以表示为 $x=A\backslash b$.

为了提高运算速度，节约存储空间，通常会采用矩阵分解的方案，常见的矩阵分解有LU分解、QR分解、Cholesky分解、Schur分解、SVD奇异分解等。这里简单介绍几种。

• LU分解：如果方阵A是非奇异的，LU分解总可进行。一个矩阵可以表示为一个交换下三角矩阵和一个上三角矩阵的乘机。更整洁的形式是：一个矩阵可以表示为一个上三角矩阵和一个下三角矩阵以及一个置换矩阵的形式，即：$PX=LU$，从而方程的解可以表示为$x=U\backslash (L\backslash Pb)$

• QR分解：矩阵可以分解为一个正交矩阵Q和一个上三角矩阵R的乘机形式。类似于LU，通常有一个正交矩阵Q，一个上三角矩阵R及一个 置换矩阵E，满足：XE=QR，方程的解为：x=E(R$\backslash$(Q$\backslash$b))

• Cholesky分解：如果矩阵X是对称正定的，X可以分解为一个下三角矩阵和上三角矩阵的乘机，且下三角和上三角互为转置。X=R^{T}R
  如果任何非零向量z,都有$z^{T}Xz>0$,则X为正定矩阵。虫咬条件是X的特征值全为正。

• 特征值分解EVD：任意n阶方阵X可以分解为$XV=VD$，其中D为特征值对角阵，V是特征向量矩阵。

• 奇异值分解SVD：任意一个mn维的矩阵X可以分解为$X=US{V}^T$,其中$UV$为酉矩阵，S是mn维的对角矩阵，其对角线元素为X的从大到小排序的非负奇异值。SVD分解十分强大且适用，因为任意一个矩阵都可以实现SVD分解，相比与SVD分解，特征值分解只能应用于方阵。

LU 分解

矩阵 $A$ 的因式分解是把 $A$ 表示为两个或更多个矩阵的乘积。矩阵乘法是数据的综合 (把两个或更多个线性变换的作用结合成一个矩阵) 矩阵因式分解是数据分解。在计算机科学中，将 $A$ 表示为矩阵的乘积对应于对 $A$ 中数据的预处理过程, 把这些数据分成两个或更多个部 分, 这种结构可能更有用, 或者更便于计算。
现实中，有可能会求解一系列系数矩阵 $A$ 相同, 但 $b$ 不相同的线性方程:
$$A\mathbf{x}={\mathbf{b}}_1,A\mathbf{x}={\mathbf{b}}_2,\dots ,A\mathbf{x}={\mathbf{b}}_p$$
如果能将 $A$ 预处理为另一种形式, 使得每次求解上述任意方程时的计算量减少，那么即使预处理会耗费一些精力, 那也是值得的。LU分 解就是这样一个预处理过程, 通过LU分解, 可以使得每一个形如 $Ax=b$ 的方程求解过程变得更为简单。
首先, 设 $A$ 是 $m\times n$ 矩阵, 它可以行化简为阶梯形而不必进行行对换 (后面再考虑一般情形)，则 $A$ 可写成形式 $A=LU,L$ 是 $m\times m$ 下三角矩阵, 主对角线元素全是 $1,U$ 是 $A$ 的一个 $m\times n$ 阶梯形矩阵。这样一个分解称为LU分解, 矩阵 $L$ 是可逆的, 称为单位下三角矩 阵。

一旦矩阵 $A$ 可以写成 $A=LU$ 的形式, 方程 $A\mathbf{x}=\mathbf{b}$ 可写成 $L(U\mathbf{x})=\mathbf{b}$, 把 $U\mathbf{x}$ 写成 $\mathbf{y}$, 可以解下面一堆方程来求解 $\mathbf{x}:$
$$\begin{array}{rl}L\mathbf{y}& =\mathbf{b}\\ U\mathbf{x}& =\mathbf{y}\end{array}$$
首先解 $L\mathbf{y}=\mathbf{b}$ 求得 $\mathbf{y}$, 然后解 $U\mathbf{x}=\mathbf{y}$ 求得 $\mathbf{x}$, 由于 $L$ 和 $U$ 都是三角矩阵, 因此每个方程都比较容易解。

QR分解

QR分解定义

一个矩阵 $A\in {\mathbb{R}}^{m\times n},m\ge n$ 可以被分解成 $A=QR$, 其中:

• $Q\in {\mathbb{R}}^{m\times m}$ 是正交矩阵

• $R\equiv \left[\begin{array}{c}\hat{R}\\ 0\end{array}\right]\in {\mathbb{R}}^{m\times n}$

• $\hat{R}\in {\mathbb{R}}^{n\times n}$ 是上三角矩阵

正交矩阵的性质

$Q^{T}Q=Q{Q}^T=I$

左乘一个正交矩阵对欧式范数的结果不影响 (在下面证明eq.2的时候会用到 $)$
$$\Vert Qv{\Vert }_2^2=v^T{Q}^{T}Qv=v^{T}v=\Vert v{\Vert }_2^2$$

从QR分解角度看线性最小二乘

对于一个over-determined线性最小二乘问题 $Ax?b，$ 其目标函数是
$$\begin{array}{rl}?(x)=\Vert r(x){\Vert }_2^2& =\Vert b?Ax{\Vert }_2^2={\Vert b?Q\left[\begin{array}{c}\hat{R}\\ 0\end{array}\right]x\Vert }_2^2\\ & ={\Vert Q^T\left(b?Q\left[\begin{array}{c}\hat{R}\\ 0\end{array}\right]x\right)\Vert }_2^2\\ & ={\Vert Q^{T}b?\left[\begin{array}{c}\hat{R}\\ 0\end{array}\right]x\Vert }_2^2\end{array}$$
这里 $Q\in {\mathbb{R}}^{m\times m},Qb\in {\mathbb{R}}^{m\times 1},\left[\begin{array}{c}\hat{R}\\ 0\end{array}\right]\in {\mathbb{R}}^{m\times n},\left[\begin{array}{c}\hat{R}\\ 0\end{array}\right]x\in {\mathbb{R}}^{m\times 1}$.
如果把 $Q^{T}b$ 拆分成上下两部分, 形式 $\left[\begin{array}{c}\hat{R}\\ 0\end{array}\right]$ 类似, $Q^{T}b=\left[\begin{array}{l}{c}_1\\ c_2\end{array}\right]$, where $c_1\in {\mathbb{R}}^n,c_2\in {\mathbb{R}}^{m?n}°$ 那么目标函数可以写成下面的形式:
$$\Vert r(x){\Vert }_2^2={\Vert c_1?\hat{R}x\Vert }_2^2+{\Vert c_2\Vert }_2^2$$
可以看到, 我们只能最小化前一部分 ${\Vert c_1?\hat{R}x\Vert }_2^2$ 到0, 即 $\hat{R}x=c_1,\Vert r(x){\Vert }_2^2$ 的最小值 为 ${\Vert c_2\Vert }_2^2$ 。这样处理之后就避免了求正规方程组中的 ${\left(A^{T}A\right)}^{?1}$, 避免了条件数变成 $\mathrm{cond}\left(A^{T}A\right)=\mathrm{cond}(A{)}^2$, 所以QR分解法更加数值稳定。

SVD的定义

奇异值分解(Singular Value Decomposition，以下简称SVD)是在机器学习领域广泛应用的算法，它不光可以用于降维算法中的特征分解，还可以用于推荐系统，以及自然语言处理等领域。是很多机器学习算法的基石。本文就对SVD的原理做一个总结，并讨论在在PCA降维算法中是如何运用运用SVD的。

1. 回顾特征值和特征向量

首先回顾下特征值和特征向量的定义如下：
$$Ax=\lambda x$$
其中 $A$ 是一个 $n\times n$ 矩阵, $x$ 是一个 $n$ 维向量, 则 $\lambda$ 是矩阵 $A$ 的一个特征值, 而 $x$ 是 矩阵 $A$ 的特征值 $\lambda$ 所对应的特征向量。
求出特征值和特征向量有什么好处呢? 就是我们可以将矩阵A特征分解。如果我们求出了矩阵A的 n个特征值 ${\lambda }_1\le {\lambda }_2\le \dots \le {\lambda }_n$, 以及这 $n$ 个特征值所对应的特征向量 $w_1,w_2,\dots ,w_n$
那么矩阵A就可以用下式的特征分解表示：
$$A=W\Sigma W^{?1}$$
其中$W$是这n个特征向量所组成的的$n\times n$维矩阵, 而$\sum$为这n个特征值为主对角线的$n\times n$维矩阵。
一般我们会把W的这n个特征向量标准化, 即满足 ${\Vert w_i\Vert }_2=1$, 或者 $w_i^T{w}_i=1$, 此时W的
n个特征向量为标准正交基, 满足 $W^{T}W=I$, 即 $W^T=W^{?1}$, 也就是说W为酉矩阵。
这样我们的特征分解表达式可以写成
$$A=W\Sigma W^T$$
注意到要进行特征分解，矩阵A必须为方阵。
那么如果A不是方阵, 即行和列不相同时，我们还可以对矩阵进行分解吗? 答案是可以，此时我们 的SVD登场了。

2. SVD的定义

SVD也是对矩阵进行分解，但是和特征分解不同, SVD并不要求要分解的矩阵为方阵。假设我们的 矩阵A是一个 $\mathrm{m}\times \mathrm{n}$ 的矩阵, 那么我们定义矩阵A的SVD为:
$$A=U\Sigma V^T$$
其中 $U$ 是一个 $m\times m$ 的矩阵, $\Sigma$ 是一个 $m\times n$ 的矩阵, 除了主对角线上的元素以外全 为0, 主对角线上的每个元素都称为奇异值, $V$ 是一个 $n\times n$ 的矩阵。 $U$ 和 $V$ 都是西矩 阵, 即满足
$U^{T}U=I,V^{T}V=I$ 。下图可以很形象的看出上面SVD的定义:

那么我们如何求出SVD分解后的U, $\Sigma$,V 这三个矩阵呢?
如果我们将A的转置和A做矩阵乘法, 那么会得到 $n\times n$ 的一个方阵 $A^{T}A$ 。既然 $A^{T}A$ 是方阵, 那么我们就可以进行特征分解, 得到的特征值和特征向量满足下式:
$$\left(A^{T}A\right)v_i={\lambda }_i{v}_i$$
这样我们就可以得到矩阵 $A^{T}A$ 的n个特征值和对应的n个特征向量V了。将 $A^{T}A$ 的所有特征 向量张成一个 $n\times n$ 的矩阵V，就是我们SVD公式里面的V矩阵了。一般我们将V中的每个特征向量叫做A的右奇异向量。
如果我们将A和A的转置做矩阵乘法，那么会得到 $\mathrm{m}\times \mathrm{m}$ 的一个方阵 $A{A}^T$ 。既然 $A{A}^T$ 是方
阵，那么我们就可以进行特征分解，得到的特征值和特征向量满足下式：
$$\left(A{A}^T\right)u_i={\lambda }_i{u}_i$$
这样我们就可以得到矩阵 $A{A}^T$ 的m个特征值和对应的m个特征向量u了。将 $A{A}^T$ 的所有特征 向量张成一个 $\mathrm{m}\times \mathrm{m}$ 的矩阵U，就是我们SVD公式里面的U矩阵了。一般我们将U中的每个特征向量 叫做A的左奇异向量。
U和V我们都求出来了，现在就剩下奇异值矩阵\Sigma没有求出了.
由于 $\Sigma$ 除了对角线上是奇异值其他位置都是0，那我们只需要求出每个奇异值\sigma就可以了。
我们注意到:
$$A=U\Sigma V^T?AV=U\Sigma V^{T}V?AV=U\Sigma ?A{v}_i={\sigma }_i{u}_i?{\sigma }_i=A{v}_i/u_i$$
这样我们可以求出我们的每个奇异值, 进而求出奇异值矩阵$\Sigma$。
上面还有一个问题没有讲, 就是我们说 $A^{T}A$ 的特征向量組成的就是我们SVD中的V矩阵, 而
$A{A}^T$ 的特征向量组成的就是我们SVD中的矩阵, 这有什么根据吗? 这个其实很容易证明, 我 们以V矩阵的证明为例。
$$A=U\Sigma V^T?A^T=V\Sigma U^T?A^{T}A=V\Sigma U^{T}U\Sigma V^T=V{\Sigma }^2{V}^T$$
上式证明使用了 $U^U=I,{\Sigma }^T=\Sigma$ 。可以看出 $A^{T}A$ 的特征向量组成的的确就是我们SVD中 的V矩阵。类似的方法可以得到 $A{A}^T$ 的特征向量組成的就是我们SVD中的U矩阵。

进一步我们还可以看出我们的特征值矩阵等于奇异值矩阵的平方，也就是说特征值和奇异值满足如下关系：
$${\sigma }_i=\sqrt{{\lambda }_i}$$
这样也就是说, 我们可以不用 ${\sigma }_i=\frac{A{v}_i}{u_i}$ 来计算奇异值, 也可以通过求出 $A^{T}A$ 的特征值取平方根来求奇异值。

3. SVD计算举例

这里我们用一个简单的例子来说明矩阵是如何进行奇异值分解的。我们的矩阵A定义为:
$$\mathbf{A}=?\begin{array}{ll}0& 1\\ 1& 1\\ 1& 0\end{array}?$$
首先求出 $A^T{A}^{\text{和?}}A{A}^T$
$$\begin{array}{rl}& {\mathbf{A}}^{\mathrm{T}}\mathbf{A}=\left(\begin{array}{lll}0& 1& 1\\ 1& 1& 0\end{array}\right)?\begin{array}{ll}0& 1\\ 1& 1\\ 1& 0\end{array}?=\left(\begin{array}{ll}2& 1\\ 1& 2\end{array}\right)\\ & {\mathrm{A}\mathrm{A}}^{\mathrm{T}}=?\begin{array}{ll}0& 1\\ 1& 1\\ 1& 0\end{array}?\left(\begin{array}{lll}0& 1& 1\\ 1& 1& 0\end{array}\right)=?\begin{array}{lll}1& 1& 0\\ 1& 2& 1\\ 0& 1& 1\end{array}?\end{array}$$
进而求出 $A^{T}A$ 的特征值和特征向量:
$${\lambda }_1=3;v_1=\left(\begin{array}{c}1/\sqrt{2}\\ 1/\sqrt{2}\end{array}\right);{\lambda }_2=1;v_2=\left(\begin{array}{c}?1/\sqrt{2}\\ 1/\sqrt{2}\end{array}\right)$$
接着求出 $A{A}^T$ 的特征值和特征向量:
$${\lambda }_1=3;u_1=?\begin{array}{l}1/\sqrt{6}\\ 2/\sqrt{6}\\ 1/\sqrt{6}\end{array}?;{\lambda }_2=1;u_2=?\begin{array}{c}1/\sqrt{2}\\ 0\\ ?1/\sqrt{2}\end{array}?;{\lambda }_3=0;u_3=?\begin{array}{c}1/\sqrt{3}\\ ?1/\sqrt{3}\\ 1/\sqrt{3}\end{array}?$$
利用 $A{v}_i={\sigma }_i{u}_i,i=1,2$ 求奇异值:
$$\begin{array}{rl}& ?\begin{array}{ll}0& 1\\ 1& 1\\ 1& 0\end{array}?\left(\begin{array}{l}1/\sqrt{2}\\ 1/\sqrt{2}\end{array}\right)={\sigma }_1?\begin{array}{l}1/\sqrt{6}\\ 2/\sqrt{6}\\ 1/\sqrt{6}\end{array}??{\sigma }_1=\sqrt{3}\\ & ?\begin{array}{ll}0& 1\\ 1& 1\\ 1& 0\end{array}?\left(\begin{array}{c}?1/\sqrt{2}\\ 1/\sqrt{2}\end{array}\right)={\sigma }_2?\begin{array}{c}1/\sqrt{2}\\ 0\\ ?1/\sqrt{2}\end{array}??{\sigma }_2=1\end{array}$$
也可以用 ${\sigma }_i=\sqrt{{\lambda }_i}$ 直接求出奇异值为 $\sqrt{3}$ 和1.
最终得到A的奇异值分解为：
$$A=U\Sigma V^T=?\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}??\begin{array}{cc}\sqrt{3}& 0\\ 0& 1\\ 0& 0\end{array}?\left(\begin{array}{cc}1/\sqrt{2}& 1/\sqrt{2}\\ ?1/\sqrt{2}& 1/\sqrt{2}\end{array}\right)$$

4. SVD的一些性质

对于奇异值,它跟我们特征分解中的特征值类似，在奇异值矩阵中也是按照从大到小排列，而且奇 异值的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的 99%以上的比例。
也就是说，我们也可以用最大的k个的奇异值和对应的左右奇异向量来近似描述矩阵。
也就是说：
$$A_{m\times n}=U_{m\times m}{\Sigma }_{m\times n}{V}_{n\times n}^T\approx U_{m\times k}{\Sigma }_{k\times k}{V}_{k\times n}^T$$
其中k要比n小很多，也就是一个大的矩阵A可以用三个小的矩阵 $U_{m\times k},{\sum }_{k\times k},V_{k\times n}^T$ 来表
示。如下图所示，现在我们的矩阵A只需要灰色的部分的三个小矩阵就可以近似描述了。

由于这个重要的性质，SVD可以用于PCA降维，来做数据压缩和去噪。也可以用于推荐算法，将用户和喜好对应的矩阵做特征分解，进而得到隐含的用户需求来做推荐。同时也可以用于NLP中的算法，比如潜在语义索引（LSI）。

SVD 和最小二乘法

设 $A\in R^{m?n}$ 列满秩, $A=U\left[\begin{array}{l}\Sigma \\ 0\end{array}\right]V^T$是A的奇异值分解。

令 $U_n$ 为U的前n列矩阵, 即 $U=\left[U_n,\bar{U}\right]$, 则:

$\Vert Ax?b{\Vert }_2^2=\Vert U\left[\begin{array}{c}\Sigma \\ 0\end{array}\right]V^{T}x?b\Vert =\Vert \left[\begin{array}{c}\Sigma \\ 0\end{array}\right]V^{T}x?{\left[U_n,U\right]}^{T}b\Vert$

$=\Vert \begin{array}{c}\sum V^{T}x?U_n^{T}b\\ ?{\bar{U}}^{T}b\end{array}]\Vert$

$=\Vert \Sigma V^{T}x?U_n^{T}b\Vert +\Vert {\bar{U}}^{T}b\Vert \ge \Vert {\bar{U}}^{T}b\Vert$

等号当且仅当 $\sum V^{T}x?U_n^{T}b=0$ 时成立, 所以:

$x={\left(\Sigma V^T\right)}^{?1}{U}_n^{T}b=V{\Sigma }^{?1}{U}_n^{T}b$

这就是线性最小二乘问题的解。

特殊情况：齐次线性方程 $\mathrm{A}x=0$,其中A的行数大于列数
$$\min \Vert Ax\Vert ，st.\Vert x\Vert =1$$
此时, 最小二乘解为 $A^{T}A$ 最小特征值对应的特征向量。
感性认识: 如果X是 $A^{T}A$ 的特征向量, 则目标函数：
$$||Ax||=x^T\left(A^{T}A\right)x={\lambda }^2\Vert x\Vert$$
求解方案:

1. $\mathrm{eig}\left(A^{T}A\right)=[V,D]$, V为特征向量阵, 找最小特征值对应的V中的特征向量.
2. $\mathrm{svd}(A)=[U,S,V]$, 前面我们知道U是 $A{A}^T$ 的特征值, $\mathrm{V}$ 是 $A^{T}A$ 的特征值,zhaoS中最小奇异值对应的V的右奇异向量即可.

参考：

Cholesky分解
QR分解
矩阵分解
SVD奇异分解
SVD 最小二乘问题
LU分解
SLAM QR SVD