形式陈述
设 是相互独立理路独立性Statistical independence从概率表理解独立性,区分两两、相互和条件独立,并用可计算反例澄清零协方差与条件均值的限度。的 实对称或复 Hermitian 随机矩阵,其中 。矩阵期望理路期望Expectation · Expected value实值或复值随机变量关于概率测度的 Lebesgue 积分,概括加权平均与总体质量平衡。按各条目的实部、虚部分别积分。假设 ,并存在确定常数 ,使每项的谱范数理路矩阵范数与诱导算子范数Matrix norm · Induced matrix norm · Operator norm of a matrix用诱导范数和常用可计算矩阵范数度量线性映射的放大能力,并区分算子范数、Frobenius 范数与谱半径。几乎处处满足 。定义矩阵方差参数
这里 总是半正定理路正定与半正定矩阵Positive definite matrix · Positive semidefinite matrix · PSD matrix由二次能量严格为正或非负定义的实对称与复 Hermitian 矩阵。,所以 。当 时,对任意 ,矩阵 Bernstein 不等式给出
时事件概率为 ,可直接补上。若 ,则 ;在有限个标准基向量上应用此式,得到每项 几乎处处。因此此时正阈值的尾概率为零,不需要解释公式中的 。
给定 ,令 ,其中 是自然对数。一个方便的置信阈值是
它满足 ,所以范数不超过 的概率至少为 。解二次方程得到的更紧阈值是 ;方便式保留了“方差平方根项加单项幅度项”的结构。
非交换指数矩:明确调用 Lieb 凹性
证明沿用Chernoff 方法理路Chernoff 方法与 Chernoff 界Chernoff method · Chernoff bounds从指数矩与 Markov 不等式推导尾界,给出独立 Bernoulli 和的乘法形式、KL 形式及适用条件。,但矩阵一般不交换,不能把 分成各项指数的乘积。需要的外部定理是 Lieb 凹性定理:对固定 Hermitian 矩阵 ,函数
在正定矩阵锥上是凹函数。这里 、 均由谱定理理路有限维谱定理Finite-dimensional spectral theorem有限维复正规算子存在正交规范特征基;实数情形对应自伴算子。定义。本页调用 Tropp 所述的这一深层引理,不证明 Lieb 定理本身;以下给出从它到 Bernstein 界的全部步骤。
固定 ,记 。指数矩正定,故对数有定义。令
给定 后,括号里除 外的部分是固定 Hermitian 矩阵 。把 Hermitian 矩阵空间看作有限维实向量空间,对 Lieb 凹函数的负值应用Jensen 不等式理路Jensen 不等式Jensen's inequality凸函数作用于平均值不超过函数值的相同加权平均。,再用独立性消去条件期望,得到
这里 ,所以 可积、均值仍在正定锥内;对固定 ,所用连续迹函数也在这个紧区间上有界,Jensen 的可积条件满足。再对已给定的变量取期望,利用条件期望的塔式法则理路条件期望Conditional expectation以信息分组的加权平均建立条件期望直觉,再连接测度定义、最小均方预测、塔式性质和可计算反例。,于是 。从 向下逐项剥离,便有
这一步替代了标量独立和的矩母函数乘法公式,整个过程没有交换矩阵因子。
从逐项幅度得到方差控制
若实数 ,则对 有 ;结合 ,对 得
谱定理把这个标量不等式逐特征值提升为 Loewner 不等式。取期望并用中心化条件,得到
第二步使用 的算子单调性以及标量 的谱版本。前者可由积分表示
和正定矩阵取逆会反转 Loewner 次序得到。求和后有 ,故
这里使用的是 :由Courant–Fischer 极值原理理路Rayleigh 商与 Courant–Fischer 变分原理Courant–Fischer min–max theorem · Rayleigh quotient variational characterization从正交谱展开和子空间维数相交证明每个有序特征值的 min–max 公式,明确 Hermitian 假设与重数。,Loewner 次序逐个控制排序后的特征值,再对它们取指数求和即可。并未使用一般不成立的“矩阵指数在 Loewner 序下算子单调”。
优化参数与合并两侧
设 。由 和Markov 不等式理路Markov 不等式Markov's inequality非负随机变量超过阈值的概率由其期望除以阈值控制。,
时取 ,代入指数得到 。对 重复证明,方差与幅度上界不变。最后利用 Hermitian 矩阵的
及并集界理路并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率,不超过各事件概率之和。得到因子 。这也解释了为何双侧结论要求 ,只有 的单侧假设不足以直接处理 。
例子与边界
为 计算一个完整置信界
设 是Erdős–Rényi 随机图理路Erdős–Rényi 随机图Erdős–Rényi random graph · G(n,p) · G(n,m)在固定标号顶点集上独立采样边或均匀采样固定边数的随机图模型。 的邻接矩阵, 是全 矩阵。对每条候选边 ,令 独立,并定义
则 ,。每个边矩阵只在二维子空间上作用,其特征值为 ,所以可以取 。进一步,
因此 ,而不是候选边数乘以 :每个坐标只出现在 项中。取 、、,逐项代入得
于是以至少 的概率,所有单位向量 同时满足
这是明确可算的充分界,没有声称这个数就是典型误差或最优常数。
适用条件的边界
或 时图是确定的,中心化邻接矩阵恒为零,应使用 的退化结论。 的边数固定,边指示变量不独立,不能直接使用这里的分解套本定理。若矩阵项彼此依赖,需另证适合其依赖结构的矩阵集中界;若只有有限二阶矩而没有幅度上界,也不能凭同一个 得到这里的指数尾界。
时结论回到有界中心化标量和的 Bernstein 界理路有界标量 Bernstein 不等式Scalar Bernstein inequality · Bernstein inequality for bounded random variables在已知中心化幅度与方差预算时控制独立标量和,以初等指数矩证明解释两种偏差尺度,并计算罕见事件均值的充分样本量。;其独立页面不用矩阵或 Lieb 凹性完成标量证明,并比较罕见 Bernoulli 均值的充分样本量。本页的非交换证明与统一方向结论仍保留。一般非对称矩阵则不具备这里的特征值与二次型接口,可通过 Hermitian 扩张处理,但必须重新计算扩张后的维数与方差,不能直接把原矩阵的最大特征值当成谱范数。