阅读设置

设置与阅读位置仅保存在这个浏览器。

中文English0%

选择一段文字或公式,即可在这里留下建议。保存后的建议仅作者可见,审核后才会公开。

第三单元(续):先选择偏移,再控制非核心部分的路径平方和

本篇展开 D §6.4 中式 (6.13)–(6.15),原文 pp.50–51。前篇已经在所列源几何前提下得到冻结非核心模式的平方能量。现在把它与当前输出的滚动变化合并,选择一个物理近似误差小的偏移,并通过首次超限停止得到逐路径的平方和控制。

H 的偏移截断满足下文列明的平均误差性质。主局部化数据及其实际使用集合须在偏移选择之前固定;后来的模式选择和停止可以依赖这个已选偏移,不需要另加独立性假设。

1. 三个分量位于什么空间

本段暂固定 α>0\alpha>0、0<θ<10<\theta<1,使用

η=exp⁡(−kθ),P=⌈η−α⌉=⌈exp⁡(αkθ)⌉. \eta=\exp(-k^\theta),\qquad P=\lceil\eta^{-\alpha}\rceil =\lceil\exp(\alpha k^\theta)\rceil.

因此 G0=Po(1)G_0=P^{o(1)}、log⁡P=O(k)\log P=O(k);最终共同参数的选择仍在 D §7 完成。

固定一个位置 ll、组 GG 与分析块 [b,b+K)[b,b+K)。主输出为 Zl,G,sZ_{l,G,s},在 ub=b−4Ku_b=b-4K 冻结后,经固定线性映射得到

Z~l,G,b=Rl,GZl,G,ub. \widetilde Z_{l,G,b}=\mathcal R_{l,G}Z_{l,G,u_b}.

把其模式展开按固定分类分成精确核心部分 Al,G,bA_{l,G,b} 与精确非核心部分 Vl,G,bV_{l,G,b},所以

Z~l,G,b=Al,G,b+Vl,G,b. \widetilde Z_{l,G,b}=A_{l,G,b}+V_{l,G,b}.

主空间与模式空间共享同一个物理标量坐标,私有坐标作互不相交的标记,嵌入一个共同的 Hilbert 直和。这样下面的向量加减均有确定含义,所有范数仍保留各自的私有分量。

在基本 BB 位置,定义

Sl,G,sroll=Zl,G,s−Zl,G,ub,Sl,G,s=Sl,G,sroll+Vl,G,b. S^{\mathrm{roll}}_{l,G,s}=Z_{l,G,s}-Z_{l,G,u_b}, \qquad S_{l,G,s}=S^{\mathrm{roll}}_{l,G,s}+V_{l,G,b}.

另定义纯物理误差

El,G,b=(Zl,G,ub)phys−(Z~l,G,b)phys. E_{l,G,b} =(Z_{l,G,u_b})_{\mathrm{phys}} -(\widetilde Z_{l,G,b})_{\mathrm{phys}}.

于是对 b≤s<b+Kb\le s<b+K,有 D 式 (6.13) 的物理恒等式

(Zl,G,s)phys=(Al,G,b)phys+(Sl,G,s)phys+El,G,b.(Physical-split) (Z_{l,G,s})_{\mathrm{phys}} =(A_{l,G,b})_{\mathrm{phys}} +(S_{l,G,s})_{\mathrm{phys}}+E_{l,G,b}. \tag{Physical-split}

在基本 UU 位置,不建立核心部分:令 Sl,G,s=Zl,G,sUS_{l,G,s}=Z^U_{l,G,s},物理误差为零。这一位置在后面始终属于非核心部分。

2. 偏移选择前固定的资料

使用 H 的统一参数上界和共同分析块长度。以下资料在选择偏移之前已经固定:

  • 主列函数族、主投影与搜索分支;
  • 全部原始实际主使用 (l,G,I)(l,G,I) 及它们的冻结端点 ub(I)u_{b(I)};
  • 冻结主输出在整个端点区间上的系数
Zl,G,ub=∑ΦβΦΦ. Z_{l,G,u_b}=\sum_\Phi\beta_\Phi\Phi.

因此可以先对所有这些实际使用的误差取偏移平均,而不随着后来保留了哪些模式重新定义求和集合。

H 的偏移截断满足

Eρ∣1−(ζρ(y))2∣2≤Cdmax⁡δc, \mathbb E_\rho|1-(\zeta^\rho(y))^2|^2 \le C d_{\max}\delta_c,

