矩阵 Bernstein 不等式

形式陈述 ​

设 $X_1,\dots ,X_m$ 是相互独立公理库独立性Statistical independence从概率表理解独立性，区分两两、相互和条件独立，并用可计算反例澄清零协方差与条件均值的限度。的 $d\times d$ 实对称或复 Hermitian 随机矩阵，其中 $d\ge 1$。假设 $\mathbb{E}{X}_k=0$，并存在确定常数 $R>0$，使每项的谱范数公理库矩阵范数与诱导算子范数Matrix norm · Induced matrix norm · Operator norm of a matrix用诱导范数和常用可计算矩阵范数度量线性映射的放大能力，并区分算子范数、Frobenius 范数与谱半径。几乎处处满足 $\Vert X_k{\Vert }_2\le R$。定义矩阵方差参数

$$V=\sum _{k=1}^m\mathbb{E}{X}_k^2,v=\Vert V{\Vert }_2.$$

这里 $X_k^2$ 总是半正定公理库正定与半正定矩阵Positive definite matrix · Positive semidefinite matrix · PSD matrix由二次能量严格为正或非负定义的实对称与复 Hermitian 矩阵。，所以 $V⪰0$。当 $v>0$ 时，对任意 $t>0$，矩阵 Bernstein 不等式给出

$$\text{Pr}({\Vert \sum _k{X}_k\Vert }_2\ge t)\le min\{1,2d\exp (-\frac{t^2}{2(v+Rt/3)})\}.$$

$t=0$ 时事件概率为 $1$，可直接补上。若 $v=0$，则 $\sum _k\mathbb{E}\Vert X_{k}u{\Vert }_2^2=u^{\ast }Vu=0$；在有限个标准基向量上应用此式，得到每项 $X_k=0$ 几乎处处。因此此时正阈值的尾概率为零，不需要解释公式中的 $0/0$。

给定 $0<\delta <1$，令 $\ell =\log \left(2d/\delta \right)$，其中 $\log$ 是自然对数。一个方便的置信阈值是

$$t_{\delta }=\sqrt{2v\ell }+\frac{2R\ell }{3}.$$

它满足 $t_{\delta }^2\ge 2\ell (v+R{t}_{\delta }/3)$，所以范数不超过 $t_{\delta }$ 的概率至少为 $1-\delta$。解二次方程得到的更紧阈值是 $R\ell /3+\sqrt{2v\ell +(R\ell /3{)}^2}$；方便式保留了“方差平方根项加单项幅度项”的结构。

非交换指数矩：明确调用 Lieb 凹性 ​

证明沿用Chernoff 方法公理库Chernoff 方法与 Chernoff 界Chernoff method · Chernoff bounds从指数矩与 Markov 不等式推导尾界，给出独立 Bernoulli 和的乘法形式、KL 形式及适用条件。，但矩阵一般不交换，不能把 $\exp \left(\theta \sum _k{X}_k\right)$ 分成各项指数的乘积。需要的外部定理是 Lieb 凹性定理：对固定 Hermitian 矩阵 $H$，函数

$$A⟼\mathrm{tr}\exp (H+\log A)$$

在正定矩阵锥上是凹函数。这里 $\exp$、$\log$ 均由谱定理公理库有限维谱定理Finite-dimensional spectral theorem有限维实对称或复自伴算子存在正交规范特征向量基。定义。本页调用 Tropp 所述的这一深层引理，不证明 Lieb 定理本身；以下给出从它到 Bernstein 界的全部步骤。

固定 $\theta >0$，记 $K_k=\log \mathbb{E}{e}^{\theta X_k}$。指数矩正定，故对数有定义。令

$$T_j=\mathbb{E}\mathrm{tr}\exp (\theta \sum _{k\le j}{X}_k+\sum _{k>j}{K}_k),0\le j\le m.$$

给定 $X_1,\dots ,X_{j-1}$ 后，括号里除 $\theta X_j$ 外的部分是固定 Hermitian 矩阵 $H$。将 Lieb 凹性与条件 Jensen 用于 $A=e^{\theta X_j}$，再用独立性消去条件期望，得到

$${\mathbb{E}}_{X_j}\mathrm{tr}\exp (H+\theta X_j)\le \mathrm{tr}\exp (H+\log \mathbb{E}{e}^{\theta X_j}).$$

