常用数学工具

前置

• L-integral

多维 Chebyshev 不等式

定理（加权多维 Chebyshev 不等式）　设 $\mathbf{X}\in {\mathbb{R}}^d$ 是二阶矩有限的随机向量，即

$$\mathbb{E}\Vert \mathbf{X}{\Vert }_2^2<\infty .$$

记

$$\mathbf{\mu }:=\mathbb{E}[\mathbf{X}],\mathbf{\Sigma }:=\mathbb{E}\left[(\mathbf{X}-\mathbf{\mu })(\mathbf{X}-\mathbf{\mu }{)}^{\top }\right].$$

若 $A\in {\mathbb{R}}^{d\times d}$ 是对称半正定矩阵，且 $c>0$，则

$$\mathbb{P}\left((\mathbf{X}-\mathbf{\mu }{)}^{\top }A(\mathbf{X}-\mathbf{\mu })\ge c\right)\le \frac{\mathrm{tr}(A\mathbf{\Sigma })}{c}.$$

二阶矩有限保证 $\mathbf{\mu }$、$\mathbf{\Sigma }$ 以及上式中的期望都存在且有限。

证明　令

$$Y:=(\mathbf{X}-\mathbf{\mu }{)}^{\top }A(\mathbf{X}-\mathbf{\mu }).$$

由 $A⪰0$ 可知 $Y\ge 0$。Markov 不等式与迹的线性性质给出

$$\begin{array}{rl}\mathbb{P}(Y\ge c)& \le \frac{\mathbb{E}[Y]}{c}\\ & =\frac{1}{c}\mathbb{E}\left[\mathrm{tr}\left((\mathbf{X}-\mathbf{\mu }{)}^{\top }A(\mathbf{X}-\mathbf{\mu })\right)\right]\\ & =\frac{1}{c}\mathrm{tr}\left(A\mathbb{E}\left[(\mathbf{X}-\mathbf{\mu })(\mathbf{X}-\mathbf{\mu }{)}^{\top }\right]\right)\\ & =\frac{\mathrm{tr}(A\mathbf{\Sigma })}{c}.\end{array}$$

证毕。

取 $A=I$，并把阈值换成 $c^2$，可得：对任意 $c>0$，

$$\begin{array}{rl}\mathbb{P}\left(\Vert \mathbf{X}-\mathbf{\mu }{\Vert }_2\ge c\right)& =\mathbb{P}\left(\Vert \mathbf{X}-\mathbf{\mu }{\Vert }_2^2\ge c^2\right)\\ & \le \frac{\mathrm{tr}(\mathbf{\Sigma })}{c^2}.\end{array}$$

特别地，若

$$\mathbf{X}\sim \mathcal{N}(\mathbf{\mu },{\sigma }^2{I}_d),{\sigma }^2>0,$$

则 $\mathbf{\Sigma }={\sigma }^2{I}_d$ 且 $\mathrm{tr}(\mathbf{\Sigma })=d{\sigma }^2$，所以对每个 $c>0$，

$$\mathbb{P}\left(\Vert \mathbf{X}-\mathbf{\mu }{\Vert }_2\ge c\right)\le \frac{d{\sigma }^2}{c^2}.$$

高斯随机向量具有所有有限阶矩，因而上述可积性条件自动满足。

期望与最小二乘

定理（期望是最佳常数最小二乘预测）　设 $f(\mathbf{X})$ 是 ${\mathbb{R}}^m$ 值随机向量，并满足

$$\mathbb{E}\Vert f(\mathbf{X}){\Vert }_2^2<\infty .$$

则对确定性向量 $\mathbf{y}\in {\mathbb{R}}^m$，

$$\underset{\mathbf{y}\in {\mathbb{R}}^m}{\mathrm{argmin}}\mathbb{E}\left[\Vert \mathbf{y}-f(\mathbf{X}){\Vert }_2^2\right]=\left\{\mathbb{E}[f(\mathbf{X})]\right\}.$$

二阶矩条件保证目标函数有限，并由 Cauchy–Schwarz 不等式推出 $\mathbb{E}\Vert f(\mathbf{X}){\Vert }_2<\infty$，所以期望存在。

