第四单元（续）：低维投影与近正交张量

本篇讨论 B §4 的 Theorem 4.1、Lemma 4.2 及其证明，原文 pp.11–14。这里是有限维 Hilbert 空间论证，不用 mixing、选取长度或 distal 结构。后面 B §5 才把此估计用于按起点选择的遍历平均。

原文把这个结果称为 tensor packing。下面直接陈述所估计的数量：一列近正交的秩一张量中，有多少个在同一个低维子空间上的投影仍然较大。

1. 完整陈述

Hilbert 空间均为实空间，张量积为 Hilbert 张量积，对数为自然对数。固定

0<\varepsilon\le1, \quad d\ge1, \quad L\ge0,

其中 $d,L$ 为整数。设 $x_1,\ldots,x_m$ 与 $y_1,\ldots,y_m$ 分别属于 $H_1,H_2$ 的单位球。

对 $x$ 这列向量，存在一个顶点集为 $\{1,\ldots,m\}$ 、最大度数不超过 $L$ 的图，包含所有满足

i\ne j, \quad |\langle x_i,x_j\rangle|>\eta

的配对。 $y$ 这列也满足同样条件，其例外图可以不同。阈值满足

0\le\eta\le\varepsilon^2/10^4.

B Theorem 4.1（p.11，式 (4.1)）断言：存在绝对常数 $C$ ，对每个秩至多 $d$ 的正交投影 $P:H_1\otimes H_2\to H_1\otimes H_2$ ，都有

\#\{n:\|P(x_n\otimes y_n)\|\ge\varepsilon\} \le C(1+L)\varepsilon^{-2} \exp\!\left(C\varepsilon^{-2}\sqrt d\log(2+d)\right). \tag{Count}

常数不依赖两个 Hilbert 空间的维数。此处 $d$ 表示投影维数上界，与遍历平均的函数个数无关。

2. 图外小内积限制平均向量

对应 B p.12，证明中的式 (4.5)。

若单位球向量 $v_n$ 在最大度数 $L$ 的例外图之外满足 $|\langle v_i,v_j\rangle|\le\eta$ ，则对任意非空指标集合 $A$ ，

\left\|\frac1{|A|}\sum_{n\in A}v_n\right\|^2 \le\frac{1+L}{|A|}+\eta. \tag{Mean}

展开左边平方。有 $|A|$ 个对角项，每项至多 $1$ ；有序的例外配对至多 $L|A|$ 个，每项绝对值至多 $1$ ；其他项绝对值至多 $\eta$ 。除以 $|A|^2$ ，即得式 (Mean)。

反过来，如果某批向量的平均范数至少为 $a>0$ ，且 $a^2>\eta$ ，则

|A|\le\frac{1+L}{a^2-\eta}.

后面两次用到这一事实：先限制高协方差方向上的指标数，再限制投影系数靠得很近的指标数。

3. 先转到有限维，再写成矩阵

3.1 有限维化不会减少待估计数量

对应 B p.12，有限线性张成的化简段。

令 $H'_1$ 与 $H'_2$ 分别由有限列 $x_n$ 、 $y_n$ 张成，令 $Q$ 投影到 $H'_1\otimes H'_2$ 。原投影子空间为 $E=\operatorname{Ran}P$ ，用 $E'=Q(E)$ 代替，并令 $P'$ 为到 $E'$ 的正交投影。 $E'$ 有限维，且 $\dim E'\le d$ 。

对 $z\in H'_1\otimes H'_2$ ，

\|Pz\|=\sup_{\substack{u\in E\\\|u\|\le1}}|\langle z,u\rangle| =\sup_{\substack{u\in E\\\|u\|\le1}}|\langle z,Qu\rangle| \le\|P'z\|.

第二个等号使用 $Qz=z$ ，最后用 $Qu\in E'$ 、 $\|Qu\|\le1$ 。因此证明新投影的计数界足以控制原投影。此后可把 $H_1,H_2$ 视为有限维空间，并用 $P$ 表示这个新的投影。

3.2 Hilbert–Schmidt 正交基与两个协方差矩阵

把 $x\otimes y$ 识别为从 $H_2$ 到 $H_1$ 的秩一矩阵。取投影子空间的 Hilbert–Schmidt 标准正交基 $A_1,\ldots,A_r$ ， $r\le d$ 。如果 $r=0$ ，计数为零，以下无需继续。

定义

R_1=\sum_{j=1}^{r}A_jA_j^*, \quad R_2=\sum_{j=1}^{r}A_j^*A_j.

两者正半定，而且

