Tensor CP 分解视角下的矩阵乘法

对于两个 规模的矩阵乘法，标准算法的计算量为 量级，回归到 矩阵的乘法，则是 8 次乘法。 具体来说，对于

标准矩阵乘法的计算流程为：计算 8 个中间量

然后组合得到结果

Strassen 算法（1967年）利用巧妙的构造可以把运算减少为 7 次乘法（和几次额外的加减法），具体计算过程如下：首先计算 7 个中间量

然后组合得到结果

对大规模矩阵来说，可以通过对矩阵乘法不断分解为 的子矩阵乘法，分层应用 Strassen 算法，最终把计算复杂度降低到 量级。

理论上可以证明这里的七次乘法是最少的，不存在只需要六次乘法的同类型算法，因此在这个意义下 Strassen 算法已经达到最优。 但是，最新的研究已经可以把复杂度从 降低到 左右。

这里讨论的都是计算复杂度，对于小规模的矩阵，这种算法的优势可能并不明显。

可以从张量的视角来解释这里的矩阵乘法。 首先，把矩阵乘法写成如下形式

因此，可以将 矩阵乘法写成一个三阶张量的形式

其中 为一个 张量，其中元素为

假设张量 存在如下 CP 分解

那么

我们要求 的元素只含有 或 ，这样就不会存在系数所带来的额外乘法，此时计算所有的 所需的乘法运算次数为 。

例如标准矩阵乘法实际对应 8 个秩一张量所组成的 CP 分解（每一项分别对应前面的 8 个中间量）

Strassen 算法则对应 7 个秩一张量所组成的 CP 分解（每一项分别对应前面的 7 个中间量）

对于三阶张量的秩的计算都非常复杂，更不要说这种在特定格式下的 CP 分解的最优秩，不过通过前面的实践可以看出，对于这个特殊的三阶张量 ，最优秩应该为 。