证明思路

用 $\varepsilon$-$\delta$ 证明一致连续，用线段积分证明梯度上界推出 Lipschitz。

完整证明

(a) 若 $d_Y(f(u),f(v))\le Ld_X(u,v)$，给定 $\varepsilon>0$，取 $\delta=\varepsilon/L$ 即得一致连续；$L=0$ 时函数常值。

(b) 对 $x,y\in\mathbb R^n$，由微积分基本定理，

取绝对值并用 Cauchy-Schwarz，得

(c) $f(x)=\sqrt{|x|}$ 在 $[-1,1]$ 上一致连续但不是 Lipschitz，因为 $|f(h)-f(0)|/|h|=1/\sqrt{|h|}\to\infty$。(d) $f(x)=|x|$ Lipschitz，常数为 $1$，但在 $0$ 不可微。

证明思路

上界用 Cauchy-Schwarz 或算子范数定义；下界取达到或逼近上确界的方向。

完整证明

(a) $|\langle x-y,\theta\rangle|\le\|\theta\|_2\|x-y\|_2$，取 $x-y$ 平行于 $\theta$ 得等号，所以 Lipschitz 范数为 $\|\theta\|_2$。(b) $\|Ax-Ay\|_2\le\|A\|\|x-y\|_2$，而算子范数定义保证该常数最小。(c) 由三角不等式，$|\|x\|-\|y\||\le\|x-y\|$。若 $\|z\|\le L\|z\|_2$ 对所有 $z$ 成立，则 $f$ 是 $L$-Lipschitz；反过来取 $y=0$，任何 Lipschitz 常数 $L$ 都必须满足 $\|x\|\le L\|x\|_2$。

证明思路

先反证 $A_s$ 的测度超过 $1/2$；再对 $A_s$ 应用 Lemma 5.1.6。

完整证明

(a) 反设 $\sigma(A_s)\le1/2$，令 $B=(A_s)^c$，则 $\sigma(B)\ge1/2$。由 Lemma 5.1.6，$\sigma(B_s)\ge1-2e^{-cs^2}$。但 $B_s\cap A=\varnothing$，否则 $A$ 中某点到 $B$ 距离至多 $s$，与 $B\subset(A_s)^c$ 矛盾。因此 $\sigma(A)\le2e^{-cs^2}$，矛盾。

(b) 由 (a)，$\sigma(A_s)>1/2$。对 $A_s$ 应用 Lemma 5.1.6，得 $\sigma((A_s)_t)\ge1-2e^{-ct^2}$。且 $(A_s)_t\subset A_{s+t}\subset A_{2t}$，因为 $t\ge s$。结论成立。

证明思路

比较弧长距离和 chordal Euclidean 距离。

完整证明

单位球面上两点夹角为 $\theta\in[0,\pi]$ 时，geodesic 距离为 $\theta$，Euclidean 距离为 $2\sin(\theta/2)$。有 $\theta\le(\pi/2)2\sin(\theta/2)$。因此若 $f$ 关于 geodesic 距离 Lipschitz 常数为 $L$，则关于 Euclidean 距离 Lipschitz 常数至多 $(\pi/2)L$。把 Theorem 5.1.3 用于 Euclidean 距离即可，常数吸收 $\pi/2$。

证明思路

令 $Y=\sqrt n X$，把单位球面函数转成半径 $\sqrt n$ 球面函数。

完整证明

设 $X\sim\operatorname{Unif}(S^{n-1})$，令 $Y=\sqrt n X$，则 $Y\sim\operatorname{Unif}(\sqrt nS^{n-1})$。定义 $g(y)=f(y/\sqrt n)$。则

由 Theorem 5.1.3，

尾界形式由 $\psi_2$ 范数定义推出。

证明思路

用 $\psi_2$ 控制一阶矩，证明均值和中位数距离被集中尺度控制。

完整证明

设 $K=\|Z-M\|_{\psi_2}$。则 $\mathbb E|Z-M|\le CK$，所以 $|\mathbb EZ-M|\le CK$。于是

反过来设 $L=\|Z-\mathbb EZ\|_{\psi_2}$。若 $a=|M-\mathbb EZ|$，中位数性质给出 $\mathbb P\{|Z-\mathbb EZ|\ge a\}\ge1/2$，从次高斯尾界可得 $a\le CL$。因此

证明思路

取距离函数 $f(x)=d(x,A)$。它是 1-Lipschitz，且中位数为 $0$。

完整证明