其中取 dmax⁡≥1d_{\max}\ge1 为相关维数的统一上界;零维情形采用源常数截断约定。精度

δc=exp⁡(−kCc) \delta_c=\exp(-k^{C_c})

在主列函数常数确定后选择。

固定映射的构造给出逐点等式

El,G,b=(1−(ζρ)2)(Zl,G,ub)phys−∑ΦβΦqΦ,∣qΦ∣≤δc.(Offset-error) E_{l,G,b} =(1-(\zeta^\rho)^2)(Z_{l,G,u_b})_{\mathrm{phys}} -\sum_\Phi\beta_\Phi q_\Phi, \quad |q_\Phi|\le\delta_c. \tag{Offset-error}

3. 整个冻结端点上的系数控制没有深度滞后损失

在一个深度 ubu_b 端点区间 UU 上,实际函数 Fl,ubF_{l,u_b} 的归一化范数至多一。基本 BB 至多两个局部投影之差,内部当前深度投影平均及补算子为压缩,外层主投影也为压缩。因此冻结主输出在 UU 上的归一化 L2L^2 范数有固定上界。

私有坐标下界控制其系数的 ℓ2\ell^2 范数;路径列数与列函数大小再控制系数 ℓ1\ell^1 范数和物理上界。对正平均先将系数补零到共同指标集再平均,结论仍成立。于是

∑Φ∣βΦ∣,∥(Zl,G,ub)phys∥∞,U≤DmC.(Whole-endpoint-size) \sum_\Phi|\beta_\Phi|,\quad \|(Z_{l,G,u_b})_{\mathrm{phys}}\|_{\infty,U} \le D_{\mathrm m}^C. \tag{Whole-endpoint-size}

这里是在原来的整个 ubu_b 区间上估计。没有将某个很细使用区间上的范数放大到祖先,因此不产生 24K2^{4K} 因子。

由式 (Offset-error)、(Whole-endpoint-size) 及偏移平均性质,

Eρ∣El,G,b(y)∣2≤DmCdmax⁡δc. \mathbb E_\rho|E_{l,G,b}(y)|^2 \le D_{\mathrm m}^C d_{\max}\delta_c.

主实际使用的路径次数也已被主预算控制。积分并对选择前固定的全部实际使用求和,得到

Eρ∑l,G,I 实际使用∣I∣∥El,G,b(I)∥2,I2≤DmCdmax⁡δc∣R∣.(Average-error) \mathbb E_\rho \sum_{l,G,I\text{ 实际使用}} |I|\|E_{l,G,b(I)}\|_{2,I}^2 \le D_{\mathrm m}^C d_{\max}\delta_c|R|. \tag{Average-error}

4. 选偏移后不需要再证明独立性

式 (Average-error) 是一个非负随机量的平均界。若右侧为正,Markov 不等式保证存在偏移,使该总误差不超过右侧的两倍;若平均为零,则总误差几乎处处为零。固定这样的偏移,常数二吸收进统一常数。

前篇非核心模式能量

∑G,b∥Vl,G,b∥22≤G0∣R∣(V-energy) \sum_{G,b}\|V_{l,G,b}\|_2^2\le G_0|R| \tag{V-energy}

对任意备选偏移一致,因而在此选择后仍成立。

后来的核心分类、限制、停止或删除区间可以依赖这个偏移。它们只从已经固定的非负误差和中移除部分项,所以不会增加总误差。这里需要的是先固定主使用再取平均,不是要求后续选择与偏移独立。

选择偏移之后,整个附加向量 Sl,G,sS_{l,G,s} 已确定。D p.50 随后调用 H 的辅助列闭合构造,其测试对象是这些完整向量及原来规定的有序投影积;不为每个模式、每个高度或每个大小另造一个辅助基底。这个构造的计数是主列函数常数预先包含的资料,本篇不重新证明 H 的闭合命题。

5. 三种非核心组成部分的积分平方和

对应 D 式 (6.14),p.51。

5.1 滚动变化

对每个使用深度 s∈[b,b+K)s\in[b,b+K),比较区间为 [ub,s][u_b,s]。对于一条固定深度边,可能覆盖它的块起点只落在一个长度为 5K5K 的范围内,块起点间隔为 KK;每块有至多 KK 个使用深度。因此这组深度区间的边重叠数为 O(K)O(K)。