证明　令 $\mathbf{Z}=f(\mathbf{X})$。在误差中加上并减去 $\mathbb{E}[\mathbf{Z}]$：

$$\mathbf{y}-\mathbf{Z}=(\mathbf{y}-\mathbb{E}[\mathbf{Z}])+(\mathbb{E}[\mathbf{Z}]-\mathbf{Z}).$$

利用

$$\Vert \mathbf{a}+\mathbf{b}{\Vert }_2^2=\Vert \mathbf{a}{\Vert }_2^2+2⟨\mathbf{a},\mathbf{b}⟩+\Vert \mathbf{b}{\Vert }_2^2$$

展开并取期望。交叉项为

$$\begin{array}{rl}& 2\mathbb{E}\left[⟨\mathbf{y}-\mathbb{E}[\mathbf{Z}],\mathbb{E}[\mathbf{Z}]-\mathbf{Z}⟩\right]\\ & =2⟨\mathbf{y}-\mathbb{E}[\mathbf{Z}],\mathbb{E}\left[\mathbb{E}[\mathbf{Z}]-\mathbf{Z}\right]⟩=0.\end{array}$$

于是得到偏差—方差分解

$$\mathbb{E}\Vert \mathbf{y}-\mathbf{Z}{\Vert }_2^2=\Vert \mathbf{y}-\mathbb{E}[\mathbf{Z}]{\Vert }_2^2+\mathbb{E}\Vert \mathbf{Z}-\mathbb{E}[\mathbf{Z}]{\Vert }_2^2.$$

第二项与 $\mathbf{y}$ 无关，第一项非负且仅在

$$\mathbf{y}=\mathbb{E}[\mathbf{Z}]=\mathbb{E}[f(\mathbf{X})]$$

时为零，因此该最小化解存在且唯一。证毕。

二次型与高斯分布

设 $A\in {\mathbb{R}}^{D\times D}$ 为对称正定矩阵，$\mathbf{b}\in {\mathbb{R}}^D$，$c\in \mathbb{R}$。考虑未归一化核

$$\tilde{p}(\mathbf{x}):=\exp \left[-\frac{1}{2}\left({\mathbf{x}}^{\top }A\mathbf{x}-2{\mathbf{b}}^{\top }\mathbf{x}+c\right)\right].$$

$A\succ 0$ 保证该核在 ${\mathbb{R}}^D$ 上可积。定义

$$\mathbf{\Sigma }:=A^{-1},\mathbf{\mu }:=A^{-1}\mathbf{b}.$$

这里始终用 $\mathbf{\Sigma }$ 表示协方差矩阵；相应的精度矩阵为

$${\mathbf{\Sigma }}^{-1}=A.$$

$D$ 维高斯 $\mathcal{N}(\mathbf{\mu },\mathbf{\Sigma })$ 的密度为

$$p(\mathbf{x})=\frac{1}{(2\pi {)}^{D/2}\det (\mathbf{\Sigma }{)}^{1/2}}\exp \left[-\frac{1}{2}(\mathbf{x}-\mathbf{\mu }{)}^{\top }{\mathbf{\Sigma }}^{-1}(\mathbf{x}-\mathbf{\mu })\right].$$

展开其指数中的二次型：

$$\begin{array}{rl}(\mathbf{x}-\mathbf{\mu }{)}^{\top }{\mathbf{\Sigma }}^{-1}(\mathbf{x}-\mathbf{\mu })& ={\mathbf{x}}^{\top }{\mathbf{\Sigma }}^{-1}\mathbf{x}-{\mathbf{x}}^{\top }{\mathbf{\Sigma }}^{-1}\mathbf{\mu }\\ & -{\mathbf{\mu }}^{\top }{\mathbf{\Sigma }}^{-1}\mathbf{x}+{\mathbf{\mu }}^{\top }{\mathbf{\Sigma }}^{-1}\mathbf{\mu }.\end{array}$$

因为 ${\mathbf{\Sigma }}^{-1}$ 对称，中间两项都是标量且相等：

$${\mathbf{x}}^{\top }{\mathbf{\Sigma }}^{-1}\mathbf{\mu }={\mathbf{\mu }}^{\top }{\mathbf{\Sigma }}^{-1}\mathbf{x}.$$

故指数项可以写成