令 $f(x)=d(x,A)$。则 $f$ 是 1-Lipschitz，并且因为 $\sigma(A)\ge1/2$，$0$ 是 $f(X)$ 的一个中位数。由假设和 Exercise 5.6，$\|f(X)\|_{\psi_2}\le CK$。于是

因此 $\sigma(A_t)\ge1-2\exp(-ct^2/K^2)$。

证明思路

完全仿照球面：用 half-space 作为等周最小化对象，先得 blow-up，再对中位数 sublevel set 应用。

完整证明

Gaussian 等周不等式说明，在给定 Gaussian measure 下，half-space 的邻域测度最小。若 $\gamma_n(A)\ge1/2$，与某个 measure 为 $1/2$ 的 half-space 比较，并用一维 Gaussian 尾界，得

对 Lipschitz 函数 $f$ 取中位数 $M$ 和集合 $A=\{f\le M\}$。若 $\|f\|_{\mathrm{Lip}}=1$，则 $X\in A_t$ 推出 $f(X)\le M+t$。对 $f$ 和 $-f$ 分别处理，再用 Exercise 5.6 把中位数换成均值，得到 Theorem 5.2.3。

证明思路

最大值函数是 Lipschitz 的；联合正态向量可写成标准 Gaussian 的线性像。

完整证明

(a) 函数 $g(x)=\max_i x_i$ 满足

故 $1$-Lipschitz。对 $X\sim N(0,I_n)$ 用 Gaussian concentration 得结论。

(b) 联合正态向量可写为 $X=BG$，其中 $G\sim N(0,I_r)$。令 $b_i$ 是 $B$ 的第 $i$ 行，则 $\operatorname{Var}(X_i)=\|b_i\|_2^2$。函数 $h(g)=\max_i\langle b_i,g\rangle$ 的 Lipschitz 常数至多 $\max_i\|b_i\|_2$。用 Gaussian concentration 得结论。

证明思路

用 subgaussian moment bound 控制 $\|Z-\mathbb EZ\|_{L^p}$，再用反三角不等式控制两个中心的距离。

完整证明

令 $\mu=\mathbb EZ$，$K=\|Z-\mu\|_{\psi_2}$。次高斯矩估计给出 $\|Z-\mu\|_{L^p}\le C\sqrt pK$。由反三角不等式，

由于 $\mu\ge0$，$|\mu|=\mu$。因此

证明思路

一维用分布函数变换；多维用独立性。

完整证明

若 $U=\Phi(Z)$ 且 $Z\sim N(0,1)$，则对 $u\in[0,1]$，

所以 $U\sim\operatorname{Unif}[0,1]$。因为 $Z_1,\ldots,Z_n$ 独立，坐标变换后 $\Phi(Z_i)$ 仍独立，故向量均匀分布在 $[0,1]^n$。

证明思路

把 Gaussian 坐标用 CDF 推到 uniform 坐标，并检查推送映射 Lipschitz。

完整证明

令 $\phi(z)=(\Phi(z_1),\ldots,\Phi(z_n))$。由 Exercise 5.11，$\phi(Z)\sim\operatorname{Unif}([0,1]^n)$。又 $\Phi'(t)\le1/\sqrt{2\pi}$，所以

若 $f$ 在 cube 上 Lipschitz，则 $f\circ\phi$ 在 $\mathbb R^n$ 上 Lipschitz，常数至多 $C\|f\|_{\mathrm{Lip}}$。对 $f(\phi(Z))$ 应用 Gaussian concentration 即得结论。

证明思路

使用径向传输：Gaussian 的方向本来均匀，只需把半径分布变成 ball 的均匀半径分布。

完整证明

把 $Z\sim N(0,I_n)$ 写成 $Z=RU$，其中 $U\sim\operatorname{Unif}(S^{n-1})$，$R=\|Z\|_2$，且二者独立。令 $F$ 为 $R$ 的分布函数。定义

因为 ball $\sqrt nB_2^n$ 的均匀半径分布满足 $\mathbb P\{\rho\le r\}=(r/\sqrt n)^n$，所以 $\phi(Z)$ 均匀分布在 $\sqrt nB_2^n$ 上。径向函数 $r\mapsto\sqrt nF(r)^{1/n}$ 是绝对常数 Lipschitz，并且不超过常数倍 $r$；结合径向映射的标准 Lipschitz 判别，$\phi$ 的 Lipschitz 范数被绝对常数控制。于是对 $f\circ\phi$ 应用 Gaussian concentration，得到 ball 上的集中。

