[线性代数]介绍几种矩阵分解算法以及应用

线性代数作为很多应用科学的基础，重要性不言而喻，在[线性代数本质]系列中介绍了线性代数理论知识，除此之外，还展示了线性代数在多个领域的应用，例如，深度学习，推荐系统，自然语言处理，计算机图像学等。本篇文章将继续探索线性代数在现实生活中的应用。

线性代数中最重要的是矩阵，我们身边到处都是矩阵，凡是能写进Excel表格中的都可以看成矩阵，语言，文档，图像也是矩阵，矩阵除了可以代表一种实体外，矩阵还是一种线性变换，这个我们在线性代数本质中已经展现的淋漓尽致。

矩阵最重要的是矩阵运算，最重要的两种矩阵运算类型：

• 矩阵积

• 矩阵分解

矩阵积包括：矩阵与向量乘积，矩阵与矩阵乘积，矩阵与高维张量的乘积等。向量可视为特殊的矩阵，所以，向量的点积和叉积也可视为特殊的矩阵乘积。

矩阵与向量乘积：

假设下面的概率转移矩阵代表HIV患者1年内从一种健康状态转移到另一种状态的概率：

对应的状态转移过程如下：

如果某个社区的当前状态为：

• 85% asymptomatic（无症状）

• 10% symptomatic（有症状）

• 5% AIDS

• 0% death

那么，这个社区下一年会是什么状态？

可以将当前状态转换为向量，有了状态转移矩阵，下一年的状态可以转换为矩阵和向量的乘法：

最终结果：

76.5%会继续保持无症状，而1.8%会死亡。

矩阵与矩阵乘积：

一张手写体数字图像可以表示成如下矩阵形式：

卷积是卷积神经网络的核心，相当于在图像上应用一个滤波操作：

从前馈神经网络的角度看卷积：

卷积也可以看成是一种特殊的矩阵乘积操作：

矩阵分解：

矩阵分解被列为20世纪科学与工程领域10大顶尖算法：

其中最重要的矩阵分解算法包括NMF（非负矩阵分解），SVD（奇异值分解），随机SVD，PCA（主成分分析）和健壮PCA。

下面将会通过几个示例来展示矩阵分解的强大作用。

1.通过NMF和SVD构建主题模型

SVD：

假设现在有m个文档，每个文档提取n个单词，并且通过某种方法（词袋或者word2vec）进行向量化，这就构成了一个矩阵：

现在对矩阵A进行奇异值分解：

A_ij对应第i个文本的第j个词的特征值。U_il 对应第i个文本和第l个主题的相关度。V_jm 对应第j个词和第m个词义的相关度。

 _{对应第l个主题和第m个词义的相关度。}

_{一般主题的个数要远小于文档的个数，如果要选择其中的k个主题，则可以将}

中对角元素进行排序，取前k个元素。

最终文档被划分为k个聚类中心，每个类簇代表一个鲜明的主题。当需要对一个新的文档进行分类时，可以依据向量的距离来选择类簇，这种方法不仅简单，更重要的是，它是一种无监督算法。

NMF：

还是前面那个文档矩阵V，NMF与SVD不同，它将矩阵A分解为两个矩阵：

在NMF中求解出来的W和H，分别体现的是文本和主题的概率相关度，以及词和主题的概率相关度。

那如何求解W和H呢？NMF的期望是找到两个W、H矩阵，使得WH的矩阵乘积结果和对应的原矩阵V对应位置的值相比误差尽可能的小。

对于上面的优化问题，可以直接使用梯度下降法或者拟牛顿法来进行求解。

为了防止过拟合，也可以在NMF的目标函数的基础上添加一个正则化项：

但是当加入L1正则项后，由于没法求解出正常的导函数出来（导函数不是连续的），也就没法使用梯度下降法和拟牛顿法求解参数，此时一般采用坐标轴下降法来进行参数的求解。

2.求解线性方程组

对于齐次线性方程组Ax=0，如果数据点的个数（A的行数）远大于变量的个数，则可能找不到精确解，但是可以通过最小化Ax拟合出一条直线。通过奇异值分解就可以拟合出这么一条直线。

如上图所示，有多个数据点对 (xi,yi)。

假设这些点满足线性方程：

最终可以写成矩阵的形式：

Ax=0

对矩阵A进行奇异值分解：

如果要找到Ax=0的非零解，根据线性代数本质系列，矩阵是一种变换，矩阵的行列式代表变换前后面积或者体积的变化，要想求x的非零解，只有A的行列式等于0的情况下，才能将非零向量x压缩到更低维度的空间。

矩阵行列式值等于特征值乘积：

所以，如果Σ中有一个对角元素为0就能对方程组求解，该0元素对应矩阵V的列就是方程组的解，如果没有一个元素为0，虽然不能求方程组精确解，但可以求近似解，数据拟合就是在求近似解，所以，只要找到Σ中的最小元素，该元素对应V的列就是方程组的近似解。

现在让我们看一下主流机器学习库中是如何求解线性方程组的。

sklearn：

sklearn调用的是scipy.linalg.lstqr, lstqr调用LAPACK方法，LAPACK根据输入的参数选择求解方法：

• gelsd: uses SVD and a divide-and-conquer method

• gelsy: uses QR factorization

• gelss: uses SVD

Scipy：

Scipy Sparse采用迭代的方式求近似解

1. Compute a residual vector r0 = b - A*x0.

2. Use LSQR to solve the system A*dx = r0.

3. Add the correction dx to obtain a final solution x = x0 + dx.

其本质上就是求A的近似M，M*x = b，使得M - A具有低秩。

让我们再看看其他方式：

Naive Solution：

我们的目的是要

，使得

最小化。换个角度就是让b接近A所张成的子空间，也就是将b投影到A上，由于b−Ax垂直A所张成的子空间，所以：

所以：

Normal Equations (Cholesky)：

QR分解：

总结：

本节讲解了几种求解线性方程组的方法，有迭代的方法还有矩阵分解的方法。

3.通过压缩感知对CT图像进行重建

前面已经讲了如何通过矩阵分解求解线性方程组，现在看一下通过求解线性方程组来进行CT图像重建，这种方法被称为“压缩感知”。

根据CT的成像原理可知，每一束X线最终得到的是一个方向的投影图像。

所以压缩感知的最终目的：通过多个投影图像来恢复出原始图像。

重建过程本质就是一个线性回归问题：

Ax=b

A是投影矩阵，它是一个4维矩阵（angle, location, x, y），x就是原始图像，b是投影图像。

4.通过PCA去除视频背景

PCA也叫主成分分析，通过对矩阵特征值分解来找到变换的主方向，对于一段视频而言，将所有帧图像组织成一个矩阵，也就是矩阵的每一列都是一帧图像，对这个矩阵施行主成分分析，就能够实现不变的背景和变化的前景分离。

我们要实现的目标：

将这个矩阵显示出来：

条状的代表背景，波浪的代表运动的前景，PCA的目的就是要构造下面的等式：

M代表原始矩阵，L是低阶矩阵，低阶矩阵意味着有很多冗余信息，也就是不变的背景，S是稀疏矩阵，也就是运动的前景。

PCA通过优化下面函数进行求解：

最终效果如下：

除了PCA，还可以通过SVD进行求解。