$$-\frac{1}{2}\left[{\mathbf{x}}^{\top }{\mathbf{\Sigma }}^{-1}\mathbf{x}-2({\mathbf{\Sigma }}^{-1}\mathbf{\mu }{)}^{\top }\mathbf{x}+{\mathbf{\mu }}^{\top }{\mathbf{\Sigma }}^{-1}\mathbf{\mu }\right].$$

与一般形式

$$-\frac{1}{2}\left[{\mathbf{x}}^{\top }A\mathbf{x}-2{\mathbf{b}}^{\top }\mathbf{x}+c\right]$$

逐项比较可得

$$A={\mathbf{\Sigma }}^{-1},\mathbf{\Sigma }=A^{-1},\mathbf{b}={\mathbf{\Sigma }}^{-1}\mathbf{\mu },\mathbf{\mu }=\mathbf{\Sigma }\mathbf{b}=A^{-1}\mathbf{b}.$$

也可以直接配方：

$${\mathbf{x}}^{\top }A\mathbf{x}-2{\mathbf{b}}^{\top }\mathbf{x}+c=(\mathbf{x}-\mathbf{\mu }{)}^{\top }A(\mathbf{x}-\mathbf{\mu })+c-{\mathbf{b}}^{\top }{A}^{-1}\mathbf{b}.$$

最后两项与 $\mathbf{x}$ 无关，只改变归一化常数，不改变均值与协方差。因此将 $\tilde{p}$ 归一化后，

$$\mathbf{X}\sim \mathcal{N}(A^{-1}\mathbf{b},A^{-1}).$$

若 $A$ 不是正定矩阵，该核一般不能在整个 ${\mathbb{R}}^D$ 上归一化为非退化高斯密度。

Hutchinson 迹估计与随机投影

高维情形下，$\mathrm{tr}(A)$ 与 $\Vert \mathbf{s}{\Vert }_2^2$ 可以用随机方向上的一维投影作无偏估计，从而避免显式构造完整的 $d\times d$ 矩阵或计算完整向量内积。

设随机向量 $\mathbf{u}\in {\mathbb{R}}^d$ 满足

$$\mathbb{E}[\mathbf{u}{\mathbf{u}}^{\top }]=I_d.$$

这一各向同性二阶矩条件蕴含

$$\mathbb{E}\Vert \mathbf{u}{\Vert }_2^2=d<\infty .$$

常见选择包括：

• 各分量独立同分布的 Rademacher 向量，即 $u_i\in \{-1,+1\}$ 且两个取值概率均为 $1/2$；
• $\mathbf{u}\sim \mathcal{N}(0,I_d)$。

随机矩阵的 Hutchinson 迹估计

定理　设随机矩阵 $A\in {\mathbb{R}}^{d\times d}$ 满足

$$\mathbb{E}\Vert A{\Vert }_{\mathrm{F}}<\infty ,$$

且 $\mathbf{u}$ 与 $A$ 独立、$\mathbb{E}[\mathbf{u}{\mathbf{u}}^{\top }]=I_d$。则 ${\mathbf{u}}^{\top }A\mathbf{u}$ 可积，并且

$$\mathbb{E}\left[{\mathbf{u}}^{\top }A\mathbf{u}\mid A\right]=\mathrm{tr}(A)\text{几乎处处}.$$

因此

$$\mathbb{E}[{\mathbf{u}}^{\top }A\mathbf{u}]=\mathbb{E}[\mathrm{tr}(A)].$$

当 $A$ 是确定矩阵时，上式退化为

$$\mathrm{tr}(A)={\mathbb{E}}_{\mathbf{u}}[{\mathbf{u}}^{\top }A\mathbf{u}].$$

$A$ 不必对称；其反对称部分对二次型和迹都没有贡献。

证明　由

$$|{\mathbf{u}}^{\top }A\mathbf{u}|\le \Vert A{\Vert }_{\mathrm{F}}\Vert \mathbf{u}{\Vert }_2^2$$

以及独立性，

$$\mathbb{E}|{\mathbf{u}}^{\top }A\mathbf{u}|\le \mathbb{E}\Vert A{\Vert }_{\mathrm{F}}\mathbb{E}\Vert \mathbf{u}{\Vert }_2^2<\infty .$$