证明思路

固定差向量后，$Az$ 的坐标是独立次高斯，Theorem 3.1.1 控制长度；再 union bound。

完整证明

固定 $z$。由于 rows $A_i$ 各向同性，$\mathbb E\langle A_i,z\rangle^2=\|z\|_2^2$；次高斯性保证 $\langle A_i,z\rangle$ 是次高斯。由 norm concentration，

对 $\mathcal X-\mathcal X$ 中至多 $N^2$ 个差向量做 union bound，若 $m\gtrsim\varepsilon^{-2}\log N$，得到 JL 结论。若 $A$ entries 为独立 Rademacher $\pm1$，rows 均值零、各向同性且次高斯，所以是特例。

证明思路

用 packing 体积比较限制低维空间中可容纳的分离点数量。

完整证明

(a) 以 $z_i$ 为中心、半径 $1/2$ 的球两两不交。又所有中心都在 $B(z_1,2)$ 中，所以这些小球都包含在 $B(z_1,5/2)$ 中。体积比较得

即 $N\le5^n$。

(b) 取 $x_i=e_i\in\mathbb R^N$。若存在 $T$ 满足题中距离保持，则 $z_i=T(e_i)/(0.99\sqrt2)$ 在 $\mathbb R^n$ 中满足 $1<\|z_i-z_j\|_2\le2$。由 (a)，$N\le5^n$。当 $n<\frac12\log N$ 时，$5^n<N$，矛盾。因此不存在这样的 $T$。

证明思路

对谱分解逐特征值运算。

完整证明

设 $X=\sum_i\lambda_i u_iu_i^{\mathsf T}$。则 $X^k=\sum_i\lambda_i^k u_iu_i^{\mathsf T}$。因此对多项式 $f(x)=\sum_{k=0}^pa_kx^k$，

对收敛幂级数同理，矩阵级数在 Frobenius 范数中逐特征值绝对收敛，从而也在算子范数中收敛。取 $f(x)=e^x$ 即得 $e^X=I+X+X^2/2!+\cdots$。

证明思路

交换对称矩阵可同时正交对角化；反例用 $f(t)=t^2$。

完整证明

(a) 若 $X,Y$ 交换且对称，则可同时正交对角化：$X=U\operatorname{diag}(x_i)U^{\mathsf T}$，$Y=U\operatorname{diag}(y_i)U^{\mathsf T}$。$X\preceq Y$ 等价于 $x_i\le y_i$。若 $f$ 弱增，则 $f(x_i)\le f(y_i)$，故 $f(X)\preceq f(Y)$。

(b) 令

则 $C\succeq0$，所以 $X\preceq Y$，且 $X,Y\succeq0$。函数 $f(t)=t^2$ 在 $[0,\infty)$ 上弱增。但

行列式为 $8-9=-1$，不是半正定。因此 $X^2\preceq Y^2$ 失败。

证明思路

逆函数用 congruence 归一化；$\log$ 用积分表示和逆函数单调性。

完整证明

由 $X$ 可逆且 $0\preceq X$，有 $X\succ0$。又 $Y\succeq X$，故 $Y\succ0$。令 $A=Y^{-1/2}XY^{-1/2}$，则 $0\prec A\preceq I$，所以 $A^{-1}\succeq I$。两边作 congruence 变换，得到 $X^{-1}\succeq Y^{-1}$，且 $Y^{-1}\succeq0$。

积分恒等式由

令 $M\to\infty$ 得到。若 $0\prec X\preceq Y$，则对每个 $t\ge0$，$X+tI\preceq Y+tI$，由逆函数反向单调，$(X+tI)^{-1}\succeq(Y+tI)^{-1}$。代入积分表示并积分，得到 $\log X\preceq\log Y$。

证明思路

交换时同时对角化；反例用两个不交换的 Pauli 型矩阵。

完整证明

(a) 若 $X,Y$ 交换且对称，则可同时正交对角化。逐特征值使用 $e^{x_i+y_i}=e^{x_i}e^{y_i}$，得到 $e^{X+Y}=e^Xe^Y$。

(b) 取

它们不交换。$e^{X+Y}$ 是对称矩阵；而

由于 $XY\ne YX$，该乘积不是对称矩阵。因此 $e^{X+Y}\ne e^Xe^Y$。

证明思路

把尾界写成 $2n\exp[-c\min(t^2/\sigma^2,t/K)]$，选择阈值吸收维度因子，再积分。