于是 $T_j\le T_{j-1}$。从 $j=m$ 向下逐项剥离，便有

$$\mathbb{E}\mathrm{tr}{e}^{\theta \sum _k{X}_k}\le \mathrm{tr}\exp (\sum _k\log \mathbb{E}{e}^{\theta X_k}).$$

这一步替代了标量独立和的矩母函数乘法公式，整个过程没有交换矩阵因子。

从逐项幅度得到方差控制 ​

若实数 $|x|\le R$，则对 $j\ge 2$ 有 $x^j\le R^{j-2}{x}^2$；结合 $j!\ge 2\cdot 3^{j-2}$，对 $0<\theta <3/R$ 得

$$e^{\theta x}\le 1+\theta x+g(\theta )x^2,g(\theta )=\frac{{\theta }^2}{2(1-\theta R/3)}.$$

谱定理把这个标量不等式逐特征值提升为 Loewner 不等式。取期望并用中心化条件，得到

$$\mathbb{E}{e}^{\theta X_k}⪯I+g(\theta )\mathbb{E}{X}_k^2,\log \mathbb{E}{e}^{\theta X_k}⪯g(\theta )\mathbb{E}{X}_k^2.$$

第二步使用 $\log$ 的算子单调性以及标量 $\log (1+s)\le s$ 的谱版本。前者可由积分表示

$$\log A={\int }_0^{\mathrm{\infty }}(\frac{1}{1+s}I-(A+sI{)}^{-1})ds$$

和正定矩阵取逆会反转 Loewner 次序得到。求和后有 $\sum _k{K}_k⪯g(\theta )V⪯g(\theta )vI$，故

$$\mathbb{E}\mathrm{tr}{e}^{\theta \sum _k{X}_k}\le d{e}^{g(\theta )v}.$$

这里使用的是 $A⪯B\Rightarrow \mathrm{tr}{e}^A\le \mathrm{tr}{e}^B$：Loewner 次序逐个控制排序后的特征值，再对它们取指数求和即可。并未使用一般不成立的“矩阵指数在 Loewner 序下算子单调”。

优化参数与合并两侧 ​

设 $S=\sum _k{X}_k$。由 $e^{\theta {\lambda }_{max}(S)}\le \mathrm{tr}{e}^{\theta S}$ 和Markov 不等式公理库Markov 不等式Markov's inequality非负随机变量超过阈值的概率由其期望除以阈值控制。，

$$\text{Pr}({\lambda }_{max}(S)\ge t)\le e^{-\theta t}\mathbb{E}\mathrm{tr}{e}^{\theta S}\le d\exp (-\theta t+g(\theta )v).$$

$v,t>0$ 时取 $\theta =t/(v+Rt/3)<3/R$，代入指数得到 $-t^2/[2(v+Rt/3)]$。对 $-X_k$ 重复证明，方差与幅度上界不变。最后利用 Hermitian 矩阵的

$$\Vert S{\Vert }_2=max\{{\lambda }_{max}(S),{\lambda }_{max}(-S)\}$$

及并集界得到因子 $2d$。这也解释了为何双侧结论要求 $\Vert X_k{\Vert }_2\le R$，只有 ${\lambda }_{max}(X_k)\le R$ 的单侧假设不足以直接处理 $-X_k$。

直觉

对每个固定单位向量 $u$，$u^{\ast }Su$ 都是一个标量随机和。矩阵范数却要求一次抽样后，对所有单位向量同时控制 $|u^{\ast }Su|$。分别对固定方向应用标量界，不能直接跨过这个量词变化。迹指数把全部特征方向装进一个非负标量中，付出的代价是尾界前面的维数因子；Lieb 凹性则让独立性在非交换情形下仍能逐项发挥作用。

$R$ 控制一次随机扰动能有多大，$v$ 控制这些扰动在最不利方向上累积的平方幅度。小偏差区间由 $t^2/v$ 决定，较大偏差逐渐由 $t/R$ 决定。矩阵方差是“先平方、取期望、求和，再量范数”，用 $\sum _k\mathbb{E}\Vert X_k{\Vert }_2^2$ 替代它虽可给上界，却可能丢掉不同项分布在不同方向上的结构。

例子与边界

为 $G(1000,0.1)$ 计算一个完整置信界 ​

