西电 - 网络信息论 第七章：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）的矩阵迭代版本。
免责声明：内容来源于课程讲义和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(n)$ 由归一化约束 $q(n) = 1 - q(1) - \cdots - q(n-1)$ 确定，求导时需计入 $q(n)$ 随 $q(x)$ 的变化（式中 $p(y|n)$ 与 $H(Y|X=n)$ 两项即来源于此）。

更新规则: $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$ 是 $Q[q] (x|y) = 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)}$$

$d[Q](x)$ 可理解为在给定 $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}$$

其中 $S_d = \sum_{x'} \exp\{d[Q](x')\}$ 是归一化常数。

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(q_k) \geq f(q_{k-1})$。序列 $\{f(q_k)\}$ 单调不减且有上界（最大互信息 $C$ ），因此收敛。

📌 对一般问题的意义: 点对点情形下 $f(q) = I(X;Y)$ 对 $q$ 是凹的，但一般问题（如 §7、§8 的 BC 目标函数 $F(q(u,x))$）并不凹。BA 框架的威力在于：即使原目标非凹，只要扩展目标 $f(q, Q)$ 在分别固定 $q$、$Q$ 时是凹的，交替最大化就仍然适用，且每一步都保证 $f$ 不降。

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$。

详细推导:

第一步（讲义 p.12）：由 (3) 知 $d [Q_n] (x) - \ln q_n(x) \equiv \ln S_d^{(n)} = f(q_n, Q_n)$ 对每个 $x$ 恒成立（因 $q_n = q[Q_n]$），故

$$\begin{aligned} 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{p(y|x)}{q_{n-1}(y)} \quad (\text{代入 } Q_n = q_{n-1}(x|y) \text{ 与 } d[Q] \text{ 的定义}) \end{aligned}$$

第二步（讲义 p.13）：两边与 $f(q^*) = \sum_{x,y} q^*(x)p(y|x)\ln\frac{p(y|x)}{q^*(y)}$ 相减，

$$\begin{aligned} f(q^*) - f(q_n, Q_n) - \sum_x q^*(x)\ln\frac{q_n(x)}{q_{n-1}(x)} &= \sum_{x,y} q^*(x)p(y|x) \ln\frac{q_{n-1}(y)}{q^*(y)} \\\\ &= \sum_y q^*(y) \ln\frac{q_{n-1}(y)}{q^*(y)} = -D_Y(q^* \| q_{n-1}) \leq 0 \end{aligned}$$

因此 $f(q^*) - f(q_n, Q_n) \leq \sum_x q^*(x)\ln\frac{q_n(x)}{q_{n-1}(x)}$。对 $n$ 求和（逐项对消、望远镜求和）：

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

各项 $f(q^*) - f(q_n, Q_n) \geq 0$ 且部分和有界，故 $f(q^*) - f(q_n, Q_n) \to 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$。

证明（扰动法，讲义 p.11）: 将最优分布 $q$ 沿方向 $\lambda$ 扰动为 $r_x = q_x + \epsilon\lambda_x$，其中 $\epsilon \geq 0$、$\sum_x \lambda_x = 0$，且 $q_x = 0$ 时要求 $\lambda_x \geq 0$（保证 $r$ 仍是概率分布）。由最优性 $f(q) \geq f(r)$，在 $\epsilon = 0$ 处的方向导数非正：

$$\frac{df(r)}{d\epsilon}\Big|_{\epsilon=0} = \sum_x \lambda_x \cdot \underbrace{\sum_y p(y|x)\ln\frac{p(y|x)}{q(y)}}_{=:\, D_x} \leq 0$$

（交叉项 $\sum_y \frac{d r_y}{d\epsilon} = 0$ 自动消去。）对任意合法扰动均成立，特别地：

• 若 $q_x > 0$ 且 $q_{x'} > 0$：取 $\lambda_x = 1$、$\lambda_{x'} = -1$，正反两个方向都必须 $\leq 0$，故 $D_x = D_{x'}$
• 若 $q_x = 0$ 且 $q_{x'} > 0$：只能取 $\lambda_x = 1$、$\lambda_{x'} = -1$，得 $D_x \leq D_{x'}$

即正概率输入的信息势能彼此相等、零概率输入的势能不更大——(5) 得证。

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) 知 $d[Q[q]](x) - \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$ 的容量区域（$R_2 \leq I(U;Z)$，$R_1 \leq I(X;Y|U)$，对某个 $p(u,x)$ 取并）的边界可由支撑超平面刻画：

$$\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)$。