对各组取实际使用深度 ss 区间的并作为右端集合,应用已经证明的 D Lemma 6.1。相同深度的使用区间互不相交,得到

∑s,G∑I 在 s 使用∣I∣∥Sl,G,sroll∥2,I2≤CKG0∣R∣.(Rolling-square) \sum_{s,G}\sum_{I\text{ 在 }s\text{ 使用}} |I|\|S^{\mathrm{roll}}_{l,G,s}\|_{2,I}^2 \le CKG_0|R|. \tag{Rolling-square}

5.2 冻结的非核心模式在一个块中被重复使用

固定 G,bG,b 后,Vl,G,bV_{l,G,b} 在整个块中是同一个函数。每个深度的使用区间不交,故这一深度的限制范数平方和不超过其全空间范数平方。一个块至多有 KK 个使用深度,由式 (V-energy),

∑s,G∑I 在 s 使用∣I∣∥Vl,G,b(s)∥2,I2≤KG0∣R∣.(Repeated-V) \sum_{s,G}\sum_{I\text{ 在 }s\text{ 使用}} |I|\|V_{l,G,b(s)}\|_{2,I}^2 \le KG_0|R|. \tag{Repeated-V}

这不是假设不同块的系数相同,而是对每个块分别计其最多 KK 次使用。

5.3 基本 UU 位置

在每个固定深度,外层组投影对共同函数的平方和界可应用于内部共享有序积作用后的 UsU_s。内部当前深度投影为局部压缩,因此不会增加对应深度使用区间上的总能量。

再用基本 UU 的延迟增量平方能量,得到

∑s,G∑I 在 s 使用∣I∣∥Zl,G,sU∥2,I2≤G0∣R∣.(U-side) \sum_{s,G}\sum_{I\text{ 在 }s\text{ 使用}} |I|\|Z^U_{l,G,s}\|_{2,I}^2 \le G_0|R|. \tag{U-side}

基本能量中的 kk 固定多项式已吸收进 G0G_0。

在 BB 位置用

∥Sroll+V∥2≤2∥Sroll∥2+2∥V∥2. \|S^{\mathrm{roll}}+V\|^2 \le2\|S^{\mathrm{roll}}\|^2+2\|V\|^2.

结合 K≤poly⁡(P,k)K\le\operatorname{poly}(P,k)、G0=Po(1)G_0=P^{o(1)},各位置整个 SS 的积分平方和都由 PC∣R∣P^C|R| 控制。但后面停止时仍要分别保留三个组成部分的界。

6. 从积分平方和到保留路径的平方和

这里展开原文引用的 componentwise first-crossing construction。

对一个固定组成部分,令每个原使用区间 II 的非负权为 aIa_I,它等于该区间上该组成部分的归一化平方大小,对指定的组求和。已有

∑I∣I∣aI≤B0∣R∣. \sum_I|I|a_I\le B_0|R|.

对路径点 yy,其总权为

A(y)=∑I∋yaI,∫RA(y) dy≤B0∣R∣. A(y)=\sum_{I\ni y}a_I,\qquad \int_RA(y)\,\mathrm{d}y\le B_0|R|.

取阈值 MB0M B_0。沿路径从上向下,若原使用区间处的累计权第一次超过该阈值,就切出该区间及其原后代。首次超限区间两两不交,且每个这样的区间上,已累计权都是常数并大于阈值。因此

∑I 首次超限∣I∣≤∣R∣M. \sum_{I\text{ 首次超限}}|I| \le\frac{|R|}{M}.

将首次超限格及其后代原求和项转交新尝试,严格祖先仍完整保留。对每条路径,本次尝试留下的前缀累计权不超过 MB0M B_0;即使路径后来进入一个切格,也不把移交后的项继续计入这个前缀。

分别对滚动部分、重复 VV 及基本 UU 部分作这一构造。D 式 (6.5) 的搜索叶至多为 poly⁡(k)\operatorname{poly}(k) 个,颜色、位置与这里三个组成部分的合并配置数也至多为 poly⁡(k)\operatorname{poly}(k)。把阈值按这个数目放大,可使全部新增停止根总长度小于任意预定的固定比例,同时各阈值仍为 PP 的固定幂。

于是对保留路径得到 D 式 (6.15):

