低秩矩阵近似简易调研

SA23916023 叶宏波

在机器学习和深度学习处理输入的过程中，一般来说，输入的数据可以表示成二维矩阵的形式，矩阵的每一列均被称为特征，而矩阵的每一行则是一个采集的数据Xi，例如说在机器学习典型算法xgboost，Decison Tree和Random Forest。例如，可以利用pandas中的DataFrame的.columns 方法查看表头，也就是查看各个特征名即列名；再利用.shape[0] 可以查看样本数即数据行数。在更一般的大数据问题中，数据的数量很大、特征也很多，因此用来表示数据的矩阵极为庞大。如果想按照矩阵的每个元素下标顺序存储，这会增加数据存储的复杂度，也会加大数据处理和运算的难度——在实际情况中大数据通常具有非常多的冗余信息和噪声，将其单纯的表示为一个庞大的矩阵，对于存储和计算都是过度的消耗。

低秩矩阵近似的提出目的就是去除数据中庞杂的冗余信息，同时降低噪声对于信息的影响，提炼出数据中真正有用的信息。

低秩矩阵近似的本质是利用高维空间中的立维结构来近似原来的高秩矩阵，使得低秩矩阵既能够保持原来矩阵的一些性质，就能够减少冗余信息和噪声降低存储空间在处理低秩矩阵，又能有效的减少计算量。 鉴于低秩矩阵近似，在大数据处理上有如此多的优势其在数据挖掘，计算机视觉，影像处理，数值线性代数等诸多领域都有着广泛的理论研究与实际应用。

我们知道大数据有五v特征，即数量多，高速，真实，多样，价值密度低。随着大数据的普及，低秩矩阵近似，在理论研究中取得了巨大进展，在实际中也有着广泛的应用。由于笔者数学底子薄弱，前期搜集和查阅了一些算法，然而在面向屏幕的时候却只能记得算法的名称了，为避免班门弄斧，笔者不在此做相关分享。下文主要从应用角度，和读者分享一下自己的一些看法和收集到的观点，论述的过程中会穿插着一些理论或公式。

低秩矩阵填充

下面简单介绍一下，低秩矩阵填充应用在实际问题中的情况。

我们知道，推荐系统中有时候评论打分系统， 针对各个产品的评分很不完善，在有限的打分中如何为更多的用户推荐影片是急需解决的，这个问题我们按照以下思路，用矩阵填充来进行建模假设矩阵的每一行代表同一用户对不同的电影打分，每一列代表不同的用户对同类电影的打分。这是行的维数就是用户数量，列的维数就是电影数量，因此矩阵维度十分庞大。由于用户对自己接触过的极为有限的电影打分，每部电影的受众又常常有限，因此只有很小一部分元素是已知的——这个矩阵是稀疏矩阵。所有用户对不同电影喜好的因素数量比较有限*。更具体的，从矩阵的行来看，不同的电影其实可能具有相似的性质。例如，两部电影质量都比较高，那么用户对这两部电影的打分应该类似。相反，两部电影质量很低，那么用户的打分普遍应该都比较低。打分矩阵包含着诸多的冗余信息，特征方向有限，所以这个矩阵也是低秩矩阵。 打分推荐问题（matrix completion），就是如何从这个不完整的矩阵中推测其中未知元素的值——那些用户没有打分的缺失值，从而把那些预测值分数较高的电影推荐给用户；矩阵填充的越准确，为用户推荐的电影也就越符合用户的喜好。

有时在不同的场合, 低秩矩阵恢复也被称为矩阵低秩稀疏分解(即将一个矩阵分解为一个低秩矩阵和一个稀疏矩阵之和)、鲁棒主成分分析 (Robust PCA, RPCA)、低秩稀疏非相干分解等. 这个问题在不同的应用领域可能会有不同的理解.

可以考虑用矩阵分解方法来进行低秩矩阵补全。 打分矩阵S 可以分解为两个低秩矩阵的乘法， $S = U^T M$ 如下图所示。 第一个矩阵U的列代表用户，行代表某个隐藏的因素；U的元素$u_{ij}$ 代表用户对该隐藏因素的评分。第二个矩阵M的列代表电影，行代表和U相同的隐藏的因素；M的元素$m_{ij}$ 代表该隐藏的因素下，对电影的评分。因此，基于低秩矩阵分解的方法来进行推荐预测，可以看做是在学习影响用户对电影打分的隐藏因子——也即用户对不同电影喜好的因素或者说打分的因素的数量比较有限。