\operatorname{tr}R_1=\operatorname{tr}R_2 =\sum_{j=1}^{r}\|A_j\|_{\mathrm{HS}}^2=r\le d.

令 $E_1,E_2$ 分别由对应矩阵中大于 $\sqrt d$ 的特征值所对应特征向量张成。每个空间的维数不超过 $\sqrt d$ ：每个这样特征值至少贡献 $\sqrt d$ 的迹，而总迹至多 $d$ 。

4. 排除高协方差方向上的少量指标

对应 B pp.12–13，式 (4.6)。

4.1 有限网的大小

在一个 $k$ -维欧氏单位球内，取极大的、两两距离大于 $\rho$ 的点集。半径 $\rho$ 的球覆盖单位球；这些点周围半径 $\rho/2$ 的球互不相交，且包含在半径 $1+\rho/2$ 的球内。比较体积得到点数至多

(1+2/\rho)^k.

取 $\rho=\varepsilon/40$ 、 $k\le\sqrt d$ ，所以 $E_1$ 或 $E_2$ 的单位球可以用至多

(1+80/\varepsilon)^{\sqrt d}

个半径 $\varepsilon/40$ 的球覆盖。

4.2 每个小球至多含多少个大投影

先删除满足 $\|P_{E_1}x_n\|>\varepsilon/10$ 的指标。若其中 $s$ 个投影落在同一个网球内，任取其中一个投影，它与其他投影的距离不超过 $\varepsilon/20$ 。故这批投影的平均范数至少为 $\varepsilon/20$ 。原向量平均的范数不会小于其正交投影的平均范数。

由式 (Mean)，

\varepsilon^2/400\le\frac{1+L}{s}+\eta.

由于 $\eta\le\varepsilon^2/10^4$ ，得到 $s\le C(1+L)\varepsilon^{-2}$ 。对所有网球相加，再对 $y_n,E_2$ 做同样删除，总删除数至多

C(1+L)\varepsilon^{-2} \exp\!\left(\sqrt d\log(1+80/\varepsilon)\right). \tag{Exceptional}

两列使用的例外图可以不同，以上分别估计后相加即可。

5. 剩余指标的系数向量与分离集合

对应 B p.13，从压缩矩阵 $B_j$ 到极大分离集的段落。

5.1 压缩后仍然有较大的系数

令 $Q_i$ 为到 $E_i^\perp$ 的正交投影，并设

B_j=Q_1A_jQ_2.

对未删除的指标，

\begin{aligned} \|x_n\otimes y_n-Q_1x_n\otimes Q_2y_n\| &\le\|(1-Q_1)x_n\|\,\|y_n\| +\|Q_1x_n\|\,\|(1-Q_2)y_n\|\\ &\le\varepsilon/5. \end{aligned}

系数映射 $z\mapsto(\langle A_j,z\rangle_{\mathrm{HS}})_j$ 是压缩映射，因为 $A_j$ 标准正交。因此，对仍满足 $\|P(x_n\otimes y_n)\|\ge\varepsilon$ 的指标，定义

v_n=(\langle x_n,B_jy_n\rangle)_{j=1}^{r},

就有 $\|v_n\|\ge\varepsilon-\varepsilon/5\ge\varepsilon/2$ 。从原张量 $x_n\otimes y_n$ 到 $v_n$ 的映射仍为压缩映射。

5.2 一个系数球内的指标数仍受控制

两列原向量的例外图之并，最大度数不超过 $2L$ 。在这个并图之外，

|\langle x_n\otimes y_n,x_{n'}\otimes y_{n'}\rangle| =|\langle x_n,x_{n'}\rangle|\, |\langle y_n,y_{n'}\rangle| \le\eta^2.

若一批系数向量都在某个 $v_{n_0}$ 的半径 $\varepsilon/8$ 球中，则它们的平均范数至少

\|v_{n_0}\|-\varepsilon/8\ge3\varepsilon/8.

原张量平均的范数至少有这么大，因为系数映射压缩。对原张量使用式 (Mean)，现在例外度数为 $2L$ 、阈值为 $\eta^2$ ，得到这一批指标至多 $C(1+L)\varepsilon^{-2}$ 个。

在剩余系数向量中取一个极大的 $\varepsilon/8$ -分离子集，记其大小为 $\ell$ 。极大性说明每个系数向量都落在某个分离点的半径 $\varepsilon/8$ 球内。因此，剩余待计数指标数至多

C(1+L)\varepsilon^{-2}\ell. \tag{Clusters}

问题化为估计 $\ell$ ，而不是直接对整个 $r$ -维系数球使用一个指数于 $d$ 的网。

