通过猜测 Expansion 来改进 Expander Code

论文 Improved Decoding of Expander Codes. Xue Chen, Kuan Cheng, Xin Li, and Minghui Ouyang. 2023 阅读笔记。这篇文章通过猜测 Expansion 的 Idea 进一步改进了 Expander Code 线性解码算法的噪声容限。

记号规定

• 若无特殊说明，文中的 $G$ 都默认是 $D$ 左部正则的，左部点集大小为 $N$，右部点集大小为 $M\,(M<N)$ 的 $(\alpha N,(1-\epsilon)D)$-bipartite expander。且我们用 $D_R$ 表示右部点集的平均度数。
• 我们用 $1\{A\}$ 表示事件 $A$ 的示性变量。
• 用 $N(S)$ 表示 $S$ 的邻集，而用 $N^1(S)$ 表示 $S$ 的 unique neighbor 的集合，即 $N^1(S):=\{v\in V\mid e(v,S)=1\}$，而 $N^{\ge 2}(S):=N(S)\backslash N^1(S)$。

New Size-Expansion Tradeoff

Thm (New Size-Expansion Tradeoff)：设 $G$ 是一个 $(\alpha N,(1-\epsilon)D)$-bipartite expander。则对于任何的常数 $k>1$ 与左部点集一个大小为 $k\alpha N$ 的子集 $S$，我们有：

1. $|N(S)|\ge (1-k\epsilon)D\cdot k\alpha N-O(\epsilon D\cdot k^2)$；
2. $|N(S)|\ge \left(1-\dfrac{2k\epsilon-1}{3-2/k} \right)\dfrac k2\cdot D\alpha N-O(D_R D)$（当 $k>1/2\epsilon$ 时，第二条的效果比第一条的好。

第一条说的意思是：一个 $(\alpha N,(1-\epsilon)D)$-bipartite expander 大致上是一个 $(k\alpha N,(1-k\epsilon)D)$-bipartite expander $(k>1)$。这告诉我们可以通过损失一定的 expansion 来得到更大子集的扩展性参数。这一定理用处颇多，说是这篇文章的关键定理也不为过。

Proof：

① 先来证明第一条，我们使用概率方法来证明这一不等式：

设 $S$ 是左部点集一个大小为 $k\alpha N\,(k>1)$ 的子集。

考虑从 $S$ 中均匀随机取出一个大小为 $\alpha N$ 的子集 $T$，并考虑 $N(S)$ 中的一个点 $u$，其在 $S$ 中有超过一个邻居。设这些个邻居为 $v_1,\ldots,v_{d_S(u)}\,(d_S(u)>1)$，则用一下 Union Bound 就有：

$1\{u\in N(T)\}\le \sum_{i=1}^{d_S(u)}1\{v_i\in T\}-\sum_{i=2}^{d_S(u)}1\{v_1\in T\}1\{v_i\in T\}$

上式在随机变量 $T$ 上求个期望则有：

$\mathop{\mathbb E}\limits_T[1\{u\in N(T)\}]\le d_S(u)\cdot \dfrac{|T|}{|S|}-(d_S(u)-1)\cdot \dfrac{|T|(|T|-1)}{|S|(|S|-1)}$

又注意到：

$\sum_{u\in N(S)}d_S(u)=D|S|, \sum_{u\in N(S)}(d_S(u)-1)=D|S|-|N(S)|$

所以再对所有 $u\in N(S)$ 求个和既有：

$\mathop{\mathbb E}\limits_T [|N(T)|]\le D|T|-(D|S|-|N(S)|)\cdot \dfrac{|T|(|T|-1)}{|S|(|S|-1)}=D|T|\left(1-\left(1-\dfrac{|N(S)|}{D|S|} \right)\cdot \dfrac{|T|-1}{|S|-1} \right)$

再由 expander 的性质，有 $|N(T)|\ge (1-\epsilon)D|T|$，所以有：

$1-\epsilon\le 1-\left(1-\dfrac{|N(S)|}{D|S|}\right)\cdot \dfrac{|T|-1}{|S|-1}$

再整理一下就有：

$|N(S)|\ge (1-k\epsilon)D|S|-\dfrac{\epsilon(k-1)}{\alpha N-1}\cdot D|S|\ge (1-k\epsilon)D|S|-2\epsilon Dk^2$

得证。

② 再来证明第二条，我们使用另一种方法——线性规划的原始对偶方法——计算 $\mathop{\mathbb E}\limits_T [|N(T)|]$，依此来证明这一不等式：

设 $S$ 是一个大小为 $k\alpha N$ 的左部点集的子集。再设有 $\beta_j\cdot D\alpha N$ 个在 $N(S)$ 里的点，满足其恰有 $j$ 个邻居在 $S$ 里。则：

$|N(S)|=(\beta_1+\cdots+\beta_k)\cdot D\alpha N$

double counting $e(S,N(S))$ 可得：

$\beta_1+2\beta_2+\cdots+k\beta_k=k$

考虑 $\mathop{\mathbb E}\limits_T[|N(T)|]$ 的另一种计算方式：

$\mathop{\mathbb E}\limits_T[|N(T)|]=\sum_{i\in N(S)}\Pr\limits_{T\sim \binom{S}{\alpha N}}[T\cap N(i)\ne\varnothing]\ge (1-\epsilon)D\alpha N$

其中最有一个不等号是由 vertex expansion 的性质。

对于每个满足 $e(i,S)=j$ 的点 $i\in N(S)$，有：

$\Pr\limits_T[T\cap N(i)\ne\varnothing]=1-\Pr\limits_T[T\cap N(i)=\varnothing] \\ =1-\dfrac{(|S|-|T|)(|S|-|T|-1)\cdots(|S|-|T|-j+1)}{|S|(|S|-1)\cdots(|S|-j+1)} \\ =1-\left(1-\dfrac 1k\right)^j+O\left(\dfrac{D_R}{k\alpha N} \right)$

