专栏名称: PaperWeekly

PaperWeekly是一个分享知识和交流学问的学术组织，关注的领域是自然语言处理的各个方向。我们热爱知识，分享知识，希望通过我们大家的努力为自然语言处理的发展做出一点点贡献。我们每周会分享一期特定话题的论文笔记和本周值得读的相关论文。

低秩近似之路（三）：矩阵乘法的CR近似

PaperWeekly · 公众号 · 科研 · 2024-11-07 13:14

正文

©PaperWeekly 原创 · 作者 | 苏剑林

单位 | 科学空间

研究方向 | NLP、神经网络

在《低秩近似之路（二）：SVD》中，我们证明了 SVD 可以给出任意矩阵的最优低秩近似。那里的最优近似是无约束的，也就是说 SVD 给出的结果只管误差上的最小，不在乎矩阵的具体结构，而在很多应用场景中，出于可解释性或者非线性处理等需求，我们往往希望得到具有某些特殊结构的近似分解。

因此，从这篇文章开始，我们将探究一些具有特定结构的低秩近似，而本文将聚焦于其中的 CR 近似（Column-Row Approximation），它提供了加速矩阵乘法运算的一种简单方案。

问题背景

矩阵的最优 r 秩近似的一般提法是

其中。在前两篇文章中，我们已经讨论了两种情况：

1. 如果不再有其他约束，那么的最优解就是，其中是的奇异值分解（SVD）；

2. 如果约定（），且（或）已经给定，那么的最优解是（或），这里的是“伪逆”。

这两个结果都有很广泛的应用，但它们都没有显式地引入与结构上的关联，这就导致了很难直观地看到与的关联，换言之的可解释性不强。

此外，如果目标中包含非线性运算如，通常也不允许我们使用任意实投影矩阵来降维，而是要求使用“选择矩阵（Selective Matrix）”，比如对于任意矩阵不是恒成立的，但对于选择矩阵是恒成立的。

所以，接下来我们关注选择矩阵约束下的低秩近似。具体来说，我们有，然后选定，我们的任务是从中选出列、从中选出相应的行来构建，即

这里的可以理解为 slice，即按照 Python 的切片规则来理解，我们称的“CR 近似”。注意这种切片结果也可以用选择矩阵来等价描述，假设的第列分别为的第列，那么可以定义选择矩阵：

即的第列的第个元素为 1，其余都为 0，这样一来就有以及。

初步近似

如果我们将分别表示成

其中都是列向量，那么可以写成

而找的最优 CR 近似则可以等价地写成

我们知道，矩阵的范数实际上就是将矩阵展平成向量来算模长，所以这个优化问题本质上就相当于给定个向量，求

其中，。记，那么可以进一步简化成

如果笔者没有理解错，这个优化问题的精确求解是 NP-Hard 的，所以一般情况下只能寻求近似算法。一个可精确求解的简单例子是两两垂直，此时

所以它的最小值就是最小的个之和，即让模长最小的个的等于 1，剩下的则等于 0。当两两正交的条件不严格成立时，我们依然可以将选择模长最小的个作为一个近似解。

回到原始的 CR 近似问题上，我们有，所以的最优 CR 近似的一个 baseline，就是保留的列向量与对应的行向量模长乘积最大的个列/行向量。

采样视角

有一些场景允许我们将式（6）放宽为

其中表示时输出 1，否则输出 0。这个宽松版本其实就是将 CR 近似的形式从拓展成，其中是对角阵，即允许我们调整对角阵来达到更高的精度。相应地，式（7）变为

这样放宽之后，我们可以从采样视角来看待这个问题。首先我们引入任意元分布，然后我们就可以写出

也就是说，的数学期望正好是我们要逼近的目标，所以我们可以通过从分布独立重复采样来构建近似：

这意味着当是之一时有，否则。可能有读者疑问为什么要独立重复采样，而不是更符合逼近需求的不放回采样呢？无他，纯粹是因为独立重复采样使得后面的分析更简单。

到目前为止，我们的理论结果跟分布的选择无关，也就是说对于任意都是成立的，这给我们提供了选择最优的可能性。那如何衡量的优劣呢？很显然我们希望每次采样估计的误差越小越好，因此可以用采样估计的误差

来比较不同的之间的优劣。接着利用均值不等式有

等号在时取到，由此可得最优的为

对应的误差为

最优的正好正比于，所以概率最大的个也正是模长最大的个，这就跟上一节的近似联系起来了。

该结果出自 2006 年的论文《Fast Monte Carlo Algorithms for Matrices I: Approximating Matrix Multiplication》[1]，初衷是加速矩阵乘法，它表明只要按照

来采样对应的列/行，并乘以，就可以得到的一个 CR 近似，从而将乘法复杂度从降低到。

延伸讨论

不管是按模长排序还是按随机采样，它们都允许我们在线性复杂度【即】内构建一个 CR 近似，这对于实时计算来说当然是很理想的，但由于排序或采样都只依赖于，所以精度只能说一般。如果我们可以接受更高的复杂度，那么如何提高 CR 近似的精度呢？

我们可以尝试将排序的单位改为 k 元组。简单起见，假设是的一个因数，个向量选个的组合数为，对于每个组合我们都可以算出向量和的模长。有了这些数据，我们就可以贪婪地构建（8）的近似解：

初始化

对于，执行：

返回。

说白了，就是每次都从剩下的向量中挑选和模长最小的个向量，重复挑选次即得到个向量，它是按照单个向量模长来排序的自然推广，其复杂度为，当且比较大时可能难以承受，这也侧面体现了原问题精确求解的复杂性。

另一个值得思考的问题是如果允许 CR 近似放宽为，那么的最优解是什么呢？如果不限定的结构，那么答案可以由伪逆给出

如果必须是对角阵呢？那可以先将问题重述为给定

，求

我们记：

那么优化目标可以写成

这同样可以通过伪逆写出最优解

最后一个等号假设了可逆，这通常能满足，如果不满足的话改就行。

现在的问题是直接套用上式的话对原始问题来说计算量太大，因为，即是维向量，所以大小为、大小为，这在较大时比较难受。利用能帮我们进一步化简上式。不妨设，那么

即

，这里的是 Hadamard 积 [2]，这样恒等变换之后和的计算量就降低了。

文章小结

本文介绍了矩阵乘法的 CR 近似，这是一种具有特定行列结构的低秩近似，相比由 SVD 给出的最优低秩近似，CR 近似具有更直观的物理意义以及更好的可解释性。

参考文献

[1] https://www.stat.berkeley.edu/~mmahoney/pubs/matrix1_SICOMP.pdf

[2] https://en.wikipedia.org/wiki/Hadamard_product_(matrices)

更多阅读

#投稿通道#

让你的文字被更多人看到

如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。

总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。

PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学术热点剖析、科研心得或竞赛经验讲解等。我们的目的只有一个，让知识真正流动起来。

📝 稿件基本要求：

• 文章确系个人原创作品，未曾在公开渠道发表，如为其他平台已发表或待发表的文章，请明确标注

• 稿件建议以 markdown 格式撰写，文中配图以附件形式发送，要求图片清晰，无版权问题

• PaperWeekly 尊重原作者署名权，并将为每篇被采纳的原创首发稿件，提供业内具有竞争力稿酬，具体依据文章阅读量和文章质量阶梯制结算

📬 投稿通道：

• 投稿邮箱：[email protected]

• 来稿请备注即时联系方式（微信），以便我们在稿件选用的第一时间联系作者

• 您也可以直接添加小编微信（pwbot02）快速投稿，备注：姓名-投稿

△长按添加PaperWeekly小编

🔍

现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