💡 两种情形: $\theta \geq 1/2$ 时权重偏向强用户 $Y$，支撑点退化为单用户角点（$R_2 = 0$，速率全部分配给 $Y$ 用户，由 $\max_{q(x)} I(X;Y)$ 决定）；$\theta < 1/2$ 时支撑点在叠加编码区域的弯曲边界上，需要优化 $(U, X)$ 的联合分布——这正是 BA 算法（对”超符号” $(u,x)$）发挥作用的地方。该结果来自 Yasui-Matsushima（ISIT 2010）。

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 的 $d[Q](x) = \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（等价刻画 $R_2 \leq \min{I(U;Y), I(U;Z)}$，$R_1 \leq I(X;Y|U)$）的支撑超平面（对非平凡的 $\theta \in [0, 1/2)$）形如：

$$\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)$，且利用了 $\min{I(U;Y), I(U;Z)} = \min_{\alpha \in [0,1]} \big[\bar{\alpha}I(U;Y) + \alpha I(U;Z)\big]$。

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

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

扩展目标函数（对固定的 $\alpha$ 套用 BA，讲义 p.19）:

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

迭代算法: 在 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 内界（带公共消息 $W$）:

$$R_1 \leq I(U, W; Y), \qquad R_2 \leq I(V, W; Z)$$ $$R_1 + R_2 \leq \min\{I(W; Y), I(W; Z)\} + I(U; Y|W) + I(V; Z|W) - I(U; V|W)$$

目标函数结构类似，但辅助变量扩展到 $(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)$$

其中（讲义 p.21）:

$$\begin{aligned} d[Q](u,v,w,x) = \sum_{y,z} p(y,z|x)\bigg[&\frac{\bar{\theta}-\alpha\theta}{\bar{\theta}}\ln Q(w|z) + \frac{\alpha\theta}{\bar{\theta}}\ln Q(w|y) + \ln Q(v|w,z) \\\\ &+ \frac{\theta}{\bar{\theta}}\ln Q(u|w,y) + \frac{\bar{\theta}-\theta}{\bar{\theta}}\ln Q(u|v,w) + \ln Q(x|u,v,w)\bigg] \end{aligned}$$

各分量对应 Marton 编码中的条件结构：公共消息 $W$（在两个接收端之间由 $\alpha$ 折中）、$V$ 以 $W$ 为条件、$U$ 以 $(V,W)$ 为条件等。

8.4 UVOB 的 BA 算法

UV 外界（Nair-El Gamal）:

$$R_1 \leq I(U; Y), \qquad R_2 \leq I(V; Z)$$ $$R_1 + R_2 \leq \min\big\{I(U; Y) + I(X; Z|U),\; I(V; Z) + I(X; Y|V)\big\}$$

目标函数（$\alpha, \beta \in [0,1]$ 满足 $\bar{\theta}\alpha + \theta\beta \geq \max{\theta, \bar{\theta}}$，讲义 p.22）:

$$\begin{aligned} G(\alpha, \beta, q, Q) = &-(\bar{\theta}\alpha + \theta\beta) \sum_x q(x)\ln q(x) \\\\ &+ \bar{\theta}\alpha \sum_{x,v} q(x)q(v|x)\big(d_1[Q](v,x) - \ln q(v|x)\big) \\\\ &+ \theta\beta \sum_{x,u} q(x)q(u|x)\big(d_2[Q](u,x) - \ln q(u|x)\big) \end{aligned}$$

两个辅助函数分别对应两个速率约束（讲义 p.23）:

$$d_1[Q](v,x) = \sum_{y,z} p(y,z|x)\left[\ln Q(x|y,v)Q(v|z) + \frac{\bar{\theta}\alpha - \theta\bar{\beta}}{\bar{\theta}\alpha}\ln\frac{Q(y|v)}{p(y|x)}\right]$$ $$d_2[Q](u,x) = \sum_{y,z} p(y,z|x)\left[\ln Q(x|z,u)Q(u|y) + \frac{\theta\beta - \bar{\theta}\bar{\alpha}}{\theta\beta}\ln\frac{Q(z|u)}{p(z|x)}\right]$$

注意 UVOB 的优化变量除 $q$ 外还有 $(\alpha, \beta)$ 两个参数（对应 min-max 结构），迭代中与 §8.2 类似地交替进行 BA 与梯度下降。

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$ 时的支撑超平面值（对数取自然底 e）

实验设置与结果（讲义 pp.25-26）: 固定 $\alpha_0 = \beta_0 = 0.7$ 时的最大化部分中，UVOB / MIB / SCIB 的目标函数值在约 200 次迭代内收敛，$P(X=0)$ 收敛到约 0.5；最小化部分中 $(\alpha_k, \beta_k)$ 在梯度下降下收敛到区间内的稳定值。三类界的目标函数值互有高低——SCIB ⊆ MIB ⊆ UVOB 的包含关系在数值上得到验证。

9. 连续信道的 BA 算法

9.1 连续信道的挑战

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

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

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

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