核范数和鲁棒主成分分析

从实验数据中发现表面现象中蕴含的客观规律也即发现多参数中的较为关键的参量是科学研究的核心任务。有时候我们很难判断哪些变量更加关键，哪些变量可能对待研究的对象是不（太）相关甚至基本等同于噪声干扰，是否需要测试更多维度的信息等。此时一种常用的思路是主成分分析（PCA）。

假设我们有 $p$ 个 (随机) 变量，记为 $x := (x_1, x_2, , x_p)$ ，并每个变量实施了 $n$ 次观测，这时候可以将观测数据整合为一个 $n p$ 维的矩阵 $X$ ，即 $X$ 的每一列对应一个变量（一个特征），每行则对应一次观测 (一个样本)。

我们希望寻找这 $p$ 个 (随机) 变量的一个线性组合，记为 $z_1 := a_1^T x=${j=1}^p a{1 j} x_j ，并希望最大化这个新变量的方差，即 $_{a_1^T a_1=1} (z_1)$ ； 因为方差本身正比于 $|a_1|$ ，我们在这里限定了 $|a_1|=1$ 。

由方差和协方差运算的线性性，易见

$Var (z_1) =E(z_12)-E2(z_1)\ =${i, j=1}^p a{1 i} a_{1 j} E(x_i x_j)-{i, j=1}^p a{1 i} a_{1 j} E(x_i) E(x_j) \ ={i, j=1}^p a{1 i} a_{1 j} E\ =a^T S a

其中 $S$ 为 $(x_1, x_2, , x_p)$ 的协方差矩阵，即 $S_{i j}=(x_i, x_j)=E$ ，显然 $S_{i j}=S_{j i}$ ，即实对称矩阵$S$，存在 $Q Q^T=I$ ，使得 $S=Q Q^T$ 。利用Rayleigh引理，显然所求的组合系数向量 $a_1$ 为矩阵 $S$ 的对应于最大特征值 $_1$ 的单位特征向量(即上述矩阵 $Q=(q_{i j})$ 的第1列)；而 $z_1 a_1^T x=${j=1}^p q{1 j} x_j ，称为该组数据的第1个主成分，且 $(z_1)=_1$ ，为原数据各变量1维线性组合中方差最大的组合。

进一步，对应次大特征值 $_2$ 的单位特征向量 $a_2$ 定义了第2个主成分， $z_2 a_2^T x=${j=1}^p q{2 j} x_j ，且 $(z_1)=_2$ ，为与 $z_1$ 无关 (因 $(z_1, z_2)=a_1^T S a_2=0$ ) 的主成分中方差最大的选择。依次可以定义第 $3,4, , p$ 个主成分，可以统一记为 $z=Q^T x$ ，则 $(z_i, z_j)=$i {i=j} ，即这些主成分之间是相互无关的，方差递减，可以理解为所含的信息量递减。

然而，传统的主成分分析PCA作为一种无参分析手段，完全依赖数据本身的分布，在数据存在大量噪声时，准确性非常糟糕。

对于给定的矩阵M，传统的主成分分析，可以看做在 F-范数意义下求解 $_{rank(L) k}|M - L|$F = {rank(L) k}|N|_F 前文述及，如果观测数据本身存在很大的偏差或者噪声，则主成分（即低秩部分）的提取容易受到干扰。鲁棒主成分分析(Rbust PCA)正是低秩矩阵近似另一个重要的应用，使用 Robust PCA，就是为了能够对噪声有很好的鲁棒性，其基本思路是希望差异矩阵 $E = M - L$ 尽可能稀疏（即不一定是微扰，但是扰动集中在部分元素上），从而更好的对抗数据测量过程中可能引入的幅度较大的（但希望是局部的）误差。

容许我在介绍robust PCA之前，先简要过一下 Schatten p-范数 和核范数

Schatten p-范数

• 由奇异值分解后

