9.3 率失真定理证明

率失真定理证明

率失真定理（Rate-Distortion Theorem）确立了率失真函数 $R(D)$ 作为有损压缩可达码率下界的核心地位。该定理包含两个方向：反向证明（Converse）断言任何满足平均失真不超过 $D$ 的编码方案，其码率 $R$ 必然满足 $R\ge R(D)$；正向证明（Achievability）断言若 $R>R(D)$，则存在一种编码方案使得平均失真不超过 $D$。两者共同刻画了有损压缩的理论极限。

反向证明（Converse）。 考虑一个 $(n,M)$ 分组编码方案，编码器将长度为 $n$ 的信源序列 $X^n$ 映射到索引 $W\in \{1,\dots ,M\}$，解码器将索引 $W$ 映射到重构序列 ${\hat{X}}^n$。由编码解码过程构成马尔可夫链 $X^n\to W\to {\hat{X}}^n$，根据数据处理不等式可得：

$I(X^n;{\hat{X}}^n)\le I(X^n;W)\le H(W)\le \log M=nR$

其中 $R=\frac{1}{n}\log M$ 为码率。另一方面，由信源的独立同分布性质以及率失真函数的定义，若平均失真 $\frac{1}{n}{\sum }_{i=1}^n\mathbb{E}[d(X_i,{\hat{X}}_i)]\le D$，则有 $\frac{1}{n}I(X^n;{\hat{X}}^n)\ge R(D)$。联立两式即得 $R\ge R(D)$，反向证明完成。该证明的关键在于利用率失真函数的凸性和信源的独立同分布性质，将总互信息分解为各分量互信息之和的下界，进而得到码率的下界。

正向证明（Achievability）。 正向证明采用随机编码和强典型集技术。固定条件分布 $p(\hat{x}|x)$ 满足 $\mathbb{E}[d(X,\hat{X})]\le D$，计算边缘分布 $p(\hat{x})={\sum }_{x}p(x)p(\hat{x}|x)$。随机生成码本 $\mathcal{C}$，包含 $2^{nR}$ 个独立同分布的重构序列 ${\hat{X}}^n(m)$（$m=1,\dots ,2^{nR}$），每个序列按 $p(\hat{x})$ 独立生成。编码时，给定信源序列 $x^n$，编码器在码本中搜索使得 $(x^n,{\hat{X}}^n(m))$ 为联合典型的索引 $m$；若存在这样的 $m$，则输出该索引，否则输出固定索引（编码失败）。解码器将接收到的索引 $m$ 映射到对应的重构序列 ${\hat{X}}^n(m)$。

利用强典型集的性质，当 $n$ 充分大时，联合典型序列 $(x^n,{\hat{x}}^n)$ 的数量约为 $2^{nH(X,\hat{X})}$，而对于给定的 $x^n$，与之联合典型的 ${\hat{x}}^n$ 数量约为 $2^{nH(\hat{X}|X)}$。随机码本中每个重构序列与 $x^n$ 联合典型的概率约为 $2^{-nI(X;\hat{X})}$。因此，当 $R>I(X;\hat{X})$ 时，码本中存在至少一个联合典型重构序列的概率趋于 $1$。同时，由强典型性质，联合典型序列的经验失真以概率 $1$ 趋近期望失真 $\mathbb{E}[d(X,\hat{X})]$。综合以上分析，取满足 $I(X;\hat{X})<R$ 且 $\mathbb{E}[d(X,\hat{X})]\le D$ 的条件分布 $p(\hat{x}|x)$，当 $n\to \infty$ 时，存在以码率 $R$ 达到平均失真 $D$ 的编码方案。由率失真函数定义，$R(D)=\min I(X;\hat{X})$，因而对于任意 $ϵ>0$，取 $R=R(D)+ϵ$ 即可达到失真 $D$。

率失真定理与信道编码定理的对比。 两者在数学结构上具有对偶性：信道编码定理是在给定信道转移概率 $p(y|x)$ 的条件下，寻找输入分布 $p(x)$ 以最大化互信息，并证明当 $R<C$ 时可靠通信可达；率失真定理是在给定信源分布 $p(x)$ 的条件下，寻找条件分布 $p(\hat{x}|x)$ 以最小化互信息，并证明当 $R>R(D)$ 时有损压缩可达。信道编码需要”填满”信道容量，率失真需要”排空”信源冗余。对偶性的数学根源在于互信息 $I(X;Y)$ 既是 $p(x)$ 的凹函数，也是 $p(y|x)$ 的凸函数，这一性质使得两者分别在最大化与最小化的优化问题中具有良好的可解性。

链接到

• 上一个知识点：9.2 率失真函数
• 下一个知识点：无（本章最后一个知识点）