省略大 $O$ 那项，在把上式对所有的 $i\in N(S)$ 加起来，得到：

$\sum_{j=1}^k\left(1-\left(1-\dfrac 1k\right)^j \right)\cdot \beta_j\ge 1-\epsilon$

综合以上条件，我们把这些个条件与目标函数写成一个线性规划问题：

$\min\ \dfrac{|N(S)|}{k\alpha N}=\beta_1+\cdots+\beta_k \\ \text{s.t. }\beta_1+2\beta_2+\cdots+k\beta_k=k \\ \sum_{j=1}^k\left(1-\left(1-\dfrac 1k\right)^j \right)\cdot \beta_j\ge 1-\epsilon \\ \beta_j\ge 0,\, \forall j\in [k]$

设这一线性规划问题在 $\beta^*$ 处取到最优值。

注意到这一线性规划问题约束较少（只有两个），其对偶问题变量会比较少，方便分析：

$\max\ kx_1+(1-\epsilon)x_2 \\ \text{s.t. }jx_1+(1-(1-1/k)^j)x_2\le 1,\, \forall j\in [k] \\ x_2\ge 0$

我们有如下 Claim：$\beta^*$ 最多有两个下标是非 $0$ 的，且如果 $\beta^*$ 恰有两个下标非 $0$，则这两个下标必须是相邻的。

证明这一 Claim 的关键是注意到函数 $f(j)=1-(1-1/k)^j$ 是严格凹的。

如果有三处下标 $l_1<l_2<l_3$ 都是非 $0$ 的，则有线性规划的松弛互补，我么有：$jx_1+(1-(1-1/k)^j)x_2=1$ 对 $j=l_1,l_2,l_3$ 都成立。但是由 $j=l_1,l_3$ 时的等式成立再配合上 $f(j)$ 的凹性，可以推出：$l_2x_1+(1-(1-1/k)^{l_2})x_2>1$，矛盾了。如果有两个非零下标不相邻，证明是类似的。

那么我们假设 $j=2,3$ 处非零，则：

$2x_1+(2/k-1/k^2)x_2=1 \\ 3x_1+(3/k-3/k^2+1/k^3)x_2=1$

解得：

$x_1=\dfrac{2-1/k-k}{3-2/k},x_2=\dfrac{k^2}{3-2/k}$

可以验证这对 $(x_1,x_2)$ 是满足约束条件的。将其代入到目标函数可得对应值为 $\dfrac k2\left(1-\dfrac{2k\epsilon-1}{3-2/k} \right)$（省略了误差项 $k\cdot O\left(\dfrac{D_R}{k\alpha N}\right)$），由弱对偶原理可得：

$|N(S)|\ge \left(1-\dfrac{2k\epsilon-1}{3-2/k}\right)\dfrac k2\cdot D\alpha N-O(D_RD)$

故得证。$\Box$

一个有趣的事实是：实际上第一条的下界是在 $j=1,2$ 处非零时取到的。

Expander Code 距离的改进

利用 New Size-Expansion Tradeoff，我们可得对 Expander Code 距离的估计进行一些个改进。在 SS96 中，M. Sipser 和 D. A. Spielman 证明 expander code 的距离至少为 $\alpha N$。在 Vid13a 中，Michael Viderman 证明这一下界可以被改进为 $\dfrac{2(1-3\epsilon)}{1-2\epsilon}\alpha$。在这篇文章中，这一下界被改进到 $\dfrac1{2\epsilon}\alpha N$。具体来说：

Thm (Distance of Expander Code)：设 $G$ 是一个 $(\alpha N,(1-\epsilon)D)$-bipartite expander，且 $\epsilon<1/2$。则由 $G$ 定义的 expander code $\mathcal C$ 的距离 $d$ 至少为 $\dfrac 1{2\epsilon}\alpha N-O(1/\epsilon)$。

我们先证明如下引理：

Lemma：设 $G$ 是一个 $(\alpha N,(1-\epsilon)D)$-bipartite expander，且左部 $d$ 正则，右部平均度数为 $D_R$，则：

1. $\epsilon>1/D$；
2. $\dfrac{\alpha}{4\epsilon}\le 1/D_R+O\left(\dfrac1{D\alpha}\cdot M/N^2 \right)$。

Proof： $\Box$

接下来我们可以来证明上面的 Thm 了。

Proof of Thm：是用反证法，假设有一个 codeword $z$，其与 $0$ 的汉明距离为 $\dfrac1{2\epsilon}\alpha N-C/\epsilon$，其中 $C$ 是一个充分大的数。注意由 Lemma 的第二条，有 $\alpha/2\epsilon\le 2/D_R<1$，所以 $\dfrac1{2\epsilon}\alpha N$ 可能取到。

设 $S$ 为 $z$ 中为 $1$ 的比特位的下标集合。由 New Size-Expansion Tradeoff 中的第一条，我们有：

$|N(S)|\ge \left(1-\dfrac{|S|}{\alpha N}\right)D|S|-O\left(\epsilon D\cdot\left(\dfrac{|S|}{\alpha N}\right) \right)$

对于充分大的 $C$，不等式右边至少为：

$\left(\dfrac 12+\dfrac{C}{\alpha N}\right)D|S|-O\left(\epsilon D\cdot\left(\dfrac{|S|}{\alpha N}\right) \right)>\dfrac 12 D|S|$

则由抽屉原理，上式表明 $|N^1(S)|>0$。那么 $z$ 不是一个合法的 codeword（$z$ 不满足在 $N^1(S)$ 中的 parity check），故矛盾。$\Box$