完整证明

令 $Z=\|\sum_iX_i\|$。矩阵 Bernstein 给出

取 $u=\log(2n)$。该尾界等价推出

的失败概率至多 $e^{-s}$。积分 $s\ge0$ 得

这里 $\sigma^2=\|\sum_i\mathbb EX_i^2\|$。

证明思路

沿用矩阵 Bernstein 证明，只把单项 MGF 换成 $\mathbb Ee^{\lambda\varepsilon A}\preceq e^{\lambda^2A^2/2}$。

完整证明

对标量有 $\mathbb Ee^{\lambda\varepsilon x}=\cosh(\lambda x)\le e^{\lambda^2x^2/2}$。由函数演算升级为

重复 Theorem 5.4.1 的 Lieb-MGF 证明，得到

其中 $S=\sum_i\varepsilon_iA_i$，$\sigma^2=\|\sum_iA_i^2\|$。优化 $\lambda=t/\sigma^2$ 得右尾。对 $-S$ 重复并合并，得到因子 $2n$。

证明思路

对尾界积分，维度因子贡献 $\sqrt{\log n}$，$p$ 阶矩贡献 $\sqrt p$。

完整证明

令 $Z=\|\sum_i\varepsilon_iA_i\|$。Theorem 5.4.13 给出

等价地，$Z$ 的 subgaussian 尺度至多 $C\sigma$，但带有初始质量因子 $n$。用尾积分公式

并从 $t\asymp\sigma\sqrt{\log n}$ 开始积分，得到

证明思路

把 $X_i$ 嵌入对称块矩阵 $\mathcal D(X_i)$，其范数等于 $\|X_i\|$。

完整证明

定义

则 $\mathcal D(X_i)$ 是 $(m+n)\times(m+n)$ 对称矩阵，均值为零，且 $\|\mathcal D(X_i)\|=\|X_i\|\le K$。同时

所以 variance 参数至多题中给出的 $\sigma^2$。对 $\sum_i\mathcal D(X_i)=\mathcal D(\sum_iX_i)$ 应用矩阵 Bernstein，并用 $\|\mathcal D(M)\|=\|M\|$，得到结论。

证明思路

对 $A_i$ 做 Hermitian dilation，然后应用对称矩阵 Khintchine。

完整证明

令 $\mathcal D(A_i)$ 如 Exercise 5.23。则

并且

对维度 $m+n$ 的对称矩阵 Khintchine 应用 Theorem 5.4.14，即得

证明思路

无 loops 只删除对角项；随机噪声矩阵的 Bernstein 参数不增，信号矩阵只受有界对角扰动。

完整证明

定义无 loops 模型为 $A_{ii}=0$，$i<j$ 时按社群内/社群间概率 $p,q$ 独立连边，并令 $A_{ji}=A_{ij}$。随机部分分解为 $\sum_{i<j}Z_{ij}$，比含 loops 情况少了 $i=j$ 项，因此 $\|Z_{ij}\|\le1$ 且 $\sigma^2\le a$ 仍成立。

期望矩阵 $D$ 与含 loops 版本只差一个对角矩阵，其范数至多 $p\le a/n$，远小于谱间隙量级 $a-b$。把这一扰动并入 Davis-Kahan 的噪声项，常数调整后 Theorem 5.5.1 的条件仍给出 $99\%$ 准确率。

证明思路

在 Theorem 5.6.1 的证明中保留矩阵 Bernstein 的尾界，而不是积分成期望。

完整证明

沿 Theorem 5.6.1，$Y_i=X_iX_i^{\mathsf T}-\Sigma$ 满足

矩阵 Bernstein 给出以至少 $1-2e^{-u}$ 的概率，

除以 $m$，并写 $r=\operatorname{tr}(\Sigma)/\|\Sigma\|$，得到

证明思路

让 $X$ 以很高概率为 $0$，以很小概率取巨大值以维持协方差为 $I$。

完整证明

取任意小 $\delta>0$。令 $Y$ 是各向同性随机向量，例如 $Y$ 均匀取 $\pm\sqrt n e_j$，并定义

则 $\mathbb EXX^{\mathsf T}=\mathbb EYY^{\mathsf T}=I$，所以 $X$ 各向同性。但 $m$ 个样本全为零的概率是 $(1-\delta)^m$。若取 $\delta\ll1/m$，该概率接近 $1$；此时 $\Sigma_m=0$，而 $\Sigma=I$，误差为 $1$。因此没有 (5.20) 这种有界性或其他尾部条件时，不可能有统一协方差估计保证。