6. Gaussian 矩阵估计

对应 B Lemma 4.2，pp.11–12，式 (4.3)–(4.4)。

6.1 自伴随扩充

设 $B_1,\ldots,B_r$ 是有限维实 Hilbert 空间之间的矩阵，定义

H_j=\begin{pmatrix}0&B_j\\B_j^*&0\end{pmatrix}, \quad S=\sum_{j=1}^{r}H_j^2.

假设

\|S\|_{\mathrm{op}}\le\sqrt d, \quad \operatorname{tr}S\le2d.

对独立标准正态变量 $g_j$ ，Lemma 4.2 的结论是

\mathbb E\left\|\sum_{j=1}^{r}g_jB_j\right\|_{\mathrm{op}} \le C d^{1/4}\sqrt{\log(2+d)}. \tag{Gaussian}

令 $H=\sum_jg_jH_j$ 、 $G=\sum_jg_jB_j$ 。则 $H$ 是 $G$ 的上述自伴随扩充，且 $\|H\|_{\mathrm{op}}=\|G\|_{\mathrm{op}}$ 。

6.2 Gaussian 分部积分与矩阵幂求导

对整数 $q\ge2$ ，先写

\operatorname{tr}H^{2q} =\sum_jg_j\operatorname{tr}(H_jH^{2q-1}).

使用标准正态分部积分 $\mathbb E[g_jF(g)]=\mathbb E[\partial_{g_j}F(g)]$ ，并对矩阵幂逐项求导，得到

\mathbb E\operatorname{tr}H^{2q} =\sum_{j=1}^{r}\sum_{a=0}^{2q-2} \mathbb E\operatorname{tr}(H_jH^aH_jH^{2q-2-a}).

这里 $F$ 是多项式，所有正态矩有限，分部积分合法。

6.3 不交换的矩阵项为何仍能估计

固定自伴随矩阵 $H$ ，在其特征基中写特征值为 $\lambda_u$ 。对任意自伴随 $K$ ，令 $p=2q-2$ ，则

|\operatorname{tr}(KH^aKH^{p-a})| \le\sum_{u,v}|K_{uv}|^2|\lambda_v|^a|\lambda_u|^{p-a}.

加权算术几何平均给出

x^ay^{p-a}\le\frac ap x^p+\left(1-\frac ap\right)y^p \quad(x,y\ge0).

利用 $|K_{uv}|=|K_{vu}|$ ，对 $u,v$ 求和后两项相同，于是

|\operatorname{tr}(KH^aKH^{p-a})| \le\operatorname{tr}(K^2|H|^p).

对 $j$ 求和，并用 $S$ 正半定，得到

\mathbb E\operatorname{tr}H^{2q} \le(2q-1)\mathbb E\operatorname{tr}(S|H|^{2q-2}) \le(2q-1)\|S\|_{\mathrm{op}} \mathbb E\operatorname{tr}|H|^{2q-2}.

最后一步不要求 $S$ 与 $H$ 交换： $0\le S\le\|S\|I$ ，与正半定 $|H|^{2q-2}$ 配对取迹即可。

6.4 迹只出现一次

直接计算 $\mathbb E\operatorname{tr}H^2=\operatorname{tr}S$ 。递推上面的不等式，得到

\mathbb E\operatorname{tr}H^{2q} \le(2q-1)!!\,\|S\|_{\mathrm{op}}^{q-1}\operatorname{tr}S.

由 $\|H\|^{2q}\le\operatorname{tr}H^{2q}$ 和 Hölder 不等式，

\mathbb E\|H\|_{\mathrm{op}} \le\bigl(\mathbb E\operatorname{tr}H^{2q}\bigr)^{1/(2q)} \le C\sqrt q\,d^{1/4}(2\sqrt d)^{1/(2q)}.

选 $q=\max\{2,\lceil\log(2+d)\rceil\}$ 。最后一因子有绝对上界，而 $\sqrt q\le C\sqrt{\log(2+d)}$ ，得到式 (Gaussian)。

整个推导用的是 $\operatorname{tr}S\le2d$ ，而非环境维数乘 $\|S\|$ 。因此不会出现依赖 $\dim H_1$ 或 $\dim H_2$ 的因子。

7. 有限 Gaussian 比较为何控制分离集

对应 B p.13，式 (4.7) 及其后关于 Gaussian 插值的说明。

7.1 比较命题的准确形式

设 $(X_1,\ldots,X_\ell)$ 和 $(Y_1,\ldots,Y_\ell)$ 是两个中心化有限 Gaussian 向量。如果对全部 $i,j$ ，

