高维概率 III · ε-网与随机矩阵的谱界

前置：亚高斯集中、随机向量与各向同性，以及欧氏范数、矩阵乘法和对称矩阵的谱定理。下文会补出本页需要的网论证。

本页的问题：一台线性装置把输入 \(u\) 变成 \(Au\)。试过许多输入之后，怎样保证没有漏掉最容易被放大的方向？本页先给一个可以完整证明的二维实验，再把“有限扫描”升级为高维概率界，最后用它证明协方差估计的样本量结论。

1. 从有限方向得到整个球面的控制

网点的数量从哪里来

\(\mathcal N\subset S^{n-1}\) 称为欧氏 \(\varepsilon\)-网，指每个球面点到某个网点的距离不超过 \(\varepsilon\)。当 \(\varepsilon>0\) 时存在

证明时不断选取与已有点距离都大于 \(\varepsilon\) 的球面点。以这些点为中心、半径 \(\varepsilon/2\) 的开球两两不交，且全在半径 \(1+\varepsilon/2\) 的大球中。比较 \(n\) 维体积，

这个有限上界使选点过程必须终止。终止时若仍有球面点离全部网点超过 \(\varepsilon\)，就还能继续选，矛盾。因此它确实覆盖球面。进一步简写为 \((3/\varepsilon)^n\) 时，要有 \(0<\varepsilon\le1\)。

单网引理：一步一步补上漏掉的方向

设 \(L=\max_{u\in\mathcal N}\|Au\|\)，\(0<\varepsilon<1\)。取达到算子范数的 \(u_*\)，找 \(u_0\in\mathcal N\) 使 \(\|u_*-u_0\|\le\varepsilon\)。由三角不等式和算子范数定义，

移项得到

当 \(\varepsilon=1/4\)，常数可取 \(4/3\)；取较松的 \(2\) 也对，但应知道损失来自哪里。

双网与对称二次型

对 \(A\in\mathbb R^{m\times n}\)，输入 \(u\in S^{n-1}\)，输出测试方向 \(v\in S^{m-1}\)，有

分别取两个球面的 \(\varepsilon\)-网，令 \(u_0,v_0\) 为最近网点。精确分解

说明误差至多 \(2\varepsilon\|A\|\)。因此当 \(\varepsilon<1/2\)，

对称方阵 \(B\) 则由谱定理得到 \(\|B\|=\max_{\|u\|=1}|u^\top Bu|\)。使用

即可用同一个网和同一个 \(1/(1-2\varepsilon)\) 常数控制二次型。绝对值不能省：负特征值的绝对值也可能决定算子范数。

2. 随机矩阵：用尾概率支付方向数量

假设 \(A_{ij}\) 独立、均值为零，且 \(\|A_{ij}\|_{\psi_2}\le K\)。这里

存在与维数无关的正常数 \(C,c\)，对任意 \(t>0\)，

右侧大于 1 时不提供有用概率保证；它仍是一个成立的上界。证明分三步。

固定方向。取确定的单位向量 \(u,v\)，

独立中心亚高斯量的线性组合仍为亚高斯，尺度至多常数倍的 \(K\)，故 \(\mathbb P\{|Z|>s\}\le2e^{-cs^2/K^2}\)。不能把 \(u,v\) 换成已经观察矩阵后挑出的随机最大方向，再直接沿用这个固定方向尾界。

统一控制。预先取两个 \(1/4\)-网，大小分别至多 \(9^n,9^m\)。并集界不要求网点事件彼此独立，给出

回到连续球面。取 \(s=(K/\sqrt c)\sqrt{(m+n)\log9+t^2}\)，再乘双网引理的常数 2。利用 \(\sqrt{m+n}\le\sqrt m+\sqrt n\) 并合并绝对常数，就得到定理。维数代价来自网点数的对数，而不是一句模糊的“随机抵消”。

若条目是真正的独立标准高斯，固定方向的 \(Z\) 恰为 \(N(0,1)\)，可使用明确的尾界 \(2e^{-s^2/2}\)，于是这个较松但常数明确的结论是

这与更精细的 \(\sqrt m+\sqrt n\) 边缘结果不是同一个精度的结论；一张模拟矩阵不能决定所有维数与所有允许分布共用的 \(C\)。

确定界与分布假设

对每个有限矩阵始终有

只有逐项 \(|A_{ij}|\le1\) 时，最后才能简化成 \(\sqrt{mn}\)。高斯条目无界，不能省去最大条目因子。全 1 矩阵达到 \(\sqrt{mn}\)，也说明有方向结构的矩阵可以远离根号级的 iid 典型尺度。

