附录：从插入阶段的二进分块到任意空间深度的压缩

本附录完整重建 H 第 7–13 页中基本目录构造要用的部分。第九章只用到插入阶段的行估计；这里还必须处理各行处在不同空间深度的情况。两件事不能互相替代。下述证明固定全部列、出生格和继承掩膜以后进行，不对自适应选择本身取上确界。

1. 列的条件数与积分核

假定每条路径至多有 $D\ge2$ 个支持出生标签，列满足

\|\Phi_v\|_{L^\infty(J_v;\mathcal H)}\le D, \quad \sqrt{\epsilon_v}\ge D^{-1}.

在一格 $I$ 上，令 $E_yc=\sum_vc_v\Phi_v(y)$ 。私有坐标和 Cauchy–Schwarz 给出

D^{-1}\|c\|_2\le\|E_yc\|_{\mathcal H}\le D^{3/2}\|c\|_2.

归一化 Gram 矩阵

G_I=\frac1{|I|}\int_I E_y^*E_y\,\mathrm dy

满足 $G_I\ge D^{-2}\mathrm{Id}$ 。投影因而有表达式

P_Iz(y)=\frac1{|I|}\int_I E_yG_I^{-1}E_t^*z(t)\,\mathrm dt, \quad \|E_yG_I^{-1}E_t^*\|\le D^5. \tag{A1}

这说明

\|P_Iz\|_\infty\le D^5\frac1{|I|}\int_I\|z\|.

无私有条件数下界时，后面的系数停止不能按当前预算工作。

2. 同一个有限阶段序列的行估计

H 原稿第 8 页 · H 原稿第 9 页

设 $P_n^i$ ， $0\le n\le T$ 、 $1\le i\le m$ ，各自是递增正交投影。令

Z_n=P_n^m\cdots P_n^1, \quad L_T=1+\lceil\log_2(T+1)\rceil.

若行 $B_\nu$ 满足 $\sum_\nu\|B_\nu h\|^2\le\|h\|^2$ ，则任意选择阶段 $n(\nu)$ 都有

\left(\sum_\nu\|B_\nu Z_{n(\nu)}g\|^2\right)^{1/2} \le L_T^m\|g\|. \tag{A2}

证明如下。令 $\Delta_0^i=P_0^i$ 、 $\Delta_n^i=P_n^i-P_{n-1}^i$ 。前缀 $\{0,\ldots,n\}$ 可分为每种长度至多一个的 dyadic 指标块。固定各因子块长度后，把使用同一块组合的行合并。行收缩将其平方和控制为

\|\Delta_{A_m}^m\cdots\Delta_{A_1}^1g\|^2.

依次对 $A_m,\ldots,A_1$ 用每层内部的正交性，总和至多 $\|g\|^2$ 。长度组合至多 $L_T^m$ 个，再在行空间用三角不等式便得式 $(\mathrm{A2})$ 。不同层之间不需要交换。

逐因子作望远镜展开，

Z_n-Z_{n-1} =\sum_{i=1}^mP_n^m\cdots P_n^{i+1} \Delta_n^iP_{n-1}^{i-1}\cdots P_{n-1}^1.

丢掉左侧收缩，先对 $i$ 用 Cauchy–Schwarz，再以 $B_n=\Delta_n^i$ 使用式 $(\mathrm{A2})$ ，得到

\sum_{n=1}^T\|(Z_n-Z_{n-1})g\|^2 \le m^2L_T^{2m}\|g\|^2. \tag{A3}

这里采用略弱的指数以简化记号。

3. 用相同矩的有界函数替换原输入

H 原稿第 10 页 · H 原稿第 11 页

现在各行局部于任意格 $u(\nu)$ ，满足 $B_\nu=B_\nu1_{u(\nu)}$ 。空间深度可以任意多。树末端再补一层，不改任何原行。

令 $a_K=|K|^{-1}\int_K\|z\|$ 。从根开始，在平均值第一次超过当前根平均值两倍的后代格停止，迭代得到根族 $\mathcal S$ 。零平均根无贡献。对一个 $K\in\mathcal S$ ，将下一批停止根和其余末端叶组成分割 $\pi_K$ 。其每个格 $Q$ 都有 $a_Q\le4a_K$ 。这里的大小片段由 $K$ 内不包含于任何真停止子根的格组成；每个行格分给包含它的最深大小停止根，停止子根上的行归入新的片段。下面的系数停止在该片段内进行，片段边界用终止格补齐。

