蝶形分解的实部何时保持结构？

蝶形乘积的实部为何此前不清楚

离散余弦变换等快速变换常被写成复值结构化稀疏矩阵乘积的实部，这类矩阵称为 Kronecker 稀疏因子。方阵二进蝶形矩阵和 monarch 矩阵也依赖同类乘积，它们已知能高效表示许多快速变换。此前尚未确定的是：取这类乘积的实部或虚部后，是否仍得到 Kronecker 稀疏因子的乘积，且元素为实值。

实际关键在于数值格式。GPU 上的低精度浮点格式目前不支持复数，因此依赖复值 Kronecker 稀疏因子的变换实现无法使用它们。如果分解的实部本身仍是实值 Kronecker 稀疏的，这些变换就能以低精度实现。论文指出，这一问题此前未在文献中得到处理。

Kronecker 稀疏因子与链式架构

模式为 (a, b, c, d) 的 Kronecker 稀疏因子，是其支撑集包含于 I_a ⊗ 1_{b×c} ⊗ I_d 支撑集的矩阵，其中 1_{b×c} 是全 1 的 b×c 矩阵，I 表示单位矩阵。模式固定非零元可能出现的位置，元素本身不受限制。蝶形分解是乘积 K_1 ··· K_L，其中每个 K_ℓ 按各自模式 Kronecker 稀疏，模式组成的元组称为该分解的架构。

两个族说明其重要性。方阵二进蝶形矩阵是 n = 2^L 的 n×n 矩阵，对应 FFT 和快速 Walsh-Hadamard 变换等，可分解为 K_1 ··· K_L，其中 K_ℓ 的模式为 (2^{ℓ−1}, 2, 2, 2^{L−ℓ})。用于 transformer 权重矩阵的 monarch 分解把 m×n 矩阵表示为两个 Kronecker 稀疏因子的乘积，模式分别为 (1, p, q, m/p) 和 (q, m/p, n/q, 1)，前提是 p 和 q 分别整除 m 和 n。

先取实部会破坏稀疏模式

对单个因子（L = 1），实部和虚部继承相同模式，因为 Kronecker 稀疏性只取决于支撑集。困难从 L ≥ 2 出现。简单线性代数可把 Re(K_1 ··· K_L) 改写为 L 个矩阵的乘积，但这些矩阵由原因子的实部和虚部构成，不再是 Kronecker 稀疏的。论文以模式为 (2, 2, 2, 3) 时最后一个因子的支撑集为例说明这一点。

因此，蝶形乘积的实部总能表示为 L 个矩阵的某种乘积，但并不自动是 Kronecker 稀疏矩阵的乘积。论文填补的正是这一缺口。

置换矩阵恢复 Kronecker 稀疏分解

解决办法是在因子之间插入置换矩阵。对任意置换矩阵 P_2, …, P_L，乘积 K_1 ··· K_L 等于置换后因子的乘积：第一个变为 K_1 P_2ᵀ，中间的变为 P_ℓ K_ℓ P_{ℓ+1}ᵀ，最后一个变为 P_L K_L。问题于是变成：能否选择置换和最大稀疏模式，使每个置换后的因子都是 Kronecker 稀疏的。

论文依据每行每列非零元计数，为置换后的因子指定了特定模式。例如，第一个因子的列数是原来的两倍，而每列的稀疏度不变。目标模式为：第一个因子 (a_1, b_1, 2c_1, d_1)，最后一个因子 (a_L, 2b_L, c_L, d_L)，中间因子 (a_ℓ, 2b_ℓ, 2c_ℓ, d_ℓ)。

链式条件决定结构能否保留

在选定置换矩阵的前提下，论文给出了一个关于因子的既必要又充分的条件，用于判定 Kronecker 稀疏因子乘积的实部或虚部是否仍是 Kronecker 稀疏因子的乘积。当架构满足该链式条件时，实部可按目标模式定义的新架构 (π′_1, …, π′_L) 进行 Kronecker 稀疏分解。

同样的论证覆盖虚部，因为 Im(K_1 ··· K_L) 等于 Re((−j K_1) ··· K_L)，而 j K_1 与 K_1 具有相同模式且 Kronecker 稀疏。更一般地，对任意复数 z，Re(z K_1 ··· K_L) 也成立。论文还指出，链式条件为早先分解算法执行的 Kronecker 稀疏分解带来误差保证，并将其描述为一项重要的实际优势。

DCT、DST 和 DHT 变为全实值分解

具体收益是：当维度为 2 的幂时，DCT、DST 和 DHT 可获得全实值 Kronecker 稀疏实现。FFT 中出现的方阵二进蝶形因子以及 monarch 因子构成链式架构。DCT 和 DST 矩阵可写成 L Re(D F) R，其中 L 和 R 为实值，D 为对角矩阵，F 为 DFT 矩阵。

把 F = B P 代入，其中 B 是具有方阵二进蝶形分解的复矩阵，P 是位反转置换，则 DCT 和 DST 形如 L Re(D B) P R，而 D B 仍具有方阵二进蝶形分解。由于 DHT 是 DCT 与 DST 之和，它同样可写成 L Re((D_C + D_S) B) P R，并出于相同原因可进行 Kronecker 稀疏分解。论文称，这三种变换的实值分解据其所知在文献中是新的。

计时实验说明了什么、没说明什么

论文报告了一项实验，测量使用实值 Kronecker 稀疏分解对向量 x ∈ R^{n×b} 施加 DCT 的推理时间，其中 b 是批大小。批处理设置在实际中更相关：DCT 很少作用于单个向量，而是作用于大批数据，例如 JPEG 等图像压缩标准对图像每个 8×8 块施加 DCT，音频编码器对信号每一帧施加 DCT。报告的图覆盖 n 从 10^2 到 10^4，时间为秒，采用对数刻度。

该实验是在一种实现下对一种变换的计时测量，并非与替代分解的比较，证据包也未报告曲线背后的数值。代码见补充材料，结果已实现在 Python 库 lazylinop 中，用于为这些变换设计高效算法。

保证适用于哪里、止于哪里

该保证是有条件的，并非普遍成立。它要求架构满足链式条件，并且是在特定置换矩阵选择下陈述的；论文称该条件在此设定下既必要又充分。DCT、DST 和 DHT 的实值表示是在维度为 2 的幂时建立的，这正是方阵二进蝶形架构适用的范围。

低精度 GPU 的动机是开端而非已证明的结果：论文把实值分解描述为为使用低精度数值格式的高效 GPU 实现开辟新途径，并另外指出不规则稀疏模式不适合 GPU，使理论加速难以在实践中实现，而近期块结构或专用内核的工作正开始缩小这一差距。计时实验只测量 DCT，因此本身并不能确立低精度加速。

可复用的是条件而非变换本身

这篇论文最具迁移价值的产出是关于架构的链式条件，因为它能事先告诉你取 Kronecker 稀疏乘积的实部或虚部是否会保持结构，而不必逐例检查。DCT、DST 和 DHT 是满足该条件的实例，也是收益具体的实例：在 2 的幂维度上获得实值 Kronecker 稀疏分解，这正是低精度格式问题之所以相关的原因。

因此，对判断该结果是否适用于某个变换的读者来说，关键检验是架构，而不是变换名称。如果分解按所需意义链式成立，实部就保持 Kronecker 稀疏，实值实现随之成立；如果不成立，预分解仍然存在，但稀疏结构丢失，低精度路线也就无法据此实现。

本文引用的文献