又因为标量等于自身的迹，且迹满足循环性质，

$${\mathbf{u}}^{\top }A\mathbf{u}=\mathrm{tr}({\mathbf{u}}^{\top }A\mathbf{u})=\mathrm{tr}(\mathbf{u}{\mathbf{u}}^{\top }A).$$

对 $A$ 取条件期望。独立性给出

$$\mathbb{E}[\mathbf{u}{\mathbf{u}}^{\top }\mid A]=\mathbb{E}[\mathbf{u}{\mathbf{u}}^{\top }]=I_d,$$

所以

$$\begin{array}{rl}\mathbb{E}[{\mathbf{u}}^{\top }A\mathbf{u}\mid A]& =\mathrm{tr}\left(\mathbb{E}[\mathbf{u}{\mathbf{u}}^{\top }\mid A]A\right)\\ & =\mathrm{tr}(I_{d}A)=\mathrm{tr}(A).\end{array}$$

再使用全期望公式即可得到无条件结论。证毕。

随机投影估计平方范数

定理　设 $\mathbf{S}\in {\mathbb{R}}^d$ 满足

$$\mathbb{E}\Vert \mathbf{S}{\Vert }_2^2<\infty ,$$

且 $\mathbf{u}$ 与 $\mathbf{S}$ 独立、$\mathbb{E}[\mathbf{u}{\mathbf{u}}^{\top }]=I_d$。则 $({\mathbf{u}}^{\top }\mathbf{S}{)}^2$ 可积，并且

$$\mathbb{E}\left[({\mathbf{u}}^{\top }\mathbf{S}{)}^2\mid \mathbf{S}\right]=\Vert \mathbf{S}{\Vert }_2^2\text{几乎处处}.$$

因此

$$\mathbb{E}[({\mathbf{u}}^{\top }\mathbf{S}{)}^2]=\mathbb{E}\Vert \mathbf{S}{\Vert }_2^2.$$

特别地，对任意固定 $\mathbf{s}\in {\mathbb{R}}^d$，

$${\mathbb{E}}_{\mathbf{u}}\left[({\mathbf{u}}^{\top }\mathbf{s}{)}^2\right]=\Vert \mathbf{s}{\Vert }_2^2.$$

证明　由 Cauchy–Schwarz 不等式与独立性，

$$\mathbb{E}[({\mathbf{u}}^{\top }\mathbf{S}{)}^2]\le \mathbb{E}\left[\Vert \mathbf{u}{\Vert }_2^2\Vert \mathbf{S}{\Vert }_2^2\right]=\mathbb{E}\Vert \mathbf{u}{\Vert }_2^2\mathbb{E}\Vert \mathbf{S}{\Vert }_2^2<\infty .$$

并且

$$\begin{array}{rl}\mathbb{E}\left[({\mathbf{u}}^{\top }\mathbf{S}{)}^2\mid \mathbf{S}\right]& =\mathbb{E}\left[{\mathbf{S}}^{\top }\mathbf{u}{\mathbf{u}}^{\top }\mathbf{S}\mid \mathbf{S}\right]\\ & ={\mathbf{S}}^{\top }\mathbb{E}[\mathbf{u}{\mathbf{u}}^{\top }\mid \mathbf{S}]\mathbf{S}\\ & ={\mathbf{S}}^{\top }{I}_d\mathbf{S}=\Vert \mathbf{S}{\Vert }_2^2.\end{array}$$

对固定 $\mathbf{s}$，也可按分量展开并使用

$$\mathbb{E}[u_i{u}_j]={\delta }_{ij}$$

得到 ${\sum }_{i=1}^d{s}_i^2$。证毕。

使用 $M$ 个独立探针并取平均，便得到常用的无偏 Monte Carlo 估计：

$$\widehat{\mathrm{tr}}(A)=\frac{1}{M}\sum _{m=1}^M{\mathbf{u}}_m^{\top }A{\mathbf{u}}_m,\widehat{\Vert \mathbf{s}{\Vert }_2^2}=\frac{1}{M}\sum _{m=1}^M({\mathbf{u}}_m^{\top }\mathbf{s}{)}^2,$$

前提是以上矩条件和独立性条件成立。