在 $Q$ 上，取所有本片段中含 $Q$ 的祖先格曾用过的第一层标签，将 $z|_Q$ 投影到这些列上。把各个结果作直和，得到 $g_K$ ，在 $K$ 外补零。每条路径最多 $D$ 个标签，由式 $(\mathrm{A1})$ ，

\|g_K\|_\infty\le G a_K,\quad G=4D^5, \quad \|g_K\|_2^2=\langle z,g_K\rangle. \tag{A4}

最后的内积为实数。对片段中的任一格 $u$ ，每个第一层列的矩在其全部分割子格上都保留，因此

P_u^1g_K=P_u^1z, \quad P_u^m\cdots P_u^1g_K=P_u^m\cdots P_u^1z. \tag{A5}

这不是逐点截断；普通截断未必保留第一层矩。

平均值沿停止根至少翻倍。若 $M_d\|z\|$ 是根内 dyadic 极大函数，则逐点几何级数和及 $L^2$ 极大不等式给出

\sum_{K\in\mathcal S}a_K^2|K| \le\frac43\|M_d\|z\|\|_2^2 \le\frac{16}3\|z\|_2^2. \tag{A6}

下面还需要比 $\|g_K\|_\infty\le Ga_K$ 更强的累计能量界。

记 $S=\sum_K\|g_K\|_2^2$ 。固定 $y$ ，把含它的根分为

a_K<\frac{M_d\|z\|(y)}{GD^2} \quad\text{和}\quad a_K\ge\frac{M_d\|z\|(y)}{GD^2}.

第一类的 $a_K$ 总和至多阈值的两倍，因此这些 $g_K(y)$ 的范数和至多 $2D^{-2}M_d\|z\|(y)$ 。第二类至多有

L_D=2+\lceil\log_2(GD^2)\rceil\le C\log(2D)

个根。由式 $(\mathrm{A4})$ ，先逐点再积分作 Cauchy–Schwarz，得到

S\le4D^{-2}\|z\|_2^2+ \sqrt{L_D}\,\|z\|_2\sqrt S.

解关于 $\sqrt S$ 的二次不等式，得

\sum_K\|g_K\|_2^2\le C\log(2D)\|z\|_2^2. \tag{A7}

因此有界代表所付出的只是对数，而不是 $D$ 的幂。

4. 按末层系数变化停止

H 原稿第 11 页 · H 原稿第 12 页

固定一个大小片段 $K$ ，写 $g=g_K$ 、 $a=a_K$ 。取

\tau=D^{-10},\quad b=2D(m+1), \quad T=\left\lceil b^{128(m+1)^2}\right\rceil. \tag{A8}

令 $c(u)$ 为 $P_u^m\cdots P_u^1g$ 的唯一末层系数向量，补零到全部标签。

在一次从 $R\subseteq K$ 开始的尝试中，根为第零个选定格。从一个选定格 $A$ 出发，把第一批满足

\|c(u)-c(A)\|_2>\tau a

的后代格选为下一代。经过 $T$ 次转移的第一个格交给新尝试。令新根族为 $\mathcal R(R)$ 。

每代选定格可以补成 $R$ 的停止分割：没有下一代的部分用终止格补齐，并在随后阶段保留其投影不变。原掩膜继承确保直和投影族递增。于是本次选定阶段真正满足式 $(\mathrm{A2})$ 、 $(\mathrm{A3})$ 的假设。

每个新根 $R'$ 的路径经过 $T$ 次系数变化。私有下界说明在该根上每次变化的向量范数都大于 $D^{-1}\tau a$ 。所以