\mathbb E(X_i-X_j)^2\ge\mathbb E(Y_i-Y_j)^2,

则

\mathbb E\max_iX_i\ge\mathbb E\max_iY_i. \tag{SF}

不要求每个对应坐标方差相等。这个有限形式通常称为 Sudakov–Fernique 比较。

7.2 用光滑最大值证明比较

可把两个向量放在独立的概率空间上。对 $\beta>0$ ，令

f_\beta(z)=\beta^{-1}\log\sum_{i=1}^{\ell}\mathrm e^{\beta z_i}, \quad p_i(z)=\frac{\mathrm e^{\beta z_i}}{\sum_j\mathrm e^{\beta z_j}}.

有 $\partial_if_\beta=p_i$ ，以及

\partial_{ij}f_\beta =\beta(\delta_{ij}p_i-p_ip_j).

考虑独立 Gaussian 插值 $Z_t=\sqrt t\,X+\sqrt{1-t}\,Y$ 。记协方差差矩阵为 $\Delta C=C_X-C_Y$ 。在 $0<t<1$ 上对期望求导，再对 Gaussian 变量分部积分，得到

\begin{aligned} \frac{\mathrm{d}}{\mathrm{d}t}\mathbb E f_\beta(Z_t) &=\frac12\sum_{i,j}\Delta C_{ij} \mathbb E\,\partial_{ij}f_\beta(Z_t)\\ &=\frac\beta4\mathbb E\sum_{i,j}p_i(Z_t)p_j(Z_t) \left[\mathbb E(X_i-X_j)^2-\mathbb E(Y_i-Y_j)^2\right]. \end{aligned}

第二个等号使用 $\sum_jp_j=1$ ，将两个对角方差项与协方差项合并。假设使导数非负。有限维 Gaussian 的矩存在， $f_\beta$ 的一、二阶导数有界；先在内部闭区间积分，再由端点连续性取极限，得到 $\mathbb E f_\beta(X)\ge\mathbb E f_\beta(Y)$ 。退化协方差也可通过加入独立小 Gaussian 噪声后取极限处理。

最后利用

\max_i z_i\le f_\beta(z)\le\max_i z_i+\frac{\log\ell}{\beta},

令 $\beta\to\infty$ ，即得式 (SF)。

7.3 独立正态最大值的下界

对独立标准正态 $\xi_1,\ldots,\xi_\ell$ ，有一个绝对常数 $c>0$ ，使

\mathbb E\max_{1\le i\le\ell}\xi_i \ge c\sqrt{\log\ell} \quad(\ell\ge2). \tag{Normal}

可由正态尾部直接验证。对 $u\ge1$ ，只积分区间 $[u,u+1/u]$ ，得到

\mathbb P(\xi_1\ge u) \ge\frac1{u\sqrt{2\pi}} \exp\!\left(-\frac{(u+1/u)^2}{2}\right) \ge\frac c u\mathrm e^{-u^2/2}.

取 $u=\tfrac12\sqrt{\log\ell}$ 。当 $\ell$ 足够大时， $\ell\mathbb P(\xi_1\ge u)\to\infty$ ，所以独立性给出

\mathbb P\left(\max_i\xi_i\ge u\right) =1-\bigl(1-\mathbb P(\xi_1\ge u)\bigr)^\ell\ge\tfrac12.

还须控制最大值的负部。记 $M_\ell=\max_i\xi_i$ ，则

\mathbb E(-M_\ell)_+ =\int_0^\infty\mathbb P(\xi_1<-t)^\ell\,\mathrm{d}t \le2^{-(\ell-1)}\mathbb E(-\xi_1)_+ =\frac{2^{-(\ell-1)}}{\sqrt{2\pi}}.

故 $\mathbb EM_\ell\ge u/2-o(1)\ge c\sqrt{\log\ell}$ 对所有足够大的 $\ell$ 成立。其余有限多个 $\ell\ge2$ ，使用单调性和

\mathbb E\max(\xi_1,\xi_2) =\frac12\mathbb E|\xi_1-\xi_2|=\frac1{\sqrt\pi}>0

，再缩小绝对常数 $c$ ，得到式 (Normal) 的完整范围。

7.4 应用到压缩后的系数向量

在第五节的分离集上，令

G=\sum_{j=1}^{r}g_jB_j, \quad Z_n=\langle x_n,Gy_n\rangle.

这些是中心化 Gaussian 变量，其增量方差为

