Hadamard矩阵笔记

Hadamard 矩阵与量化旋转笔记

旋转量化里的核心工具。理解它就理解了 QuaRot / SpinQuant / ConvRot 一大半。

1. 定义与基本性质

Hadamard 矩阵 $H_n$ 是一个 $n \times n$ 的方阵，满足：

• 元素只取 $+1$ 或 $-1$
• $H_n \cdot H_n^T = n \cdot I_n$（自身转置 $\times$ 自身 = $n$ 倍单位阵）
• 归一化后 $U = \frac{1}{\sqrt{n}} H_n$ 是一个正交矩阵（满足 $U U^T = I$）

对称性：常见的 Hadamard 矩阵（如通过 Sylvester 递归构造的）通常是对称矩阵，即 $H_n = H_n^T$。此时满足 $H_n^2 = n I_n$。

存在的必要条件：阶数 $n = 1, 2$，或 $4k$（$k$ 为正整数）。其他阶数（如 $n=3, 5, 6$）不存在 Hadamard 矩阵。

2. Sylvester 递归构造（最常用的构造方式）

Sylvester 构造法适用于 $n = 2^k$（$k \ge 0$）的情形：

物理直觉：每升一阶，就是把上一阶“复制 4 份”放在四个角，右下角的符号取反（按 $\begin{bmatrix} + & + \\ + & - \end{bmatrix}$ 模式排列）。

3. 为什么正交？

两行（或两列）做内积：

• 由于 $H$ 中每一行（除了第一行外）都恰好包含 $\frac{n}{2}$ 个 $+1$ 和 $\frac{n}{2}$ 个 $-1$。
• 任意两个不同的行向量之间，同号位置与异号位置各占一半，因此内积总和为 $0$。

自己跟自己内积：

• 每个元素平方后都为 $1$（即 $(\pm 1)^2 = 1$），$n$ 个元素相加等于 $n$。

因此 $H \cdot H^T = n \cdot I$，归一化矩阵 $U = \frac{1}{\sqrt{n}} H$ 是标准的正交变换矩阵。

4. 几何与物理直觉

4.1 它在做什么

假设激活向量 $v = [a, b, c, d]$，通过归一化的 $H_4$ 旋转：

本质上，Hadamard 旋转是 $n$ 维空间里的一组两两正交的 $\pm 1$ 基底。它将向量投影到这些基底上，每个旋转后的输出通道都是原始所有输入通道的某种 $\pm$ 组合。

4.2 离群点（Outliers）平滑场景

量化的最大敌人是通道间极度不均匀。假设激活向量在通道维度存在一个极大的通道离群点：$v = [0.1, 0.1, \dots, 0.1, 10.0]$（维度为 $K$）。

• 不旋转：max = 10.0，其他值 ≈ 0.1。由于量化时采用最大值作为缩放因子（Scale Factor），小数值的量化精度会被严重压缩（即被“淹没”在噪声中）。
• 旋转后（乘以 $\frac{1}{\sqrt{K}} H_K$）：
  • 第一行：全加组合 $\rightarrow \frac{0.1 \times (K-1) + 10}{\sqrt{K}}$。
  • 其他行：正负交替组合 $\rightarrow$ 大值 $10$ 被正负号均匀分摊，各个维度的值都会收敛在 $\approx \frac{10}{\sqrt{K}}$。

能量被均匀分散，原先的单一离群通道被“摊薄”到了所有通道上，极大地降低了量化困难。

4.3 记忆口诀

Hadamard 旋转 = 用等幅的正负交替投影，把“一个通道的大值”摊薄成“所有通道差不多大的值”。

5. 为什么选 Hadamard 而不是随机正交矩阵？

6. FWHT（快速沃尔什-哈达玛变换）

6.1 蝴蝶操作实现

利用 Sylvester 递归结构，可以使用类似 FFT 的蝴蝶网络进行高效计算：

import numpy as np

def fwht(x):
    """输入 x 的长度必须是 2 的幂"""
    n = len(x)
    if n == 1:
        return x
    # 递归划分为奇偶部分（或前后两半，取决于Walsh/Hadamard序）
    y_even = fwht(x[0::2])
    y_odd  = fwht(x[1::2])
    # 蝴蝶合并
    return np.concatenate([y_even + y_odd, y_even - y_odd])

6.2 复杂度

• 朴素矩阵乘法：$O(n^2)$ 次浮点乘加
• FWHT 算法：$O(n \log n)$ 次纯加减法

6.3 硬件落地局限性（ConvRot 改用普通 MatMul 的原因）

在大模型/DiT 推理中，FWHT 虽然理论复杂度低，但其蝴蝶网络的内存访问不规则。现代 GPU 的 Tensor Core 主要是为规则矩阵乘法（GEMM）设计的。 直接跑 FWHT 无法利用 Tensor Core，只能在 CUDA Core 上跑，导致实际运行速度甚至慢于用 Tensor Core 硬跑一个 $O(n^2)$ 的普通矩阵乘。 因此，ConvRot 放弃了 FWHT，直接将 Regular Hadamard 矩阵存为权重，用高效的 Tensor Core 矩阵乘法（GEMM）执行旋转。