证明思路

取 $X=\sqrt n\,\varepsilon e_J$。若某个坐标没被抽到，样本协方差在该方向为零，误差至少为 $1$。

完整证明

令 $J$ 均匀分布在 $\{1,\ldots,n\}$，$\varepsilon$ 为 Rademacher，$X=\sqrt n\,\varepsilon e_J$。则 $\mathbb EXX^{\mathsf T}=I$，且 $\|X\|_2=\sqrt n=(\mathbb E\|X\|_2^2)^{1/2}$，满足 Theorem 5.6.1 的有界性条件。

若 $m$ 个样本没有覆盖某个坐标 $k$，则 $\Sigma_m e_k=0$，而 $\Sigma e_k=e_k$，所以 $\|\Sigma_m-\Sigma\|\ge1$。coupon collector 说明若 $m\le c n\log n$，以高概率存在未出现的坐标。因此 $\|\Sigma_m-\Sigma\|<\|\Sigma\|$ 高概率失败。

若矩阵 Bernstein 期望界中的 $\log n$ 可一般去掉，Theorem 5.6.1 的证明会给出 $m\asymp n$ 的一般协方差估计，与上面的例子矛盾。因此对数因子一般不可去掉。

证明思路

把有效秩写成特征值和除以最大特征值。

完整证明

(a) 若 $\Sigma\ne0$，设非零特征值为 $\lambda_i$，最大值为 $\lambda_{\max}$。则

(b) 取 $\Sigma=\operatorname{diag}(1,\epsilon,\ldots,\epsilon)$，它满秩，但 $r(\Sigma)=1+(n-1)\epsilon\to1$。(c) 在 $\|\Sigma\|>0$ 的集合上，trace 和 operator norm 都连续，且分母非零，所以商连续。(d) 若 $X$ 取值于 $k$ 维子空间 $E$，则 $\Sigma$ 的像空间包含在 $E$ 中，因此 $\operatorname{rank}(\Sigma)\le k$，从而 $r(\Sigma)\le k$。

证明思路

把 frame elements 看成一个有界各向同性分布，应用协方差估计。

完整证明

设 frame 为 $u_1,\ldots,u_M$，满足 $\sum_j u_ju_j^{\mathsf T}=I$，且等范数给出 $\|u_j\|_2^2=n/M$。令随机向量 $X=\sqrt M\,u_J$，其中 $J$ 均匀分布在 $\{1,\ldots,M\}$。则

抽取 $m$ 个 frame elements 对应样本协方差

由 Theorem 5.6.1 的高概率形式，若 $m\gtrsim n\log n$，则 $\|\Sigma_m-I\|\le c$ 高概率成立。这就是近似 frame：其 frame operator 在 Loewner order 下满足 $(1-c)I\preceq\Sigma_m\preceq(1+c)I$。

证明思路

把 $\frac1mA^{\mathsf T}A-I$ 看成样本协方差偏差，并用高概率协方差估计控制。

完整证明

rows $A_i$ 各向同性意味着 $\mathbb EA_iA_i^{\mathsf T}=I_n$，所以

是样本协方差。由 $\|A_i\|_2\le K\sqrt n$ 和 $\mathbb E\|A_i\|_2^2=n$，Theorem 5.6.1 的高概率版本给出

以至少 $1-2n^{-ct^2}$ 的概率成立；当右侧超过常数时，所需下界可能为负且上界可由 $\|A\|^2\le\sum_i\|A_i\|^2\le mK^2n$ 粗略吸收，调整常数后仍成立。

记 $\delta=CKt\sqrt{n\log n/m}$。由奇异值与 Gram 矩阵关系，

乘以 $\sqrt m$，得到题中不等式。

证明思路

把随机 row 看成有界分布，样本协方差就是缩放后的 $B^{\mathsf T}B$。

完整证明

设 $a_1,\ldots,a_N$ 是 $A$ 的 rows，且 $\|a_j\|_2$ 相等。令随机向量 $X=\sqrt N\,a_J$，$J$ 均匀分布在 $\{1,\ldots,N\}$。则

抽取 $m$ 次形成 $B$，样本二阶矩为

等 row norm 给出有界性；有效秩不超过 $n$。由 Theorem 5.6.1 的高概率版本，若 $m\ge Cn\log n$，则以至少 $0.9$ 的概率，

Weyl 不等式把矩阵谱范数偏差转成所有特征值偏差：