第四章：率失真计算与矢量量化

本章介绍如何数值计算没有闭式解的率失真函数，重点是Blahut-Arimoto算法。我们还将扩展到多维信源，介绍矢量量化的基本原理及其与率失真理论的深刻联系。这些内容将率失真理论从解析结果推广到一般实用场景。

学习目标：

掌握Blahut-Arimoto算法的原理和实现要点
理解矢量量化的优势和设计方法
了解Lloyd-Max算法的率失真解释
建立标量量化与矢量量化的性能对比直觉

4.1 Blahut-Arimoto算法

4.1.1 问题回顾

率失真函数的定义：

$$R(D) = \min_{p(\hat{x}|x): \mathbb{E}[d(X,\hat{X})] \leq D} I(X; \hat{X})$$ 对于一般的信源分布 $p(x)$ 和失真函数 $d(x,\hat{x})$，这个优化问题没有闭式解。Blahut-Arimoto算法提供了迭代数值求解方法。

4.1.2 拉格朗日形式

引入拉格朗日乘子 $\beta \geq 0$，将约束优化转化为无约束优化： $$F(\beta) = \min_{p(\hat{x}|x)} \left[ I(X; \hat{X}) + \beta \mathbb{E}[d(X, \hat{X})] \right]$$ 关系：参数 $\beta$ 控制率失真权衡的工作点

$\beta = 0$：只关心率，最优解是 $p(\hat{x}|x) = p(\hat{x})$（独立），失真最大
$\beta \to \infty$：只关心失真，最优解趋向无损（$\hat{X} = X$）

通过变化 $\beta$，可以得到整条率失真曲线 $R(D)$。

4.1.3 算法推导

将互信息展开： $$I(X;\hat{X}) = \sum_{x,\hat{x}} p(x) p(\hat{x}|x) \log \frac{p(\hat{x}|x)}{p(\hat{x})}$$ 其中 $p(\hat{x}) = \sum_x p(x) p(\hat{x}|x)$。