相关预设每行共享一个随机量，且具有非零均值，故同时违反独立条目和中心化条件。重尾预设使用随机符号乘上 Pareto 型幅度，尾指数 \(3/2\)，理论方差无穷；有限伪随机实现有最大可生成值，这不使它成为上述理论模型的亚高斯样本。

3. 三种谱对象不要混用

以一个明确充分的模型理解极限即可：Wigner 的独立非对角标准高斯和独立有界方差高斯对角，或 iid 标准高斯的 \(X\)。实验的 Wigner 对角与非对角都按 \(1/\sqrt n\) 缩放，属于 Wigner 模型，但不是对角方差为非对角两倍的标准 GOE 规范。

整体分布收敛不排除极少数离群点。经验谱测度是 \(\mu_n=n^{-1}\sum_{j=1}^n\delta_{\lambda_j}\)。把一个特征值改成 \(n\)，任意有界测试函数的平均值最多改变 \(2\|f\|_\infty/n\)，弱极限不变，最大特征值却发散。因此半圆律本身不保证谱边缘；Bai–Yin 型边缘控制要另核矩条件和矩阵模型。

当 \(y=n/m>1\) 时，MP 分布在 0 的原子质量为 \(1-1/y\)。有限维原因已经可见：\(\operatorname{rank}(X^\top X)\le m<n\)，故至少 \(n-m\) 个零特征值。实验的 \(S\) 没有减样本均值：总体均值为零时它是协方差估计；否则估计的是二阶矩。若改成扣样本均值再除以 \(m-1\) 的无偏样本协方差，秩至多 \(m-1\)，归一化也随之改变。

4. 协方差估计：每个方向上的方差都要准确

令 \(X_1,\ldots,X_m\in\mathbb R^n\) 为独立同分布、中心、各向同性随机向量：

同一向量的坐标可以相关；此处需要的是各行样本独立，以及所有方向统一的亚高斯条件。令 \(\widehat\Sigma=m^{-1}\sum_iX_iX_i^\top\)。固定单位方向 \(u\)，其方差估计误差为

因为 \(\|Z^2\|_{\psi_1}=\|Z\|_{\psi_2}^2\)，且减均值只增加常数倍尺度，\(Y_i\) 是中心亚指数量，\(\|Y_i\|_{\psi_1}\le CK^2\)。Bernstein 不等式给出

对 \(9^n\) 个网点取并集，再用对称二次型引理。令 \(q=n+t^2\)，选择 \(a=C_0K^2(\sqrt{q/m}+q/m)\)；其平方段与线性段都能使指数至少为常数倍的 \(q\)。取足够大的 \(C_0\)，抵消 \(n\log9\) 后得到

要使误差至多 \(\varepsilon\in(0,1]\)、失败概率至多 \(\delta\in(0,1)\)，取 \(t^2=\log(2/\delta)\)。一个充分样本量是

根号项和线性项必须同时检查。将 \(K\) 当作固定常数时才可省略 \(K^4\)；“样本量约等于维数”仅表示常数误差、固定置信度和固定尾部尺度。

这个误差控制所有单位方向上的方差。若 \(\varepsilon<1\)，\(\widehat\Sigma\) 的特征值位于 \([1-\varepsilon,1+\varepsilon]\)，于是可逆，条件数至多 \((1+\varepsilon)/(1-\varepsilon)\)。要进一步保证 PCA 的特征向量准确，还需要总体特征值之间的间隙；方差接近不等于每个主方向可辨识。

5. 四道迁移题：能否自己完成关键推理

6. 下一次遇到算子界时怎么用

先写清要控制的连续方向族；再给出覆盖半径，而不只列出采样数量；然后针对固定方向证明尾界，用网点数量的对数支付并集代价，最后把离散控制送回连续对象。协方差、PCA 和随机嵌入都可复用这条推理链。下一页的 chaining 会处理更一般的方向族，并讨论为什么单一尺度的网可能浪费几何信息。

本页网引理、亚高斯矩阵与协方差证明可对照 Vershynin 的 High-Dimensional Probability 第二版 §4.2、§4.4、§4.7。半圆律与谱边缘的区别可继续阅读 Tao 的 Topics in Random Matrix Theory §2.3–2.4。本页二维覆盖和两个反例均已给出独立推导，实验承担复算与诊断用途。