西电 - 网络信息论 第七章：Blahut-Arimoto 算法 — 容量计算的交替最大化方法

第七章 Blahut-Arimoto 算法（Blahut-Arimoto Algorithms）

课程: 网络信息论（Network Information Theory）
教材: A. El Gamal and Y.-H. Kim, Network Information Theory, Cambridge University Press, 2011
整理说明: 本章专门介绍计算信道容量和 BC 容量区域的 Blahut-Arimoto (BA) 算法——一种通过交替最大化（Alternative Maximization）来求解互信息最大化问题的迭代算法。从离散信道的经典 BA 算法出发，逐步扩展到退化 BC、一般 BC（SCIB/MIB/UVOB），以及连续信道（AWGN）的矩阵迭代版本。本章26年不考。
免责声明：本笔记内容来源于课程讲义和PPT，经AI辅助汇总完成，仅供学习参考。如有错误或遗漏，请以原始课程资料为准。

目录

1. 问题背景与梯度上升
2. BA 算法的核心思想——交替最大化
3. BA 算法：给定 q 求最优 Q
4. BA 算法：给定 Q 求最优 q
5. 收敛性分析
6. 停止准则与图示
7. BA 算法在退化广播信道中的应用
8. BA 算法在一般广播信道中的应用
9. 连续信道的 BA 算法
10. 数值结果与考试重点

1. 问题背景与梯度上升

1.1 信道容量的计算问题

点对点信道 $p(y|x)$ 的容量定义为：

$$\boxed{C = \max_{q(x)} I(X; Y)}$$

其中 $I(X;Y)$ 是输入分布 $q(x)$ 的凹函数。

虽然容量有简洁的闭式表达，但对于一般的离散无记忆信道（DMC），没有解析解——需要用数值算法来求解最优输入分布 $q^*(x)$。

1.2 梯度上升法

最直接的方法：梯度上升。

假设 $|\mathcal{X}| = n$，自由变量为 $q_X(1), q_X(2), \ldots, q_X(n-1)$（最后一个由 $\sum q = 1$ 确定）。

梯度公式:

$$\frac{\partial I(X;Y)}{\partial q(x)} = \sum_y \big(p(y|n) - p(y|x)\big)\ln q(y) + H(Y|X=n) - H(Y|X=x)$$

更新规则: $q \leftarrow q + \tau \cdot \nabla I(q)$

例：Z 信道

信道矩阵 $W_{ij} = p(Y=j | X=i)$:

$$W = \begin{pmatrix} 1 & 0 \\\\ 0.5 & 0.5 \end{pmatrix}$$

• 梯度上升：步长 0.1，初始 $p_X(0) = 0.2$
• 收敛到最优值 $p_X^*(0) = 0.6$

梯度上升的问题：步长选择敏感，收敛速度不保证，需要投影回概率单纯形。

2. BA 算法的核心思想——交替最大化

Blahut 和 Arimoto 于 1972 年独立提出了更优雅的算法。核心技巧是将原问题重构为双变量的交替最大化问题。

2.1 目标函数重构

原始问题：

$$\max_{q(x)} I(X;Y) = \max_{q(x)} \sum_{x,y} q(x)p(y|x) \ln\frac{q(x|y)}{q(x)}$$

引入辅助变量 $Q(x|y)$（一个条件分布），构造扩展的目标函数：

$$\boxed{f(q, Q) = \sum_{x,y} q(x)p(y|x) \ln\frac{Q(x|y)}{q(x)}}$$

🔑 关键性质:

1. $f(q) = I(X;Y) = f(q, Q) + D{X|Y}(q | Q)$，其中 $D{X|Y}$ 是条件 KL 散度
2. $f(q) \geq f(q, Q)$ 对所有 $Q$ 成立（因为 KL 散度 $\geq 0$）
3. 给定 $q$，最优的 $Q$ 是 $Qq = q(x|y)$（后验概率），此时 $D_{X|Y}=0$

交替最大化流程: $q_0 \to Q_1 \to q_1 \to Q_2 \to q_2 \to \cdots$，每一步都保证目标函数不降。

2.2 为什么交替最大化有效？

原问题 $f(q)$ 虽然对 $q$ 是凹的，但直接优化仍不方便。引入 $Q$ 后：

• $f(q, Q)$ 对 $q$ 是凹的（给定 $Q$ 时）
• $f(q, Q)$ 对 $Q$ 是凹的（给定 $q$ 时）
• 每一步子问题都有闭式解！

3. BA 算法：给定 q 求最优 Q