7. Regular Hadamard 矩阵（ConvRot 的核心理论）

7.1 列偏差（Column Discrepancy）与定义

对于任意 $n \times n$ 的 Hadamard 矩阵 $H_n$，其**列偏差（Column Discrepancy）**定义为每列元素之和的绝对值的最大值：

• Sylvester 型 Hadamard 矩阵：其第一列全部为 $+1$，因此其列偏差达到最大值：$D(H_n) = n$。
• Regular Hadamard 矩阵：其每一行和每一列的元素之和都是一个常数 $s$。
  • 定理证明：若 $H \mathbf{1} = s \mathbf{1}$，则 $H H^T \mathbf{1} = H (s \mathbf{1}) = s^2 \mathbf{1}$。
  • 又因为 $H H^T = n I$，所以 $H H^T \mathbf{1} = n \mathbf{1}$。
  • 两式结合得到 $s^2 = n \implies s = \pm\sqrt{n}$。因此，列偏差达到了理论最小值 $D(H_n) = \sqrt{n}$。

7.2 为什么对“行向离群点”友好？（核心数学解释）

在 Diffusion Transformer (DiT) 等模型中，常出现行向离群点（Row-wise Outliers / Token-wise Outliers）。这意味着某个 Token 的所有通道值都非常大，或者存在一个系统性的偏置。 为简化理解，假设该 Token 的激活向量为系统偏置 $x = [c, c, \dots, c]$。我们用归一化矩阵 $U = \frac{1}{\sqrt{n}} H_n$ 进行旋转，输出为 $y = x U$：

1. 使用 Sylvester Hadamard（列偏差为 $n$）： 由于第一列全是 $+1$，其余列的和为 $0$：

   • $y_1 = \frac{1}{\sqrt{n}} \sum_{i=1}^n c = \sqrt{n} \cdot c$
   • $y_{2 \dots n} = 0$
   • 后果：系统偏置被全部压缩聚集到了第一个通道，导致第一个通道的值被放大了 $\sqrt{n}$ 倍！若 $n=1024$，离群值被放大了 32 倍！这在旋转后制造了更恐怖的通道离群点，彻底破坏量化。

2. 使用 Regular Hadamard（列偏差为 $\sqrt{n}$）： 由于每一列的和都是 $\pm\sqrt{n}$：

   • $y_j = \frac{1}{\sqrt{n}} \sum_{i=1}^n c H_{ij} = \frac{c}{\sqrt{n}} (\pm\sqrt{n}) = \pm c$
   • 后果：旋转后的各个通道绝对值依然是 $c$，没有任何维度被放大！成功抑制了行向离群点的能量聚集。

7.3 Kronecker 积构造法

Regular Hadamard 矩阵仅在阶数 $n$ 是完全平方数（如 $4^k$）时存在。 基于一个基础的 $4$ 阶 Regular Hadamard 矩阵 $H_4^{reg}$：

可以使用 Kronecker 积（张量积）递归构造更高阶（$4^k$ 阶）的 Regular Hadamard 矩阵：

这使得我们能够构造出维度为 $4, 16, 64, 256, 1024, 4096$ 的 Regular Hadamard 矩阵。

7.4 为什么 ConvRot 必须使用“分组旋转（Group-wise）”？

1. 尺寸限制：Regular Hadamard 矩阵的阶数必须是 $4^k$ 阶。然而，实际神经网络的通道数 $K$（如 $3072$ 或 $15360$）往往不是 $4$ 的幂。通过将其划分为固定大小的组（如组大小 $N_0 = 256$ 或 $1024$），可以在组内应用精确的 Regular Hadamard 旋转。
2. 线性复杂度：全局旋转的计算复杂度为 $O(K^2)$。而分组旋转（Group-wise RHT）的复杂度仅为 $O(K \cdot N_0)$，因为 $N_0$ 是一个常数，这成功将计算开销降为了线性复杂度 $O(K)$，从而极大地节省了在线计算耗时。

8. 等价变换恒等式（为什么旋转不改变精度）

在进行线性层 $Y = X \cdot W^T$ 计算时，我们在 $X$ 和 $W$ 之间插入归一化 Regular Hadamard 矩阵 $R = \frac{1}{\sqrt{N_0}} H_{N_0}$：

• 激活值旋转：$\tilde{X} = X \cdot R$（在线计算，抑制激活值中的离群点）。
• 权重旋转：$\tilde{W} = W \cdot R$（离线计算，不占用推理时间）。
• 最终输出 $Y$ 的数学结果完全保持一致，但参与量化和 GEMM 的矩阵变成了分布极其平滑的 $\tilde{X}$ 和 $\tilde{W}$。

9. 速查表