TD^{-2}\tau^2a^2\sum_{R'\in\mathcal R(R)}|R'| \le m^2L_T^{2m}\|1_Rg\|_2^2. \tag{A9}

一方面用 $\|g\|_\infty\le Ga$ 控制右端，另一方面用它控制新根上的能量，分别得到

\sum_{R'}|R'|\le E|R|, \quad \sum_{R'}\|1_{R'}g\|_2^2\le E\|1_Rg\|_2^2,

E=\frac{16D^{32}m^2L_T^{2m}}{T}. \tag{A10}

两条收缩都来自同一条式 $(\mathrm{A9})$ ，不能只写长度收缩就跳到能量打包。

由 $b\ge8$ ，可以验证 $L_T\le129(m+1)^2\log_2b\le b^4$ 。第二个不等式由 $m+1\le b/4$ 、 $\log_2b\le b/2$ 及 $129b^3/32\le b^4$ 得到。式 $(\mathrm{A8})$ 因而使 $E<1/2$ 。对所有尝试代数求和，

\sum_{R\text{ 为尝试根}}|R|\le2|K|, \quad \sum_{R\text{ 为尝试根}}\|1_Rg_K\|_2^2\le2\|g_K\|_2^2. \tag{A11}

上取整只增大固定常数；也可在不要求 $b$ 为整数时先取 $b$ 的上整，以逐字沿用整数幂。

5. 每一行的主项和系数误差

H 原稿第 12 页 · H 原稿第 13 页

把每行分给包含其格的最深尝试根 $R$ 。设该行格 $u$ 在本次尝试中最近的已选祖先格为 $A$ ，阶段为 $j<T$ 。停止规则给出

\|c(u)-c(A)\|_2\le\tau a_K. \tag{A12}

该格完全包含在第 $j$ 阶段分割的选定格 $A$ 中，故第 $j$ 阶段乘积在 $u$ 上恰好是祖先乘积的限制。主项由式 $(\mathrm{A2})$ 控制，平方和至多

L_T^{2m}\|1_Rg_K\|_2^2. \tag{A13}

这里的阶段是最近已选祖先的编号，不是行的物理深度。

误差写成 $\sum_ve_{\nu,v}\Phi_v$ 。若 $e_{\nu,v}\ne0$ ，则 $u(\nu)\subseteq R\cap J_v$ 。令 $\widetilde\Phi_v=1_{J_v}\Phi_v$ ，局部性给出

B_\nu1_{u(\nu)}\sum_ve_{\nu,v}\Phi_v =\sum_ve_{\nu,v}B_\nu(1_R\widetilde\Phi_v).

先对 $v$ 用 Cauchy–Schwarz，再对每个固定标签用行收缩，误差平方和至多

\begin{aligned} \tau^2a_K^2\sum_v\sum_{\nu\text{ 分给 }R} \|B_\nu(1_R\widetilde\Phi_v)\|^2 &\le\tau^2a_K^2\sum_v\|1_R\widetilde\Phi_v\|_2^2\\ &\le\tau^2a_K^2D^3|R|. \end{aligned} \tag{A14}

最后一步是

\sum_v\|1_R\widetilde\Phi_v\|_2^2 =\int_R\sum_{v:y\in J_v}\|\Phi_v(y)\|^2\,\mathrm dy \le D^3|R|.

所以不同分支上再多的标签也不增加常数。

6. 总和与使用边界

H 原稿第 13 页 · 主文中的压缩用途 · 联合 Bessel 行的应用

每行只属于一个大小片段、一次尝试。在总行 Hilbert 空间中用三角不等式，将式 $(\mathrm{A13})$ 、 $(\mathrm{A14})$ 相加，再用式 $(\mathrm{A6})$ 、 $(\mathrm{A7})$ 、 $(\mathrm{A11})$ ，得到

\begin{aligned} \left(\sum_\nu\|B_\nu P^m_{u(\nu)}\cdots P^1_{u(\nu)}z\|^2\right)^{1/2} &\le L_T^m\left(2\sum_K\|g_K\|_2^2\right)^{1/2} +\tau D^{3/2}\left(2\sum_Ka_K^2|K|\right)^{1/2}\\ &\le C\left[L_T^m\sqrt{\log(2D)}+D^{-17/2}\right]\|z\|_2. \end{aligned}

又因 $L_T\le C(m+1)^3\log(2D)$ ，得到主文式 $(11)$ 。空乘积直接使用原行收缩。含补投影时将每个 $1-P$ 展开，至多 $2^m$ 项仍可吸收到同一种界。对全体行共同固定的有限测度平均，若逐参数的投影乘积可测且统一满足上述预算，在行空间使用积分三角不等式，额外成本只是测度总变差；这里不包括逐行另选测度或投影族。

这个论证证明的是：任何已经固定、满足出生预算和条件数假设的有限列系统，都有深度无关空间压缩。它不证明某个自适应目录具有出生预算；主文第 5、8、12 节分别证明旧列、预测列和额外高列的预算。两项工作不能互作前提。