∑s,G∥Sl,G,sroll∥2,Is(y)2≤PC,∑s,G∥Vl,G,b(s)∥2,Is(y)2≤PC \sum_{s,G}\|S^{\mathrm{roll}}_{l,G,s}\|_{2,I_s(y)}^2\le P^C, \qquad \sum_{s,G}\|V_{l,G,b(s)}\|_{2,I_s(y)}^2\le P^C

于 BB 位置,

∑s,G∥Zl,G,sU∥2,Is(y)2≤PC \sum_{s,G}\|Z^U_{l,G,s}\|_{2,I_s(y)}^2\le P^C

于 UU 位置,进而

∑s,G∥Sl,G,s∥2,Is(y)2≤PC.(Path-squares) \sum_{s,G}\|S_{l,G,s}\|_{2,I_s(y)}^2\le P^C. \tag{Path-squares}

所有和只包括原实际使用。每个已经保留的严格祖先仍作为一个完整原求和项,不被拆分成新项。

7. 核心及非核心的局部大小

在保留的 BB 使用区间 II 上,当前输出 Zl,G,sZ_{l,G,s} 的局部大小由当前投影压缩性及基本 BB 大小控制。又有

Zl,G,ub=Zl,G,s−Sl,G,sroll. Z_{l,G,u_b}=Z_{l,G,s}-S^{\mathrm{roll}}_{l,G,s}.

固定映射 Rl,G\mathcal R_{l,G} 逐点有界,所以

∥Z~l,G,b∥2,I+∥Vl,G,b∥2,I≤C(∥Zl,G,s∥2,I+∥Sl,G,sroll∥2,I+∥Vl,G,b∥2,I)≤PC. \|\widetilde Z_{l,G,b}\|_{2,I} +\|V_{l,G,b}\|_{2,I} \le C\bigl( \|Z_{l,G,s}\|_{2,I} +\|S^{\mathrm{roll}}_{l,G,s}\|_{2,I} +\|V_{l,G,b}\|_{2,I}\bigr) \le P^C.

精确核心部分 A=Z~−VA=\widetilde Z-V 具有相同类型的局部界。整个 SS 由其分量控制。物理误差也可由式 (Physical-split) 或冻结差得到这样的粗局部上界。

这一步用当前输出与已经控制的滚动差推回冻结输出,避免直接从很大祖先区间粗略放大到当前区间。

8. 物理误差怎样变成形式的绝对小误差

在四线性展开中,取一个含 EE 的项,固定其中一个物理误差位置。其他三个位置在保留使用上具有 PCP^C 的局部 L2L^2 大小。局部绝对估计及 Cauchy–Schwarz 给出

∑实际使用∣I∣ ∣HI(⋯ ,E,⋯ )∣≤PC(∑∣I∣∥E∥2,I2)1/2(∑∣I∣)1/2. \begin{aligned} \sum_{\text{实际使用}}|I|\,|\mathcal H_I(\cdots,E,\cdots)| &\le P^C \left(\sum|I|\|E\|_{2,I}^2\right)^{1/2} \left(\sum|I|\right)^{1/2}. \end{aligned}

原主使用的路径次数由主预算控制,所以最后的长度和至多为 DmC∣R∣D_{\mathrm m}^C|R|。使用已选偏移下的式 (Average-error),右侧不超过

PCDmCdmax⁡1/2δc1/2∣R∣. P^C D_{\mathrm m}^C d_{\max}^{1/2}\delta_c^{1/2}|R|.

先固定各项次数,再使 CcC_c 足够大、提高起始精度,就可将其控制为 Ce−k∣R∣C\mathrm e^{-k}|R|。含多个误差的项也可固定其中一个使用平方小量,其余使用刚才的粗局部界;展开项数有限。

因此后续可以在总误差 O(e−k∣R∣)O(\mathrm e^{-k}|R|) 内,只讨论核心与非核心分量,并在范数估计中继续保留全部私有坐标。

原文范围与下一步

  • D p.50,式 (6.13):物理分解、偏移平均、选择后固定完整非核心向量。
  • D p.51,式 (6.14)–(6.15):三个组成部分分别的积分与路径平方和,以及核心局部大小。
  • H §8.7,pp.73–74:先固定主使用再平均偏移,后续依赖偏移的限制只删除非负误差项。

下一段 D pp.51–52 构造随后代继承的核心代表,证明其分离性,并把核心分量大小转为首个超阈值区间的能量界与代表数界。只有取得这些条件,才能在 §6.6 使用源核心计数结果。