目标函数为： $$F = \sum_{x,\hat{x}} p(x) p(\hat{x}|x) \left[\log \frac{p(\hat{x}|x)}{p(\hat{x})} + \beta d(x,\hat{x})\right]$$ 使用变分法，令 $\frac{\partial F}{\partial p(\hat{x}|x)} = 0$（加上归一化约束），得到最优解的形式： $$p^*(\hat{x}|x) = \frac{p(\hat{x}) \exp[-\beta d(x,\hat{x})]}{\sum_{\hat{x}'} p(\hat{x}') \exp[-\beta d(x,\hat{x}')]}$$ 定义 $Z(x,\beta) = \sum_{\hat{x}'} p(\hat{x}') \exp[-\beta d(x,\hat{x}')]$，则： $$p^*(\hat{x}|x) = \frac{p(\hat{x}) \exp[-\beta d(x,\hat{x})]}{Z(x,\beta)}$$ 这是一个自洽方程：$p(\hat{x}|x)$ 依赖于 $p(\hat{x})$，而 $p(\hat{x})$ 又依赖于 $p(\hat{x}|x)$。

更深入的理解：

这个最优解的形式有深刻的物理和信息论意义：

玻尔兹曼分布的类比：形式 $\exp[-\beta d(x,\hat{x})]$ 类似于统计物理中的玻尔兹曼分布 $\exp[-E/kT]$，其中 $\beta$ 对应"逆温度"$1/T$，失真 $d(x,\hat{x})$ 对应"能量"$E$。 - $\beta$ 小（高温）：分布接近均匀，容忍大失真 - $\beta$ 大（低温）：分布集中在低失真的 $\hat{x}$ 上
软量化 vs 硬量化： - 当 $\beta \to \infty$：$p(\hat{x}|x)$ 退化为 $\delta$ 函数，集中在失真最小的 $\hat{x}$（确定性量化） - 有限 $\beta$：$p(\hat{x}|x)$ 是软分布，以概率方式选择 $\hat{x}$（随机量化）
先验 $p(\hat{x})$ 的作用： - $p(\hat{x})$ 大 → 该重建点更"受欢迎" → $p(\hat{x}|x)$ 倾向选择它 - 这体现了"频繁使用的码字应该对应更多的信源值"的直觉 - 在信息论中，这对应于码字的先验概率，影响平均码长

为什么这个形式是最优的？

通过拉格朗日乘子法的KKT条件可以严格推导。核心思想是：在满足归一化约束 $\sum_{\hat{x}} p(\hat{x}|x) = 1$ 下，目标函数关于每个 $p(\hat{x}|x)$ 的梯度为零。具体计算： $$\frac{\partial}{\partial p(\hat{x}|x)} \left[p(x) p(\hat{x}|x) \left(\log \frac{p(\hat{x}|x)}{p(\hat{x})} + \beta d(x,\hat{x})\right)\right] = p(x) \left[\log \frac{p(\hat{x}|x)}{p(\hat{x})} + 1 + \beta d(x,\hat{x})\right]$$ 令其等于拉格朗日乘子 $\lambda(x)$（对应归一化约束），解出： $$\log p(\hat{x}|x) = \lambda(x) - 1 - \beta d(x,\hat{x}) + \log p(\hat{x})$$ 即： $$p(\hat{x}|x) = p(\hat{x}) \exp[\lambda(x) - 1 - \beta d(x,\hat{x})]$$ 利用归一化条件 $\sum_{\hat{x}} p(\hat{x}|x) = 1$，确定 $\lambda(x)$： $$\exp[\lambda(x) - 1] = \frac{1}{\sum_{\hat{x}'} p(\hat{x}') \exp[-\beta d(x,\hat{x}')]} = \frac{1}{Z(x,\beta)}$$ 代入即得最优解。

4.1.4 Blahut-Arimoto迭代

算法流程（给定 $\beta$）：

初始化：选择初始分布 $p^{(0)}(\hat{x})$（如均匀分布）
迭代 $t = 0, 1, 2, ...$： - E步：根据当前 $p^{(t)}(\hat{x})$ 计算 $$p^{(t)}(\hat{x}|x) = \frac{p^{(t)}(\hat{x}) \exp[-\beta d(x,\hat{x})]}{\sum_{\hat{x}'} p^{(t)}(\hat{x}') \exp[-\beta d(x,\hat{x}')]}$$

M步：更新边缘分布 $$p^{(t+1)}(\hat{x}) = \sum_x p(x) p^{(t)}(\hat{x}|x)$$

收敛判断：当 $|p^{(t+1)}(\hat{x}) - p^{(t)}(\hat{x})| < \epsilon$ 时停止

输出：收敛后的 $p^*(\hat{x}|x)$，计算 $R = I(X;\hat{X})$ 和 $D = \mathbb{E}[d(X,\hat{X})]$，得到率失真曲线上的一个点 $(R, D)$。

扫描 $\beta$：通过改变 $\beta$ 从 $0$ 到 $\infty$，得到完整的率失真曲线。

4.1.5 收敛性和性质

定理：Blahut-Arimoto算法保证收敛到全局最优解。

收敛速度：通常几十次迭代即可收敛，收敛是线性的。

计算复杂度：每次迭代 $O(|\mathcal{X}| \cdot |\hat{\mathcal{X}}|)$，其中 $|\mathcal{X}|$ 和 $|\hat{\mathcal{X}}|$ 分别是信源和重建的字母表大小。

Rule of thumb：Blahut-Arimoto算法是计算一般信源率失真函数的标准方法。对于离散信源，只要字母表不太大（< 100），算法都很高效。

4.1.6 数值技巧

1. 对数空间计算：为避免下溢，用 $\log p(\hat{x})$ 代替 $p(\hat{x})$： $$\log p(\hat{x}|x) = \log p(\hat{x}) - \beta d(x,\hat{x}) - \log Z(x,\beta)$$ 其中 $\log Z(x,\beta) = \text{LogSumExp}_{\hat{x}} [\log p(\hat{x}) - \beta d(x,\hat{x})]$。

2. $\beta$ 的选择：使用对数尺度，如 $\beta \in \{10^{-3}, 10^{-2}, ..., 10^3\}$，在率失真曲线的不同区域取足够密的点。

3. 初始化：从 $\beta$ 小的点开始，用前一个 $\beta$ 的收敛解作为下一个 $\beta$ 的初始值，加速收敛。

4.2 矢量量化基础

4.2.1 从标量到矢量

标量量化：每次量化一个样本 $x \in \mathbb{R}$ $$\hat{x} = Q(x) \in \{\hat{x}_1, ..., \hat{x}_M\}$$ 矢量量化（Vector Quantization, VQ）：每次量化一个向量 $\mathbf{x} \in \mathbb{R}^k$ $$\hat{\mathbf{x}} = Q(\mathbf{x}) \in \{\mathbf{c}_1, ..., \mathbf{c}_M\}$$ 其中 $\\{\mathbf{c}_1, ..., \mathbf{c}_M\\}$ 称为码本（codebook），$\mathbf{c}_i$ 称为码字或代表点。

编码：找最近的码字（最近邻规则） $$Q(\mathbf{x}) = \arg\min_{\mathbf{c}_i} |\mathbf{x} - \mathbf{c}_i|^2$$ 码率：$R = \frac{\log M}{k}$ 比特/样本

4.2.2 矢量量化的优势

为什么矢量量化更好？

定理（Shannon）：对于给定码率 $R$，当向量维度 $k \to \infty$ 时，矢量量化的失真逼近率失真函数 $R(D)$。而标量量化的失真通常严格大于 $R(D)$。

直观解释：

联合建模：矢量量化利用向量分量之间的相关性
形状适配：码字可以适应信源在高维空间的分布形状
维度增益：高维空间的"集中现象"（典型集）使量化更有效

具体示例分析：

考虑二维均匀分布源 $\mathbf{X} = (X_1, X_2)$，$X_1, X_2 \in [-1, 1]$ 独立均匀分布。码率 $R = 1$ 比特/样本（即 2 比特/向量）。

标量量化方案：

分别量化 $X_1$ 和 $X_2$，每个使用 $M=2$ 个量化点（1 比特）：

$X_1$ 的量化点：$\{-0.5, 0.5\}$
$X_2$ 的量化点：$\{-0.5, 0.5\}$
总共 $2 \times 2 = 4$ 个码字（2D网格）

量化误差（均方）： $$D_{\text{scalar}} = \mathbb{E}[(X_1 - \hat{X}_1)^2] + \mathbb{E}[(X_2 - \hat{X}_2)^2]$$ 对于均匀分布在 $[-1, 1]$ 上，用 2 个量化点，每个区域宽度为 1，均方误差约为 $\frac{1}{12}$（区间宽度平方/12）。因此： $$D_{\text{scalar}} \approx 2 \times \frac{1}{12} = \frac{1}{6} \approx 0.167$$ 矢量量化方案：

联合量化 $(X_1, X_2)$，使用 $M=4$ 个 2D 码字。最优放置（对均匀分布）是六边形排列或均匀分布的 4 个点。

例如，使用以下 4 个码字（近似最优）：

$\mathbf{c}_1 = (-0.5, -0.5)$
$\mathbf{c}_2 = (-0.5, 0.5)$
$\mathbf{c}_3 = (0.5, -0.5)$
$\mathbf{c}_4 = (0.5, 0.5)$

这看起来和标量量化一样？但关键区别是：矢量量化可以优化码字位置以最小化失真。

对于均匀分布，最优的 4 点配置实际上是正方形的顶点（等间距）。失真计算： $$D_{\text{vector}} \approx \frac{1}{6}$$ 等等，这个例子中标量和矢量性能相同，因为分量独立且分布相同。让我换一个更好的例子。

更好的示例：相关高斯源

考虑二维高斯源 $\mathbf{X} = (X_1, X_2)$ 满足 $X_1, X_2 \sim \mathcal{N}(0, 1)$，但相关：$\text{Cov}(X_1, X_2) = \rho$（$\rho > 0$）。

信源在 2D 空间形成椭圆分布，主轴沿对角线方向。

标量量化：

分别量化 $X_1$ 和 $X_2$，忽略相关性
码字形成正方形网格
失真：$D_{\text{scalar}}$（忽略了协方差结构）

矢量量化：

码字可以沿椭圆的主轴方向排列
更密集地覆盖高概率区域（椭圆中心）
失真：$D_{\text{vector}} < D_{\text{scalar}}$

量化增益：

对于高斯源，当 $k=2$ 时，矢量量化相比标量量化的增益约为： $$G_{k=2} \approx 0.5 \text{ dB}$$ 当 $k \to \infty$ 时，增益达到： $$G_{k \to \infty} = \frac{\pi e}{6} \approx 2.2 \text{ dB}$$ 这就是"形状增益"（shape gain），来源于矢量量化能够适应信源分布的形状。

维度增益的直观理解：

在高维空间，信源分布集中在一个"薄壳"上（典型集）。矢量量化可以精确覆盖这个薄壳，而标量量化必须覆盖整个超立方体，浪费了大量码字在低概率区域。

2D示意（高斯分布）：

    X2
     |     ·····     <- 高概率区域（椭圆）
     |   ··   ··
     |  ·   *   ·    <- 矢量量化码字（沿椭圆分布）
     | ·   * *   ·
     +--·-*-*-*-·--- X1
       ·   * *   ·
        ·   *   ·
         ··   ··
           ·····

    网格点 = 标量量化（忽略椭圆形状）

    * 点 = 矢量量化（适应椭圆形状）

Rule of thumb：矢量量化相比标量量化，在相同码率下可以降低失真约 $\frac{1}{2}\log(2\pi e) \approx 1.5$ 比特/维（对高斯源）。这称为"形状增益"。对于相关源或非均匀分布，增益更加显著。

4.2.3 量化区域与Voronoi分割

给定码本 $\\{\mathbf{c}_1, ..., \mathbf{c}_M\\}$，量化器将空间分割为 $M$ 个区域： $$V_i = \\{\mathbf{x} : Q(\mathbf{x}) = \mathbf{c}_i\\} = \\{\mathbf{x} : |\mathbf{x} - \mathbf{c}_i|^2 \leq |\mathbf{x} - \mathbf{c}_j|^2, \forall j \neq i\\}$$ 这些区域称为Voronoi区域，它们构成Voronoi图。

性质：

Voronoi区域是凸多面体
相邻区域的边界是超平面
最近邻规则等价于Voronoi分割

二维Voronoi图示意（ASCII）：
           |     /
    V1     |    / V2
           | c1/
      -----+---+----
          /|   |c2
         / |   |
        /  |V3 |
       / V4|   |

4.3 Lloyd-Max算法

4.3.1 问题设定

目标：给定信源分布 $p(\mathbf{x})$、码本大小 $M$，设计最优码本 $\\{\mathbf{c}_1, ..., \mathbf{c}_M\\}$ 使平均失真最小： $$\min_{\mathbf{c}_1,...,\mathbf{c}_M} \mathbb{E}[|\mathbf{X} - Q(\mathbf{X})|^2]$$

4.3.2 Lloyd算法（K-means）

Lloyd算法（也称为LBG算法、K-means聚类）是矢量量化码本设计的经典方法：

初始化：随机选择 $M$ 个码字 $\\{\mathbf{c}_1^{(0)}, ..., \mathbf{c}_M^{(0)}\\}$
迭代 $t = 0, 1, 2, ...$： - 最近邻分配：对每个训练向量 $\mathbf{x}_n$，分配到最近的码字 $$i_n = \arg\min_i |\mathbf{x}_n - \mathbf{c}_i^{(t)}|^2$$

质心更新：更新每个码字为其区域的质心 $$\mathbf{c}_i^{(t+1)} = \frac{\sum_{n: i_n=i} \mathbf{x}_n}{|\{n: i_n=i\}|}$$

收敛判断：当失真变化小于阈值时停止

收敛性：Lloyd算法保证失真单调递减，收敛到局部最优（不保证全局最优）。

4.3.3 最优性条件

定理（Lloyd-Max条件）：最优量化器必须满足：

最近邻条件：量化区域是Voronoi分割
质心条件：每个码字是其Voronoi区域的质心（期望意义下） $$\mathbf{c}_i = \mathbb{E}[\mathbf{X} | \mathbf{X} \in V_i] = \frac{\int_{V_i} \mathbf{x} p(\mathbf{x}) d\mathbf{x}}{\int_{V_i} p(\mathbf{x}) d\mathbf{x}}$$ Lloyd算法正是交替优化这两个条件。

4.3.4 与率失真理论的联系

Lloyd算法求解的是固定码率（固定 $M$）下的最小失真问题： $$D(R) = \min_{M=2^{kR}} \min_{\text{VQ}} \mathbb{E}[d(\mathbf{X}, \hat{\mathbf{X}})]$$ 这对应率失真曲线 $D(R)$ 的一个点。

关系：

率失真理论给出理论下界 $D_{\min}(R)$（渐近最优，$k \to \infty$）
Lloyd算法给出实际可达的失真 $D_{\text{Lloyd}}(R)$（有限 $k$）
差距来源：有限维度损失、码本大小限制、局部最优

更深层的理论联系：

Lloyd算法和率失真理论实际上是从不同角度解决同一个优化问题：

率失真理论视角： - 优化变量：条件概率分布 $p(\hat{\mathbf{x}}|\mathbf{x})$（测试信道） - 目标：$\min I(\mathbf{X}; \hat{\mathbf{X}})$ subject to $\mathbb{E}[d] \leq D$ - 解：软量化（概率性映射）
Lloyd算法视角： - 优化变量：码本 $\{\mathbf{c}_1, ..., \mathbf{c}_M\}$ 和分区 $\{V_1, ..., V_M\}$ - 目标：$\min \mathbb{E}[d(\mathbf{X}, Q(\mathbf{X}))]$ subject to $|\text{codebook}| = M$ - 解：硬量化（确定性映射）

连接桥梁：硬量化 vs 软量化

Lloyd算法产生的确定性量化器 $\hat{\mathbf{x}} = Q(\mathbf{x})$ 可以看作率失真理论中 $\beta \to \infty$ 的极限情况。在有限 $\beta$ 下，Blahut-Arimoto算法给出软量化（$p(\hat{\mathbf{x}}|\mathbf{x})$ 是分布），而当 $\beta \to \infty$ 时，这个分布退化为确定性映射。

性能差距的来源：

设 $k$ 维矢量量化，码本大小 $M = 2^{kR}$。理论和实际之间的差距可以分解为： $$D_{\text{Lloyd}}(R) = D_{\text{RD}}(R) + \Delta_{\text{finite-k}} + \Delta_{\text{local-opt}} + \Delta_{\text{finite-M}}$$ 其中：

$\Delta_{\text{finite-k}}$：有限维度损失（$k$ 不够大）
$\Delta_{\text{local-opt}}$：Lloyd算法局部最优（非全局最优）
$\Delta_{\text{finite-M}}$：码本大小有限（量化颗粒度）

实际性能分析：

对于 $k$ 维i.i.d.高斯源 $\mathbf{X} \sim \mathcal{N}(0, \sigma^2 \mathbf{I})$，码率 $R$ 比特/样本：

率失真界：$D_{\text{RD}} = \sigma^2 2^{-2R}$
Lloyd-VQ（有限$k$）：$D_{\text{Lloyd}} \approx \sigma^2 2^{-2R} \cdot G(k)^{-1}$

其中 $G(k)$ 是维度 $k$ 的形状增益： $$G(k) \approx \frac{k}{2\pi e} \left(\frac{2\pi e}{k}\right)^{2/k}$$

当 $k \to \infty$ 时，$G(k) \to \frac{1}{2\pi e}$，失真趋于率失真界。

数值例子：

| 维度 $k$ | 形状增益 $G(k)$ | 性能损失（dB） |

维度 $k$	形状增益 $G(k)$	性能损失（dB）
1	1	4.35 dB
2	1.13	3.82 dB
4	1.22	3.25 dB
8	1.29	2.76 dB
16	1.33	2.45 dB
$\infty$	1.42	2.2 dB（极限）

这表明：

即使 $k=8$，也能达到距理论界约 2.8 dB 的性能
$k=16$ 时，性能已经非常接近极限
继续增大 $k$ 的边际收益递减

Rule of thumb：对于高斯源，Lloyd算法设计的矢量量化器（维度 $k \approx 8$-$16$）可以达到距率失真界约 1-2 dB 的性能（考虑良好的初始化和避免局部最优），这在实际应用中是很好的。对于实际系统，$k=8$ 通常是性能和复杂度的最佳平衡点。

4.4 标量量化 vs 矢量量化

4.4.1 性能对比

高斯源，平方误差失真：

| 方法 | 失真（相同码率 $R$） | 增益（dB） |

方法	失真（相同码率 $R$）	增益（dB）
率失真界	$D_{RD} = \sigma^2 2^{-2R}$	基准
最优标量量化	$D_{SQ} \approx \frac{\pi e}{6} \sigma^2 2^{-2R}$	$-2.2$ dB
矢量量化（$k \to \infty$）	$D_{VQ} \to D_{RD}$	$0$ dB

解释：标量量化比率失真界差约 2.2 dB，而理想矢量量化可以达到率失真界。

实际矢量量化（有限 $k$）：

随着维度 $k$ 增加，矢量量化性能逐渐接近率失真界：

$k=2$：增益约 0.5 dB
$k=4$：增益约 1 dB
$k=8$：增益约 1.5 dB
$k \to \infty$：增益 2.2 dB

4.4.2 复杂度对比

编码复杂度：

标量量化：$O(M)$（搜索 $M$ 个标量码字）
矢量量化：$O(kM)$（计算 $M$ 个 $k$ 维向量的距离）

存储需求：

标量量化码本：$M$ 个标量
矢量量化码本：$M$ 个 $k$ 维向量

权衡：矢量量化性能更好，但复杂度和存储需求更高。实际中常用 $k=2$-$8$ 的折衷。

4.4.3 结构化矢量量化

为降低复杂度，实际中常用结构化矢量量化：

1. 乘积量化（Product Quantization）：将 $k$ 维向量分为 $m$ 个子向量，每个独立量化

复杂度：$O(m \cdot M^{1/m})$（远小于 $O(kM)$）
性能损失：约 1-2 dB

2. 树结构量化（Tree-Structured VQ）：用二叉树组织码本，每次决策只需比较 2 个码字

复杂度：$O(k \log M)$
性能损失：约 1-3 dB

3. 格量化（Lattice Quantization）：使用规则的几何结构（如立方格、六边形格）

编码极快（只需取整运算）
性能接近最优（高维下）

Rule of thumb：乘积量化和格量化在实际系统（如图像/视频编码器、向量数据库）中广泛应用，它们在性能和复杂度之间提供了良好的权衡。

4.5 本章小结

核心概念：

Blahut-Arimoto算法： - 迭代求解率失真函数的数值方法 - E步：更新 $p(\hat{x}|x)$，M步：更新 $p(\hat{x})$ - 保证收敛到全局最优
矢量量化： - 联合量化多个样本，利用相关性 - 渐近最优（$k \to \infty$）可达率失真界 - 性能增益：相比标量量化约 1.5-2 dB
Lloyd-Max算法： - 最近邻分配 + 质心更新 - 等价于K-means聚类 - 固定码率下的最小失真
性能-复杂度权衡： - 标量量化：简单但次优 - 矢量量化：最优但复杂 - 结构化VQ：折衷方案

关键算法：

Blahut-Arimoto迭代：

E步：p(ŷ|x) = p(ŷ)exp[-βd(x,ŷ)] / Z(x,β)
M步：p(ŷ) = Σx p(x)p(ŷ|x)

Lloyd算法：

分配：i_n = argmin_i ||x_n - c_i||²
更新：c_i = (1/|S_i|) Σ_{n∈S_i} x_n

4.6 常见陷阱与错误

Gotcha #1: Blahut-Arimoto的初始化

错误：使用不合理的初始 $p^{(0)}(\hat{x})$（如全零或非归一化的）。

正解：使用均匀分布 $p^{(0)}(\hat{x}) = 1/|\hat{\mathcal{X}}|$ 是安全的选择。虽然算法对初始化不太敏感（总会收敛），但好的初始化能加速收敛。对于 $\beta$ 扫描，用前一个 $\beta$ 的解初始化下一个。

Gotcha #2: $\beta$ 与 $D$ 的对应

错误：认为 $\beta$ 直接对应失真 $D$。

正解：$\beta$ 是拉格朗日乘子，而非失真本身。它控制率失真权衡的"陡峭程度"。给定 $\beta$，需要运行算法收敛后计算实际的 $D = \mathbb{E}[d(X,\hat{X})]$。$\beta$ 和 $D$ 的关系是单调的但非线性的。

Gotcha #3: 矢量量化的"维度诅咒"

错误：认为维度越高越好。

正解：虽然理论上 $k \to \infty$ 时性能最优，但实际中存在"维度诅咒"：

训练数据需求：需要 $\gg M$ 个训练向量，$M = 2^{kR}$ 随 $k$ 指数增长
泛化能力：高维下易过拟合
复杂度：搜索和存储开销

实际应用中，$k = 4$-$16$ 是常见的折衷。

Gotcha #4: Lloyd算法的局部最优

错误：认为Lloyd算法找到全局最优码本。

正解：Lloyd算法只保证收敛到局部最优。不同初始化可能收敛到不同的局部最优。实际中常用多次随机初始化，选最好的结果。

改进方法：

K-means++初始化（选择远离已有码字的初始点）
模拟退火、遗传算法等全局优化方法

Gotcha #5: 标量量化的独立性假设

错误：对相关信源直接使用标量量化。

正解：标量量化假设样本独立。对于相关信源（如相邻像素、时间序列），应该先去相关（通过预测、变换如DCT），再标量量化。这就是预测编码和变换编码的思想。

或者直接使用矢量量化，它天然处理相关性。

Gotcha #6: 混淆码本大小和码率

错误：认为码本大小 $M$ 就是码率。

正解：

对于标量量化：码率 $R = \log M$ 比特/样本
对于 $k$ 维矢量量化：码率 $R = \frac{\log M}{k}$ 比特/样本

别忘了除以维度！

Gotcha #7: 忽略熵编码

错误：认为矢量量化后直接输出索引（每个索引 $\log M$ 比特）。

正解：如果码字被选择的概率不同（即 $p(\mathbf{c}_i)$ 不均匀），应该在矢量量化后再做熵编码（如霍夫曼编码、算术编码），可以进一步降低码率到 $H(Q(\mathbf{X}))$。

率失真理论中的"码率"$R = I(X;\hat{X})$ 已经包含了这一点，但实际实现中需要显式的熵编码器。

下一章预告：第五章将讨论超越MSE的失真度量，探索感知失真和率失真感知（RDP）权衡的前沿理论。

← 第三章 | 返回目录 | 第五章：感知失真度量与率失真感知权衡 →