设 $A$ 是Erdős–Rényi 随机图公理库Erdős–Rényi 随机图Erdős–Rényi random graph · G(n,p) · G(n,m)在固定标号顶点集上独立采样边或均匀采样固定边数的随机图模型。 $G(n,p)$ 的邻接矩阵，$J$ 是全 $1$ 矩阵。对每条候选边 $i<j$，令 ${\xi }_{ij}\sim \mathrm{Bernoulli}(p)$ 独立，并定义

$$X_{ij}=({\xi }_{ij}-p)(e_i{e}_j^{\mathsf{T}}+e_j{e}_i^{\mathsf{T}}).$$

则 $A-\mathbb{E}A=\sum _{i<j}{X}_{ij}$，$\mathbb{E}A=p(J-I)$。每个边矩阵只在二维子空间上作用，其特征值为 $\pm ({\xi }_{ij}-p)$，所以可以取 $R=1$。进一步，

$$X_{ij}^2=({\xi }_{ij}-p{)}^2(e_i{e}_i^{\mathsf{T}}+e_j{e}_j^{\mathsf{T}}),\sum _{i<j}\mathbb{E}{X}_{ij}^2=(n-1)p(1-p)I.$$

因此 $v=(n-1)p(1-p)$，而不是候选边数乘以 $p(1-p)$：每个坐标只出现在 $n-1$ 项中。取 $n=1000$、$p=0.1$、$\delta =0.01$，逐项代入得

$$v=89.91,\ell =\log \left(200000\right)\approx 12.20607265,$$$$t_{\delta }=\sqrt{2\cdot 89.91\cdot \ell }+\frac{2\ell }{3}\approx 54.98709877.$$

于是以至少 $0.99$ 的概率，所有单位向量 $x\in {\mathbb{R}}^{1000}$ 同时满足

$$|x^{\mathsf{T}}(A-0.1(J-I))x|\le 54.98710.$$

这是明确可算的充分界，没有声称这个数就是典型误差或最优常数。

适用条件的边界 ​

$p=0$ 或 $p=1$ 时图是确定的，中心化邻接矩阵恒为零，应使用 $v=0$ 的退化结论。$G(n,m)$ 的边数固定，边指示变量不独立，不能直接使用这里的分解套本定理。若矩阵项彼此依赖，需另证适合其依赖结构的矩阵集中界；若只有有限二阶矩而没有幅度上界，也不能凭同一个 $v$ 得到这里的指数尾界。

$d=1$ 时结论回到有界中心化标量和的 Bernstein 界。一般非对称矩阵则不具备这里的特征值与二次型接口，可通过 Hermitian 扩张处理，但必须重新计算扩张后的维数与方差，不能直接把原矩阵的最大特征值当成谱范数。

推论与应用

谱稀疏化公理库谱稀疏化Spectral sparsifier · Spectral graph sparsification用少量重加权边在全部顶点向量方向上近似原图 Laplacian 二次型，并由有效电阻采样与矩阵集中给出近线性边数。把每条边的 Laplacian 贡献归一化到原图的像空间，按有效电阻设置采样概率，使中心化单项满足 $R\le 1/a$、总方差满足 $v\le 1/a$。将这里的 $t$ 换成相对误差 $\epsilon$，就把抽样参数 $a$ 转成同时控制全部图能量方向的保证。该应用还需处理 Laplacian 的核；矩阵尾界本身不会替代这一步。

随机协方差估计、随机线性代数与图的邻接谱分析也遵循同一计算顺序：写成独立中心化项，计算平方矩阵之和，确定幅度，再解失败概率。真正影响样本量的常常是能否保留方差矩阵的方向结构，而不是最后代入尾界的代数运算。

参考资料

• Joel A. Tropp, User-Friendly Tail Bounds for Sums of Random Matrices，2011-06-15 修订预印本，§3.4–3.6（Theorem 3.2 的 Lieb 凹性与迹指数方法）、Theorem 6.1(ii)、Lemma 6.7；上述双侧界由对 $\pm X_k$ 的两次单侧应用得到。
• Rasmus Kyng, Lecture 8: Matrix Concentration and Spectral Sparsification，ETH Zürich, 2020，§1.1–1.4 与 §2；提供矩阵集中到图采样的教学路线，其较松尾界不用于本页 $1/3$ 常数的依据。