Improved Decoding of Expander Codes 学习笔记

原论文：

Xue Chen, Kuan Cheng, Xin Li, and Minghui Ouyang. 2023. Improved Decoding of Expander Codes. IEEE Trans. Inf. Theor. 69, 6 (June 2023), 3574–3589. https://doi.org/10.1109/TIT.2023.3239163

The size-expansion tradeoff

Thm. Any $(\alpha N,(1-\varepsilon) D)$ expander is also roughly a $(k \alpha N,(1-k \varepsilon )D)$ expander.

Note:

只要一个点集的 expansion rate $> \frac{1}{2}$ 就说明依然存在 unique neighbors

通过这里的 tradeoff 可以把多余的 $\varepsilon$ 转化较大的 $|S|$

取 $k=\frac{1}{2 \varepsilon}$ 依然可以满足要求，从而证明本文的主要结果：expander code dis $\ge \frac{\alpha D}{2\varepsilon}$ 何时 tight？存在一个子图，左侧 $\frac{\alpha}{2 \varepsilon } N$ 个点，右侧 $\frac{\alpha}{2 \varepsilon } N \frac{D}{2}$ 个点都与左侧两个点相连。

Proof Sketch.

$T\subset L$ , $N(T)$ 很小 $\rightarrow$ $S\sim {T\choose \alpha N}$ , $E[N(S)]$ 也很小

通过两种不同的放缩，得到：

$|N(T)|\ge (1-k \varepsilon )D\times k \alpha N-O(\varepsilon D\times k^2)$
$|N(T)|\ge (1-\frac{2k \varepsilon-1}{3-\frac{2}{k}} )D\times k \alpha N-O(\cdots)$

第二个 bound 对 $k>\frac{1}{2\varepsilon}$ 时候更紧。

第二个界的证明想法及其完整结果

假设右侧有 $\beta_i \cdot \alpha N$ 个点与 $S$ 中恰好 i 个点相连，则有约束（约束的答案是 expansion 的下界）：

\begin{aligned} \min& \sum \beta_i\cr \text{s.t.}& \sum i\cdot \beta_i=k\cr &\sum (1-(1-\frac{1}{k})^j)\cdot \beta _j\ge 1-\varepsilon \cr &\beta _j\ge 0. \end{aligned}

其中第二条来自于 $N(T)$ 中每个点与 $S$ 相连的概率，（实际上这里的概率是 $\frac{(|S|-|T|)!/(|S|-|T|-j)!}{|S|!/(|S|-j)!}=1-\left( \frac{|S|-|T|}{|S|} \right)^j+O(\frac{j}{S})$ ）

（对这个 O 里面的东西我不太确定，试着放缩了几次没有得到一样的结果，但是 k 大一点的时候应该不会很大）

写出这个 LP(1) 的对偶形式 LP(2)：

\begin{aligned} \max\ &x_{1}\cdot k+(1-\varepsilon )\cdot x_{2}\cr \text{s.t. }&j\cdot x_{1}+(1-(1-\frac{1}{k})^j)\cdot x_{2}\le 1\cr &x_{1},x_{2}\ge 0. \end{aligned}

Lem LP(1) 的最优解中，仅仅有两个相邻的 $\beta _i,\beta _{i+1}$ 非零.

Proof Sketch. 若 $\beta _j\neq 0$ ，根据线性规划的相关定理，一定有对偶形式中的对应约束取等，即： $j\cdot x_{1}+(1-(1-\frac{1}{k})^j)\cdot x_{2}= 1$ . 然而因为 $(1-(1-\frac{1}{k})^j)$ 严格上凸，所以如果存在两个非相邻的 $\beta_l,\beta _r$ 都大于零，则可以推断在他们之间的 $\forall j\in [l,r],j\cdot x_{1}+(1-(1-\frac{1}{k})^j)>1$ ，都无法满足 LP(2) 中的限制。

直观上讲，右边的点与左边 $S$ 相连的边数越平均，越接近这个bound。

接下来，我们考虑最优解中哪两个 $\beta_i,\beta _{i+1}$ 非零，就可以解出相应的 $x_{1},x_{2}$ ，使得对应约束等号取等。然后就可以得到对偶形式答案的一个下界。

假如取 $i=2$ ，可以得到 $x_{1}=\frac{2-\frac{1}{k}-k}{3-\frac{2}{k}},x_{2}=\frac{k^2}{3-\frac{2}{k}}$ , 带入 $x_{1}\cdot k+(1-\varepsilon )\cdot x_{2}$ 就得到第二个 bound
假如取 $i=1$ 就可以得到上一个结果。

文章里还提到，当 $1-\varepsilon \in [\frac{k}{j+1}(1-(1-\frac{1}{k})^{j+1}),\frac{k}{j}(1-(1-\frac{1}{k})^j)]$ 的时候，LP(2) 会在 $\beta_j,\beta _{j+1}\neq 0$ 处极值，也即： $k\le \frac{1}{2\varepsilon}$ 时， $j=1$ 最优。

对于一般的 $j$ :