$|A|$F^2={i=1}^r i u_i v_i^T, {j=1}^r j u_j v_j^T={1 i, j r} _i ju_i v_i^T, u_j v_j^T={j=1}^r _j^2

所以矩阵的 $F$-范数可以看做奇异值 “向量” 本身的 $l_2$ 范数。 - 更一般的，我们可以推广定义矩阵的 Schatten $p$-范数，即 $|A|_{S_p} (_j _j(A)p){1 / p}, p$

其中 ${\sigma }_1(A)\ge {\sigma }_2(A)\ge \cdots {\sigma }_r(A)>0$1(A) 2(A) r(A)>0σ1​(A)≥σ2​(A)≥⋯σr​(A)>0 为 $A$ 的奇异值。上述 $s_p$ 范数满足三角不等式： $|A+B|${S_p} |A|{S_p}+|B|{S_p} .

核范数

• Schatten p-范数中一个常用的特例是 p = 1 的情形，称为矩阵的核范数（nuclear form），定义为 $|A|_{*} = _{j = 0}^r _j(A)$

• 向量的 $l_1$-范数可以作为其“ $l_0$-范数”（即非零元的个数）的最佳凸近似，可以用于求解满足一定约束条件的最优稀疏解。 • 同样的，矩阵的核范数（即 $s_1$-范数）也是其“Schatten 0-范数”（即矩阵的秩）的最优凸近似，可以用于求解满足一定约束条件的最优低秩解。

Robust PCA 的主要思想就是将数据矩阵M分解为低秩矩阵L加上稀疏矩阵S的形式： $M=L+S$ 其中，M为数据矩阵，每一列代表一个数据。 在Robust PCA中，主要求解如下的凸优化问题: {M=L+S}|L|*+|S|_1 式中，$\lambda$是正则化参数。 使用核范数作为低秩惩罚项，使用L1范数作为稀疏惩罚项，上述凸优化问题能够求得全局最优解。

Robust PCA 在实际中有着非常广泛的应用。

典型的如下图所示，人脸作为背景，墨镜作为前景；格子般的大楼与其前面的孤零零的树；同一个人在光照和position不同的情况下的图像数据集

下面举两个常见而且典型的例子来做说明： 在视频监控中，可以把每一顿图片转化为向量，则整个视频所有帧的向量组成一个矩阵 M。可以把矩阵 M分解成背景矩阵与前景矩阵的和。由于视频的连续性，视频中每一帧的背景是极其相似的，因此背景矩阵是低秩的。在视频监控中，一旦出现了人，则作为前景，由于长时间的视频中，人出现在每一顿图片上的位置或频次是有限的因此前景可以看成稀疏矩阵。使用 Robust PCA，就可以将视频中的背景与前景分开，从而达到监控的目的。

在人脸识别应用中，同一幅人脸在不同的光照下，呈现不同的状态，这加大了人脸识别的难度。可以将人脸矩阵转化为向量，在不同光照下的所有人脸就构成一个矩阵 M。同样的，把矩阵分解为背景矩阵与前景矩阵的和。去掉不同光照下的人脸，本质上是极其相似的，因此构成背景矩阵，是低秩的。而不同的光照就构成了前景矩阵，是稀疏的。使用Robust PCA能够有效地解决人脸识别中的对齐问题。

上述例子一般原理不再赘述，下图提供了更直观的对原理的理解方式：

重新审视矩阵的秩

从线性方程组出发，解一个n个未知数的 m个方程组成的方程组。 以下面为例，

$x_1-x_2 + x_3 = 5 \ x_1 + x_2 + x_3 = 7\ 2x_1 - 2x_2 + 2x_3 = 7$

第1个方程和第2个方程有不同的解，而第2个方程和第3个方程的解完全相同。从这个意义上说，第3个方程是“多余”的，因为它没有带来任何的信息量，把它去掉，所得的方程组与原来的方程组同解。为了从方程组中去掉多余的方程，自然就导出了“矩阵的秩”这一概念。

一般的线性代数或矩阵论教材中讲解过扩展矩阵$(A | b)$

如果 rank(A | b) = rank(A ) = rank(A)_row 则方程解唯一；

如果 rank(A | b) = rank(A ) < rank(A)_row 则方程解唯一；

如果 rank(A | b) > rank(A ) 则方程解 无解；