标准化（whitening）: 一般 AWGN 信道 $\tilde{Y} = \tilde{X} + \tilde{Z}$（$\tilde{Z} \sim \mathcal{N}(0, \tilde{S})$）在约束 $E[\tilde{X}\tilde{X}^T] \preceq K$（$K \succ 0$）下，令 $Y = K^{-1/2}\tilde{Y}$、$X = K^{-1/2}\tilde{X}$、$Z = K^{-1/2}\tilde{Z}$，即化为标准形式

$$Y = X + Z, \qquad Z \sim \mathcal{N}(0, S), \qquad E[XX^T] \preceq I$$

已知结果：容量由高斯输入 $X \sim \mathcal{N}(0, I)$ 达到。以下用 BA 算法验证这一结果。

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

所需性质（高斯条件分布）: 若 $(X, Y)$ 联合高斯，均值为零，协方差矩阵为

$$\begin{pmatrix} A & B \\ C & D \end{pmatrix}$$

则 $p_{X|Y=y}$ 仍是高斯分布，均值为 $BD^{-1}y$，协方差为 $A - BD^{-1}C$（Schur 补）。

BA 算法的矩阵推广:

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

$(X, Y)$ 联合高斯

$$\mathcal{N}\!\left(\begin{pmatrix} 0 \\ 0 \end{pmatrix}, \begin{pmatrix} M & M \\ M & M+S \end{pmatrix}\right)$$

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

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

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

给定 $Q$ 求 $q$

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

计算 $d[Q](x) = 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} + \text{tr}\Big((AS)^{-1} \cdot E_{Y|x}\big[(x-AY)(x-AY)^T\big]\Big) \quad (\text{标量取迹}) \\\\ &= \text{const} + \text{tr}\Big((AS)^{-1} \cdot (x-Ax)(x-Ax)^T\Big) \quad (Y|x \sim \mathcal{N}(x, S)) \\\\ &= \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)$），约束 $E[XX^T] \preceq I$。

叠加编码：$X = U + V$，$U \sim \mathcal{N}(0, K_U)$，$V \sim \mathcal{N}(0, K_V)$，$U \perp V$。支撑超平面（$\lambda \geq 1$）由

$$\max_{q(v,x)} I(X; Y_1|V) + \lambda I(V; Y_2)$$

给出，代入高斯分布后化为（在常数意义下，const 项来自噪声熵，讲义 p.36）:

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

该最大化问题有唯一极大点（Lau-Nair-Yao，ISIT 2022）。

KKT 方程与矩阵更新规则（Jiao-Geng-Yang，ISIT 2024；讲义 p.37）: 由最优性条件

$$K_U^{-1} = (K_U S_1^{-1} K_U + K_U)^{-1} + \Gamma, \qquad K_V^{-1} \leftarrow K_V^{-1} - (K_U + S_2)^{-1} + \Gamma/\lambda$$

其中 $\Gamma$ 是约束 $K_U + K_V = I$ 对应的拉格朗日乘子矩阵（讲义中第二式以迭代更新形式给出）。消去 $\Gamma$ 得更新规则（迭代后投影）：

$$\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$（卫星/云协方差）与 $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	$Q[q] (x\vert y) = q(x\vert y) = \frac{q(x)p(y\vert x)}{\sum q p}$（后验概率）
信息势能	$d[Q] (x) = \sum_y p(y\vert x)\ln Q(x\vert y)$
给定 Q 求 q	$q[Q] (x) \propto \exp\{d[Q](x)\}$
目标函数值	$f(q[Q], Q) = \ln\sum_x \exp\{d[Q](x)\}$
单调性	$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 = VDV^T$ 后 $D_{ii} \leftarrow \min(D_{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 算法的核心思想

10.4 本章参考文献（讲义 p.40）

编号	文献	对应内容
[1]	R. Blahut, Computation of channel capacity and rate distortion functions, IEEE Trans. Inf. Theory, 1972, 18: 460–473	经典 BA 算法
[2]	S. Arimoto, An algorithm for computing the capacity of arbitrary discrete memoryless channels, IEEE Trans. Inf. Theory, 1972, 18: 14–20	经典 BA 算法
[3]	K. Yasui, T. Matsushima, Toward computing the capacity region of degraded broadcast channel, ISIT 2010: 570–574	§7 退化 BC 的 BA
[4]	Y. Dou, Y. Liu, X. Niu, B. Bai, W. Han, Y. Geng, Blahut–Arimoto algorithms for inner and outer bounds on capacity regions of broadcast channels, Entropy, 2024, 26: 178	§8 SCIB/MIB/UVOB
[5]	C. W. K. Lau, C. Nair, C. Yao, Uniqueness of local maximizers for some non-convex log-determinant optimization problems using information theory, ISIT 2022: 432–437	§9.3 极大点唯一性
[6]	T. Jiao, Y. Geng, Z. Yang, Blahut-Arimoto algorithm for computing capacity region of Gaussian vector broadcast channels, ISIT 2024	§9.3 AWGN BC 矩阵迭代