\begin{aligned} x_{2}&=\frac{1}{1-(1+\frac{j}{k})(1-\frac{1}{k})^j},\cr x_{1}&=-x_{2}\cdot \frac{(1-\frac{1}{k})^j}{k}=\frac{-\frac{1}{k}\cdot (1-\frac{1}{k})^j}{1-(1+\frac{j}{k})(1-\frac{1}{k})^j}. \end{aligned}

对应 expansion 下界：

\begin{aligned} |N(T)|&\ge \alpha ND\cdot (x_{1}\cdot k+(1-\varepsilon )\cdot x_{2})\cr &\ge \alpha ND\cdot (1-\varepsilon -(1-\frac{1}{k})^j)x_{2}\cr &\ge \alpha ND\cdot \frac{1-\varepsilon -(1-\frac{1}{k})^j}{1-(1+\frac{j}{k})(1-\frac{1}{k})^j}. \end{aligned}

如果我认为 $j$ 是连续的，那么 j 的最优取值应该满足 $1-\varepsilon \approx \frac{k}{j}(1-(1-\frac{1}{k})^j)$ ，带入上式，也许能对于较大的 k 得到一般的结果？但是因为 $k=\frac{1}{2 \varepsilon}$ 时已经 tight,无法改进 dis. $|N(T)|\ge \alpha ND \frac{k}{2 \varepsilon k+1}$ (展开了 $(1-\frac{1}{k})^j$ 前两项)

Expander Code Dis Upperbound

Thm. 对于任何一个 $\varepsilon,\eta$ 都能找到一个 $\alpha,D$ ( $\alpha$ 可能比较小， $D$ 可能要比较大)，使得一个 $(\alpha N,(1-\varepsilon -\eta ))$ expander code dis $\le \frac{\alpha N}{2 \varepsilon}$

Idea: 通过 Ramanujan Graph 的 vertex-edge graph 构造出来一个左侧 D,右侧 2 regular 的二分图，其中左侧 $\frac{\alpha }{2\varepsilon }N$ 个点。其余的点数用随机二分图补齐。

因为 expander mixing lemma 可以得到原图 edge expansion 的下界，对应到这个图上就是 vertex expansion.

这样，这个子图中的 bits 全取 1 就构成一个 codeword，这样的图在右侧不是 regular 的，后面提到一个 open question 是能不能构造一个左右都 regular 的图。

Note: 为什么 Ram-Graph 的点数不能更小一点？

expander mixing lemma: $E(S,S)\approx \frac{D}{2|V(H)|}\cdot |S|^2\le \varepsilon |S|D$ ，其中 $S$ 是 $\alpha N$ ，从而 $V(H)$ 必须大于 $\frac{\alpha}{2\varepsilon}N$ 。

Question:

这里一定要用 ram-graph 对应的二分图吗？用随机的正则二分图会有什么问题？