3.1 推导

$$f(q) = f(q, Q) + \underbrace{\sum_y q(y) \sum_x q(x|y) \ln\frac{q(x|y)}{Q(x|y)}}_{D_{X|Y}(q\|Q) \;\geq\; 0}$$

条件 KL 散度 $D_{X|Y}(q|Q) \geq 0$，等号成立当且仅当 $Q(x|y) = q(x|y)$（对所有 $x,y$）。

因此，给定 $q$，最优 $Q[q]$ 就是后验概率分布：

$$\boxed{Q[q](x|y) = q(x|y) = \frac{q(x)p(y|x)}{\sum_{x'} q(x')p(y|x')}} \tag{1}$$

且此时 $f(q) = f(q, Q[q]) \geq f(q, Q)$（对所有 $Q$）。

4. BA 算法：给定 Q 求最优 q

4.1 推导

将 $f(q, Q)$ 写为”标准形式”：

$$f(q, Q) = \sum_x q(x) \sum_y p(y|x) \ln\frac{Q(x|y)}{q(x)} = \sum_x q(x)\big(d[Q](x) - \ln q(x)\big)$$

其中定义了关键量：

$$\boxed{d[Q](x) = \sum_y p(y|x) \ln Q(x|y)}$$

$dQ$ 可理解为在给定 $Q$ 下，输入 $x$ 的”信息势能”（information potential）。

4.2 拉格朗日乘子法

给定 $Q$，求解 $\max_{q} f(q, Q)$，约束 $\sum_x q(x) = 1$：

$$\frac{\partial}{\partial q(x)}\left[\sum_{x'} q(x')(d[Q](x') - \ln q(x')) + \lambda\Big(1 - \sum_{x'} q(x')\Big)\right] = 0$$ $$\implies d[Q](x) - \ln q(x) - 1 - \lambda = 0$$ $$\implies q(x) \propto \exp\{d[Q](x)\}$$

归一化后:

$$\boxed{q[Q](x) = \frac{1}{S_d} \exp\{d[Q](x)\}} \tag{2}$$

其中 $Sd = \sum{x’} \exp{dQ}$ 是归一化常数。

4.3 两个重要推论

由 (2) 直接可得：

$$\boxed{d[Q](x) - \ln q[Q](x) \equiv \ln S_d} \tag{3}$$

（对所有 $x$ 恒为常数！）

以及：

$$\boxed{f(q[Q], Q) = \ln S_d = \ln \sum_x \exp\{d[Q](x)\}} \tag{4}$$

4.4 BA 算法的一次完整迭代

算法伪代码:

初始化: q₀(x)（通常均匀分布）
重复:
  1. Q_{k}(x|y) = q_{k-1}(x|y)        // 后验概率
  2. d_k(x) = Σ_y p(y|x) ln Q_k(x|y)  // 信息势能
  3. q_k(x) ∝ exp{d_k(x)}             // 更新输入分布
  停止: 当 q_k ≈ q_{k-1}

5. 收敛性分析

5.1 单调性

每一步保证目标函数不降：

$$f(q_{k-1}) = f(q_{k-1}, Q_k) \leq f(q_k, Q_k) = \ln S_d^{(k)}$$

即 $f(qk) \geq f(q{k-1})$。序列 ${f(q_k)}$ 单调不减且有上界（最大互信息 $C$），因此收敛。

5.2 收敛速度

令 $q^*$ 为真实最优分布。可以证明：

$$\sum_{n=1}^{N} \big(f(q^*) - f(q_n, Q_n)\big) \leq D_X(q^* \| q_0)$$

解读: 所有迭代的”遗憾”之和被初始分布与最优分布之间的 KL 散度所控制。由于 $f(q^)-f(q_n) \geq 0$ 且求和有界，必然有 $f(q^) - f(q_n, Q_n) \to 0$。

详细推导:

$$\begin{aligned} f(q^*) - f(q_n, Q_n) - \sum_x q^*(x)\ln\frac{q_n(x)}{q_{n-1}(x)} &= \sum_x q^*(x)\big(d[Q_n](x) - \ln q_{n-1}(x)\big) \\\\ &= \sum_{x,y} q^*(x)p(y|x) \ln\frac{q_{n-1}(x|y)}{q_{n-1}(x)} \quad (\text{因为 } Q_n = q_{n-1}(x|y))\\\\ &= \sum_{x,y} q^*(x)p(y|x) \ln\frac{p(y|x)}{q_{n-1}(y)} \\\\ &= -D_Y(q^* \| q_{n-1}) \leq 0 \end{aligned}$$

因此：

$$\sum_{n=1}^{N}\big(f(q^*) - f(q_n, Q_n)\big) \leq D_X(q^*\|q_0) - D_X(q^*\|q_N) \leq D_X(q^*\|q_0)$$

6. 停止准则与图示

6.1 最优性条件（KKT 条件）

$q(x)$ 最大化 $I(X;Y)$ 的充要条件是存在常数 $D$ 使得：

$$\boxed{\sum_y p(y|x) \ln\frac{p(y|x)}{q(y)} \begin{cases} = D, & q(x) > 0 \\\\ \leq D, & q(x) = 0 \end{cases}} \tag{5}$$

物理含义: 在最优分布下，所有被使用的输入（$q(x) > 0$）产生相同的”信息势能” $D$（等于容量 $C$）；未使用的输入势能不超过 $D$。

6.2 停止准则

算法停止当以下差值足够小：

$$\max_x\big(d[Q[q]](x) - \ln q(x)\big) - \sum_x q(x)\big(d[Q[q]](x) - \ln q(x)\big) < \epsilon$$

当 $q = q^*$ 时，由 (3) 知 $dQ[q] - \ln q(x) \equiv \ln S_d$（对所有 $x$），上式恰为 0。

6.3 BA 与梯度上升的对比

             BA 算法                 梯度上升
收敛速度:     快（超线性）              慢（线性，依赖步长）
步长选择:     无需（自动）              需要调参
单调性:       严格单调不减             不一定（可能震荡）
计算量:       每次迭代 O(|X||Y|)      类似
闭式解:       每步有                     每步无（需线搜索）

7. BA 算法在退化广播信道中的应用

7.1 退化 BC 的容量区域支撑超平面

退化 BC $X \to Y \to Z$ 的容量区域边界可由支撑超平面刻画：

$$\theta R_1 + \bar{\theta} R_2 = \begin{cases} \max_{q(x)} I(X; Y), & \theta \in [\frac{1}{2}, 1] \\\\[4pt] \max_{q(u,x)} F(q(u,x)), & \theta \in [0, \frac{1}{2}) \end{cases}$$

其中 $F(q(u,x)) = \theta I(X; Y|U) + \bar{\theta} I(U; Z)$。

7.2 BA 目标函数

$$F(q, Q) = \bar{\theta} \sum_{u,x} q(u,x)\big(d[Q](u,x) - \ln q(u,x)\big)$$

其中（$\theta < 1/2$ 时）:

$$\boxed{d[Q](u,x) = \sum_{y,z} p(y,z|x)\left[\ln Q(x|y,u)Q(u|z) + \frac{\bar{\theta}-\theta}{\bar{\theta}}\ln\frac{Q(y|u)}{p(y|x)}\right]}$$

该表达式与经典 BA 的 $dQ = \sum_y p(y|x)\ln Q(x|y)$ 结构完全相同——只是将单字母 $x$ 替换为”超符号”$(u,x)$，并扩展了 $d[Q]$ 的定义以包含退化 BC 的叠加编码结构。

8. BA 算法在一般广播信道中的应用

8.1 三类界

界	全称	性质
SCIB	叠加编码内界（Superposition Coding Inner Bound）	可达区域
MIB	Marton 内界（Marton’s Inner Bound）	可达区域
UVOB	UV 外界（Nair-El Gamal UV Outer Bound）	不可超越的外界

8.2 SCIB 的 BA 算法

SCIB 的支撑超平面形如：

$$\theta R_1 + \bar{\theta}R_2 = \max_{q(u,x)} \min_{\alpha \in [0,1]} F(\alpha, q(u,x))$$

其中 $F(\alpha, q) = \theta I(X; Y|U) + \bar{\theta}\bar{\alpha}I(U; Y) + \bar{\theta}\alpha I(U; Z)$。

⚠️ max-min 结构——不能直接套用 BA。但通过 Terkelsen 型定理可以交换 max 和 min：

$$\max_q \min_{\alpha} F(\alpha, q) = \min_{\alpha} \max_q F(\alpha, q)$$

迭代算法: 在 BA（最大化 $q$）和梯度下降（最小化 $\alpha$）之间交替：

$$\alpha_{k+1} = \alpha_k - \tau \cdot \bar{\theta} \cdot \big(I(U; Z) - I(U; Y)\big)$$

8.3 MIB 的 BA 算法

Marton 内界的目标函数结构类似，但辅助变量扩展到 $(U,V,W,X)$：

$$M(\alpha, q, Q) = \bar{\theta} \sum_{u,v,w,x} q(u,v,w,x)\big(d[Q](u,v,w,x) - \ln q(u,v,w,x)\big)$$

其中 $d[Q]$ 包含 $\ln Q(w|z), \ln Q(w|y), \ln Q(v|w,z), \ln Q(u|w,y), \ln Q(u|v,w), \ln Q(x|u,v,w)$ 等分量——对应于 Marton 编码中的多种条件结构。

8.4 UVOB 的 BA 算法

UV 外界的目标函数（$\alpha, \beta \in [0,1]$ 满足 $\bar{\theta}\alpha + \theta\beta \geq \max{\theta, \bar{\theta}}$）:

$$G(\alpha, \beta, q, Q) = -(\bar{\theta}\alpha + \theta\beta) \sum_x q(x)\ln q(x) + \cdots$$

有两个辅助函数 $d_1[Q]$ 和 $d_2[Q]$，分别对应两个速率约束。

8.5 BSSC 数值结果

二元偏斜对称 BC（BSSC）:

$$P_{Y|X} = \begin{pmatrix} 1 & 0 \\\\ 0.5 & 0.5 \end{pmatrix}, \quad P_{Z|X} = \begin{pmatrix} 0.5 & 0.5 \\\\ 0 & 1 \end{pmatrix}$$

• 该信道的容量区域未知（BSSC 不属于退化/Less Noisy/More Capable 任一类！）
• 和速率: MIB = 0.3616 bits, UVOB = 0.3725 bits
• MIB ⊊ UVOB：内外界之间有微小但确实的间隙
• BA 算法成功计算了 $\theta = 0.4$ 时的支撑超平面值

9. 连续信道的 BA 算法

9.1 连续信道的挑战

BA 算法对离散有限字母表有效，但不适用于一般连续信道。通常做法是量化——但量化区间缩小会导致状态空间指数增长。

例如 MIB 中，辅助变量空间大小为 $|\mathcal{X}|^3 \cdot (|\mathcal{X}|+4)$。若 $|\mathcal{X}| = 1000$，则约 $10^{12}$ 个状态——不可行。

解决方案: 如果涉及的 pdf 可以由有限参数刻画（如高斯分布仅由均值和协方差决定），BA 算法仍可能适用。

9.2 AWGN 信道的 BA——矩阵迭代

问题: $\max_{0 \preceq M \preceq I} \log|M+S| - \log|S|$，其中输入 $X \sim \mathcal{N}(0, M)$。

BA 算法的矩阵推广:

给定 $q$（即给定 $M$）求 $Q$

$Q(x|y) = q(x|y)$ 是高斯后验：

$$Q(x|y) \sim \mathcal{N}\big(Ay,\; AS\big)$$

其中 $A = M(M+S)^{-1}$，$AS = M(M+S)^{-1}S$（Schur 补）。

给定 $Q$ 求 $q$

$$q[Q](x) \propto \exp\{d[Q](x)\}$$

计算 $dQ = E_{Y|x}[\ln Q(x|Y)]$ 涉及高斯期望，可解析求出——结果仍是高斯分布。

核心推导（slides pp.30-32）:

$$\begin{aligned} d[Q](x) &= \text{const} + E_{Y|x}\big[(x-AY)^T(AS)^{-1}(x-AY)\big] \\\\ &= \text{const} + x^T(I-A)^T(AS)^{-1}(I-A)x \end{aligned}$$

利用 $I-A = S(M+S)^{-1}$ 和 $A^{-1}-I = SM^{-1}$：

$$(I-A)^T(AS)^{-1}(I-A) = (MS^{-1}M+M)^{-1}$$

最终得到矩阵更新规则:

$$\boxed{M_{\text{new}} = MS^{-1}M + M}$$

加上投影以满足功率约束：

特征分解: M = VDV^T
投影:     D_{ii} ← min(D_{ii}, 1)
重构:     M ← V·diag(min(D_{ii},1))·V^T

物理含义: 迭代 $M \leftarrow MS^{-1}M + M$ 在低噪声方向（$S_{ii}$ 小的方向）会增大功率，在高噪声方向会减小功率。经过投影后，最优解是所有特征值都收敛到 1——即 $M^* = I$（各方向等功率），与已知的最优输入分布一致。

9.3 AWGN 广播信道的 BA——矩阵迭代

两用户高斯向量 BC $Y_1 = X + Z_1, Y_2 = X + Z_2$（$Z_i \sim \mathcal{N}(0, S_i)$）。

叠加编码：$X = U + V$，$U \sim \mathcal{N}(0, K_U)$，$V \sim \mathcal{N}(0, K_V)$。

支撑超平面（$\lambda \geq 1$）:

$$R_1 + \lambda R_2 = \max_{0 \preceq K_U \preceq I} \big(\log|K_U+S_1| - \lambda\log|K_U+S_2|\big) \tag{6}$$

矩阵更新规则（投影后）:

$$\boxed{K_U \leftarrow \left[(K_U S_1^{-1} K_U + K_U)^{-1} + \lambda \cdot (K_U + S_2)^{-1}\right]^{-1}}$$

这是 BA 算法在 MIMO 高斯 BC 中的核心迭代公式——交替更新 $K_U$（对应于 $U$ 的协方差矩阵）和 $K_V = I - K_U$。

10. 数值结果与考试重点

10.1 BA 算法迭代效果图示

对于 AWGN 信道（$S = \text{diag}(1,3,5,7,9)$，初始 $M = 0.2I$）:

• 目标函数值: 从 ~0 快速上升到约 1.5 nats（约 20 次迭代接近收敛）
• 特征值收敛: 所有 5 个特征值趋向 1（约 60 次迭代完全收敛）

对于 AWGN BC（$S_1 = \text{diag}(1,3,5,7,9), S_2 = \text{diag}(9,7,5,3,1), \lambda = 2$）:

• 目标函数值: 收敛到约 -13.3 nats
• 特征值收敛: 最大特征值约 0.9，中间 0.5，最小 0.1——体现了”注水”式的功率分配

10.2 考试重点速查表

名称	公式 / 关键点
容量最大化	$C = \max_{q(x)} I(X;Y)$，凹函数
扩展目标函数	$f(q,Q) = \sum_{x,y} q(x)p(y\vert x)\ln\frac{Q(x\vert y)}{q(x)}$
给定 q 求 Q	$Qq = q(x\vert y) = \frac{q(x)p(y\vert x)}{\sum q p}$（后验概率）
信息势能	$dQ = \sum_y p(y\vert x)\ln Q(x\vert y)$
给定 Q 求 q	$qQ \propto \exp{dQ}$
目标函数值	$f(q[Q], Q) = \ln\sum_x \exp{dQ}$
单调性	$f(q{k-1}) = f(q{k-1}, Q_k) \leq f(q_k, Q_k)$
收敛界	$\sum_{n=1}^{N}(f(q^)-f(q_n,Q_n)) \leq D_X(q^\vert q_0)$
停止准则	$\max_x(d[Q]-\ln q) - \sum_x q(d[Q]-\ln q) < \epsilon$
AWGN 矩阵更新	$M \leftarrow MS^{-1}M + M$，投影后 $M{ii} \leftarrow \min(M{ii}, 1)$
AWGN BC 矩阵更新	$K_U \leftarrow [(K_U S_1^{-1}K_U+K_U)^{-1} + \lambda(K_U+S_2)^{-1}]^{-1}$
SCIB α 梯度下降	$\alpha_{k+1} = \alpha_k - \tau \cdot \bar{\theta}(I(U;Z)-I(U;Y))$

10.3 BA 算法的核心思想速览

复习建议:

1. BA 算法的两步更新（§3-4）是核心——必须能默写 $Qq = q(x|y)$（后验）和 $qQ \propto \exp{dQ}$（Gibbs 分布）这两个闭式解，以及它们分别使条件 KL 散度为零和使 $d[Q]-\ln q$ 恒为常数的性质。
2. 交替最大化的正确性（§2, §5）——理解 $f(q) = f(q,Q) + D_{X|Y}(q|Q)$ 是保证 $f(q) \geq f(q,Q)$ 且等号可达的关键。
3. 收敛性证明（§5）——核心是用 $D_X(q^*|q_0)$ 控制所有迭代的遗憾之和，这表明 BA 算法在有限步内必然逼近最优值。
4. 连续信道的矩阵 BA（§9）——理解为什么高斯情形下的 $q[Q]$ 更新退化为一个矩阵二次型优化，以及矩阵迭代 $M \leftarrow MS^{-1}M+M$ 的推导。
5. BC 的 BA 算法（§7-8）——理解支撑超平面的思想（通过扫描 $\theta/\lambda$ 来描出容量区域边界），以及 max-min 交换（Terkelsen 定理）在 SCIB 中的应用。