\mathbb E|Z_n-Z_{n'}|^2 =\|v_n-v_{n'}\|^2\ge\varepsilon^2/64 \quad(n\ne n').

与独立正态 $Y_n$ 比较，其中每个 $Y_n$ 方差为 $\varepsilon^2/128$ 。它们的两两增量方差正好为 $\varepsilon^2/64$ 。式 (SF)、式 (Normal) 因此给出

c\varepsilon\sqrt{\log\ell} \le\mathbb E\max_n Z_n \le\mathbb E\|G\|_{\mathrm{op}}. \tag{Sep}

最后一步使用 $\|x_n\|,\|y_n\|\le1$ 。它不要求 $Z_n$ 相互独立；独立的是用于比较的 $Y_n$ 。

8. 压缩后的协方差满足 Gaussian 矩阵引理

原文位置：B p.13，式 (4.7) 之后。

由 $B_j=Q_1A_jQ_2$ 以及 $0\le Q_i\le I$ ，

\sum_jB_jB_j^*\le Q_1R_1Q_1, \quad \sum_jB_j^*B_j\le Q_2R_2Q_2.

按第三节的谱截断定义，右边的算子范数不超过 $\sqrt d$ ，迹不超过 $d$ 。因此对第六节的自伴随扩充，

S=\begin{pmatrix} \sum_jB_jB_j^*&0\\ 0&\sum_jB_j^*B_j \end{pmatrix}

满足 $\|S\|_{\mathrm{op}}\le\sqrt d$ 、 $\operatorname{tr}S\le2d$ 。式 (Gaussian) 可以应用。

将其与式 (Sep) 合并，平方并整理，得到

\log\ell\le C\varepsilon^{-2}\sqrt d\log(2+d).

若 $\ell\le1$ ，相应指数界自动成立。由式 (Clusters)，剩余待计数指标数不超过

C(1+L)\varepsilon^{-2} \exp\!\left(C\varepsilon^{-2}\sqrt d\log(2+d)\right).

再加上式 (Exceptional) 中先行删除的指标。因为 $0<\varepsilon\le1$ ，

\log(1+80/\varepsilon)\le C\varepsilon^{-2},

且 $\log(2+d)$ 有正的绝对下界，这部分也被同一形式吸收。增大一个绝对常数后，得到式 (Count)。

9. 对数增长的维数与平均形式

对应 B p.11 的式 (4.2)、p.13 末段及 p.14 的式 (4.8)。

9.1 为什么所选维数仍给次线性计数

令

d_m=\left\lceil(1+\log m)^{3/2}\right\rceil.

当 $m\to\infty$ 时，

\sqrt{d_m}\log(2+d_m) =O\bigl((\log m)^{3/4}\log\log m\bigr) =o(\log m).

因此，对每个固定 $\varepsilon,L$ ，式 (Count) 右边是 $\exp(o(\log m))$ 乘一个固定常数，从而为 $o(m)$ 。这个 $o(m)$ 对环境 Hilbert 空间、向量列、投影以及允许范围内的 $\eta$ 一致。

9.2 平均投影范数

每个投影范数都不超过 $1$ 。把指标分成投影范数小于 $\varepsilon$ 与至少为 $\varepsilon$ 两组，得到

\frac1m\sum_{n=1}^{m}\|P(x_n\otimes y_n)\| \le\varepsilon+ \frac{C(1+L)}{m\varepsilon^2} \exp\!\left(C\varepsilon^{-2}\sqrt{d_m}\log(2+d_m)\right).

量词次序为：先固定所需精度 $\varepsilon$ ，再选满足条件的 $\eta$ 以及相应例外度数 $L$ ，最后让 $m$ 增大。 $L$ 可以依赖前面选择的 $\eta$ ，但在这次 $m\to\infty$ 中必须固定。

这个有限维估计没有提供混合速率。后面若从定性的相关衰减取得某个有限例外度数，就按上述次序使用估计，而不是把一个未给出的统一速率加入假设。

原文对照与证明范围

B p.11，Theorem 4.1，式 (4.1)–(4.2)：计数结论与 $d_m$ 。
B pp.11–12，Lemma 4.2，式 (4.3)–(4.4)：Gaussian 矩阵矩估计。
B p.12，式 (4.5)：例外图条件下的平均范数界。
B pp.12–13，式 (4.6)：高协方差方向的有限网计数。
B p.13，式 (4.7)：分离系数向量、Gaussian 比较与投影范数。
B p.14，式 (4.8)：平均形式及参数选择次序。

本篇给出这个有限 Hilbert 空间结果的完整推导，并展开原文简写的 Gaussian 比较和独立正态最大值下界。它在遍历论构造中的应用尚需验证向量列、例外图及投影维数等假设，不能由这个估计本身推出四重逐点收敛。