根据后面的定理，随机的 $(D,D_R)$ regular graph 高概率是 $(\alpha N,\frac{1}{\alpha }(\frac{D}{D_R}(1-(1-\alpha)^{D_R})-2 \alpha \sqrt{D \log e/\alpha})$ expander. （大约就是邻居数量的期望减去一个小量）

假如希望类似上面构造一个小 expander graph,使得左边点数小于 $\frac{\alpha N}{2 \varepsilon }$ 。则对于这个小图来说 $\alpha'\ge 2 \varepsilon$ ，带入上式，需要 $D_R$ 很小（常数级别）。

Q: 假如 $D,D_R$ 固定，可以能得到多小的上界？ $\alpha' \le \frac{2\varepsilon}{D_r-1}$ ，则 $N'\ge \alpha \frac{N}{\alpha '} =\frac{\alpha N (D_R-1)}{2 \varepsilon}$ （展开前两项）

Finding a superset of flipped bits

Lem. 若对 $F$ (被翻转的 bits) 的任意子集 $S$ ，都有 $U(S)\ge (1-2\Delta)D|S|$ ，则上述算法找到的 $L\supseteq F$ 。

Proof Sketch. 若否，在 $F-L$ 中可以找到一个贡献超过 $(1-2 \Delta)D$ 个 unique neighbors 的点 $v$ ，其贡献的 UN 中至少有一个点没有被加入 $R$ 中，从而该点与 $L$ 也不相连，也是 $F$ 的 UN，因此这个 parity check 一定不满足，与其不在 $R$ 中矛盾。

性质:

上述过程按照任意顺序加点得到的 $L$ 总是一致的
若满足上面引理的条件，则总存在一种加点顺序，把 $F$ 中的点恰好全加到 $L$ 。

有时候，还可以通过某些条件证明最终 $|L|\le k \alpha N$ ，后面很多地方用到了类似的 argument：

Proof Sketch. 假设已知 $F$ 的 expansion 为 $(1-\gamma )D$

若否，我们考虑算法过程进行到一半，已经加入 $k \alpha N$ 的情形。我们总能假定先加入了所有 $F$ 中的点，从而有：

(1-k \varepsilon ) k D \alpha N-O(\ldots ) \le |N(L)| \le (1-\gamma )D|F|+2 \Delta D (k \alpha N -|F|) .

其中不等式第一部分来自 size-expansion tradeoff, 第二部分来自将 $F$ 加入 $L$ 后，每个新加的节点最多贡献 $2\Delta D$ 个新点到 $R$ 中。

化简得到：

|F|\ge k \alpha N \frac{1-k \varepsilon -2 \Delta }{1-\gamma -2 \Delta} +O(\ldots ) .

如果此时通过某些条件可以得到 $F$ 的实际大小比这小，则可以推出矛盾。

换用 Flip 算法的直觉是：使用更小的阈值，从而允许更大的 $|F|$ （上式）

Analysis of `Flip` Algorithm

假设阈值为： $1-t$ 。

在 $|F\cup L|\le k\alpha N$ 的前提下，文中 $k=1$ （ $|F|\le k\alpha N\frac{1-k\varepsilon -t}{1-\gamma -t}$ 即可满足）：

|F - L|\le \frac{2 \gamma}{t} |F|, |L-F|\le \frac{k \varepsilon - \gamma }{1-k \varepsilon - t} |F|

前者通过对 $N^1(F)$ 用类似 Markov Bound 的方式估计，后者对 $|F\cup L|$ 用前文类似的 Argument 估计。

我们希望 $|F-L|+|L-F|\le |F|\cdot (1-\Omega(1))$ ，计算可得，当 $\varepsilon < \frac{1}{4}, t =3 \gamma$ 的时候，刚好达到。

Guessing expansion

这一算法对于 $\forall \varepsilon = \frac{1}{4}-\beta$ 的 expansion,都可以纠正 $(1-\varepsilon)\alpha N$ 个错。假定我们知道 $F$ 的 expansion $(1-\gamma )D|F|$ ，我们会有如下高效的做法：

若 $\gamma > \frac{2}{3}\varepsilon$ 则直接用上一个 section 算法找出 $F$ 的超集，并且这一集合大小小于 $\alpha n$ (用之前提到的 argument)，直接用 Viderman 的 erasure 的算法可以求解。
若 $\gamma \le \frac{2}{3}\varepsilon$ 则找到 $S=\{v\mid v\in L, |N(V)\cap C|\ge (1-3 \gamma)\}$ ，可以证明翻转 $S$ 中 bits 时， $F$ 会减小 $\beta$ 的比例。

Proof Sketch. 先用类似之前的 argument 说明 $|F_i\cup L_{0}|\le \frac{(1+3 \eta )|F_i|}{(1-\varepsilon )}$ 。随后可以求出 $|F_i|$ 和 $|L_{0}-F_i|$ 之间的比例，再根据 $F_i$ 的 UN 数给出 $|F_i-L_{0}|$ 的一个上界。

然而我们不知道，所以只能每次猜测一个 $\gamma$ ，把 $(0,1)$ 分为 $1/\eta=(100/\beta)$ 段 (而非是 $n\times m$ 个分数)，然后要猜对 $l=\log_{1-\beta}1/3$ 次，所以额外复杂度 $\eta^{-l}$ ，对 $\beta$ 是指数级的，只是这里当作 $\beta$ 是常数，所以算是 $O(1)$ 。

为什么 $\gamma >\frac{2}{3}\varepsilon$ 的时候不可以用FLIP？

Improved decoding for $\varepsilon \le \frac{1}{8}$

这部分对于较小的 $\varepsilon$ 给出了解码半径 $\frac{\sqrt{2}-1 }{2\varepsilon}\alpha N>\frac{3}{16}\alpha N$ 的算法。

下面是这部分一个比较有意思的结论。

Clm. 假设已知 $|F|=x \alpha N, |N(F)|= |F|(1-\gamma)D$ ，则 $\forall F'\subset F,|F'|\ge \alpha N$ 都有 $|N(F')|\ge |F'|D(1-\sqrt{\varepsilon \gamma x})$

Proof Sketch. 假设 $|N(F')|\ge |F'|D(1-\beta )$ ，则根据 tradeoff 可以得到 $|F'|$ 大小的下界，随后再因为 $F'$ 中的 collision 比 $F$ 中的总数要少，可以得到 $\beta$ 的上界。

根据前面 Find 的性质，这一 $\Delta$ 的选取意味着 Find 总能包含所有出错的bits.

后面就是又用相似的 argument 证明了 Find 找到的集合大小一定小于 $\frac{1-2 \varepsilon }{2\varepsilon}\alpha N$ 。

另一个理解：

当阈值取 $t$ 时，我知道第一轮过后就有 $|F-L|\le |F| \frac{2 \gamma }{t}$ 对于这么大的集合，由于 trade-off，容易说明其中至少有 $(1- x\frac{2 \gamma }{t})$ 比例的边，连到了第一轮之后的 $U'\coloneqq U\cup N(L)$ 中。从而通过平衡 $t$ 的大小，可以说明当 $t\coloneqq O(\sqrt{x \varepsilon \gamma } )$ 的时候找到的 erasure 依然可以包含整个 $F$ 。