为了求矩阵A的秩，我们是通过矩阵初等变换把A化为阶梯型矩阵，若该阶梯型矩阵有r个非零行，那A的秩rank(A)就等于r。 其中，非零这个关键字我们当时没有做过多探讨。联系到向量线性相关的证明，向量做系数非零的线性组合，可以构造多个线性相关的向量，那么可以简单理解为，矩阵的秩度量的就是矩阵的行列之间的相关性，越低秩，行或者列的相关性就越大。秩就表示了有多少个有用的方程了。 那么反过来可以说的通吗？ 方阵可逆，各行之间或各列之间线性无关。意味着提供了 0 个无效方程， 也意味着提供了 r = n 个有用方程。这n个方程在求解意义上是无关的， 于是可以知晓矩阵的相关性实际上有带有了矩阵的结构信息。如果矩阵之间各行的相关性很强，那么就表示这个矩阵实际可以投影到更低维的线性子空间，也就是用几个向量就可以完全表达了，它就是低秩的。

如果X是一个m行n列的数值矩阵，rank(X)是X的秩，假如rank (X)远小于m和n，则我们称X是低秩矩阵。低秩矩阵每行或每列都可以用其他的行或列线性表出，可见它包含大量的冗余信息。利用这种冗余信息，可以对缺失数据进行恢复，也可以对数据进行特征提取。

因为rank()是非凸的，在优化问题里面很难求解，那么就需要寻找它的凸近似来近似它了。对，你没猜错，rank(w)的凸近似就是核范数||W||*。 我们认为图像有一些公共的模式，所有图像都由这些基本的模式组成。 图像修复、协同过滤正是基于图像中冗余的信息、低秩矩阵中冗余的信息加多，利用已有的像素或者矩阵元素，可以恢复出图像或者矩阵中的缺少元素。

其它应用

低秩矩阵近似方法还有许多其他的应用。在多任务学习中，不同的任务与任务之间有着某些相似性，不同的特征与特征之间也有着关联，因此多任务学习中的任务、特征矩阵的行和列会有“合作”的特性，可以认为是低秩的，能够使用低秩矩阵近似的方法求解。在多标签学习任务中，相似的样本可以认为具有相似的标签，因此可以认为样本的多标签矩阵是低秩的，或者认为存在一个隐变量矩阵关联样本和标签，这个隐变量矩阵是低秩的。在子空间分割问题中，直接对样本进行聚类通常效果不好。借鉴低秩近似的思想，可以对原数据学习出一个低秩表示，即用一个低秩矩阵去近似原来的数据矩阵，这样不仅能够刻画原数据矩阵的主要性质，又能够去除原数据矩阵的冗余信息达到降维的目的，还能降低原数据矩阵中噪声的影响。

总结

在本文中，我们直接开门见山地介绍了机器学习和大数据领域，数据的矩阵表示的必要性和通用性。在此基础上，尤其是将图像数据和样本-特征型数据，表示成为矩阵，很多信息存在冗余，十分有必要去除数据中庞杂的冗余信息，同时降低噪声对于信息的影响，于是低秩矩阵近似应运而生。 本文进一步介绍和解释了低秩矩阵在打分-推荐系统中的应用和原理，明晰了在矩阵补全中，通过诸如分解的方法，可以认识到矩阵内含的隐藏特征——方向有限，这为我们采用低秩的方法去除冗余提供了依据 为更好地去除冗余并且刻画数据矩阵的主要性质，增强分析后矩阵对数据信息的表现力，我们介绍了主成分分析和鲁棒主成分分析，补充了诸如核范数的概念的同时，审视了矩阵的秩的深刻内涵。 本文最后提及了低秩近似的更多的应用。

可能存在的不足，我谨列举部分

没有系统使用严苛的数学证明； 文中只提到了典型的思路，却没能涉及一些算法的介绍； 就文中提到的隐变量矩阵只是在认知层面做了介绍，没有深入研究甚至没有更多调研...

http://xwxt.sict.ac.cn/CN/Y2019/V40/I3/641

低秩与稀疏联系和区别是什么？ - Frank的回答 - 知乎 https://www.zhihu.com/question/40981767/answer/1958140423

赏

谢谢温柔的你请我喝咖啡

支付宝

微信