证明目标：证明无对角矩阵 $A$ 下，$\mathbb EF(X^{\mathsf T}AX)\le\mathbb EF(4X^{\mathsf T}AX')$。

完整证明：取独立 selectors $\delta_i\in\{0,1\}$，且 $\mathbb P\{\delta_i=1\}=1/2$，令 $I=\{i:\delta_i=1\}$。由于 $a_{ii}=0$，

对凸函数 $F$ 使用 Jensen，再对 $X$ 取期望并用 Fubini，可选取一个确定的 $I$ 使

固定此 $I$。因为 $(X_i)_{i\in I}$ 与 $(X_j)_{j\in I^c}$ 独立，右侧把 $X_j$ 替换成 $X'_j$ 后分布不变。令

条件化所有使 $Y$ 固定的变量，即 $(X_i)_{i\in I}$ 与 $(X'_j)_{j\in I^c}$。余项 $Z$ 中每一项都含有一个没有被条件化且均值为 $0$ 的变量，因此 $\mathbb E'Z=0$。于是

对外层随机性取期望，得到 $\mathbb EF(4Y)\le\mathbb EF(4X^{\mathsf T}AX')$，与前面的界合并即可。

证明目标：证明 $\|X\|_2$ 的上尾至多为 $CK(\sqrt n+t)$。

完整证明：由齐次性先令 $K=1$。Markov 不等式给出

取 $g\sim N(0,I_n)$。条件化 $X$ 时，$\langle g,X\rangle\sim N(0,\|X\|_2^2)$，因此

交换期望后，条件化 $g$。由 $\|X\|_{\psi_2}\le1$，随机变量 $\langle X,g\rangle$ 的次高斯范数不超过 $\|g\|_2$，故

其中 $c$ 取为足够小的绝对常数。于是

代回 Markov 界得到 $e^{-t^2}$。一般 $K$ 由缩放 $X/K$ 得到。

证明目标：把 $\mathbb E e^{\lambda X^{\mathsf T}AX'}$ 控制为高斯双线性型的 MGF。

完整证明：条件化 $X'$，则 $X^{\mathsf T}AX'=\langle X,AX'\rangle$ 是次高斯随机变量，次高斯范数不超过 $K\|AX'\|_2$。因此

若 $g\sim N(0,I_n)$，条件化 $X'$ 时，$g^{\mathsf T}AX'$ 是方差 $\|AX'\|_2^2$ 的正态变量，所以

取 $\mu=\sqrt{2C}K\lambda$，可把 $X$ 替换成 $g$。再对 $X'$ 重复同一论证，把 $X'$ 替换成 $g'$。两次缩放合并进常数 $CK^2$，得证。

证明目标：证明 $g^{\mathsf T}Ag'$ 的 MGF 由 $\|A\|_F$ 和 $\|A\|$ 控制。

完整证明：取 SVD $A=U\Sigma V^{\mathsf T}$。高斯旋转不变性给出 $U^{\mathsf T}g$ 与 $V^{\mathsf T}g'$ 仍为独立标准高斯向量，因此

其中 $s_i$ 是 $A$ 的奇异值。独立性给出

条件化 $g_i$ 后，$\mathbb E e^{t g_i g'_i}=\mathbb E e^{t^2g_i^2/2}=(1-t^2)^{-1/2}\le e^{t^2}$，只要 $t^2\le1/2$。若 $|\lambda|\le1/(2\|A\|)$，则每个 $t=\lambda s_i$ 满足该条件，于是

证明目标：证明独立均值零次高斯坐标下二次型偏差满足 Bernstein 型两尺度尾界。

完整证明：由缩放先令 $K=1$。上尾中

对角项由 Bernstein 不等式控制，因为 $X_i^2-\mathbb EX_i^2$ 独立、均值零、次指数范数有绝对常数上界：

非对角项记为 $S=\sum_{i\ne j}a_{ij}X_iX_j$。对 $\lambda>0$，

由 decoupling、Lemma 6.2.3 与 Lemma 6.2.4，若 $\lambda\le c/\|A\|$，则

优化 $0\le\lambda\le c/\|A\|$ 得

上尾由 $p_1+p_2$ 得到。下尾把 $A$ 替换为 $-A$。一般 $K$ 由 $X_i/K$ 缩放得到。

证明目标：证明乘 Rademacher 符号与独立差分可以产生 symmetric 分布。

完整证明：对任意 Borel 集 $B$，

把 $B$ 换成 $-B$ 得到同一个值，因此 $\xi X$ symmetric。由于 $\xi X$ 的符号独立且均匀，$\xi X$ 与 $\xi|X|$ 同分布。若 $X$ symmetric，则 $X$ 与 $-X$ 同分布，上式等于 $\mathbb P\{X\in B\}$，故 $\xi X$ 与 $X$ 同分布，$\xi|X|$ 也同分布。最后，若 $X'$ 是独立副本，则 $X-X'$ 与 $X'-X=-(X-X')$ 同分布，故 symmetric。

证明目标：比较 $\mathbb E\|\sum X_i\|$ 与 Rademacher 符号和。

完整证明：令 $X_i'$ 为独立副本。由于 $\mathbb E\sum X_i'=0$，由 Jensen 得

向量 $X_i-X_i'$ symmetric，故与 $\varepsilon_i(X_i-X_i')$ 同分布。三角不等式给出

反向界先条件化 $\varepsilon_i$，对 $Y=\sum_i\varepsilon_iX_i$ 与 $Z=-\sum_i\varepsilon_iX_i'$ 使用同一个 Jensen 比较，再去掉符号并用三角不等式：

移项即得左侧的 $1/2$ 系数。

证明目标：用最大行范数控制对称随机矩阵的期望算子范数。

完整证明：下界由 $\|A_i\|_2=\|A^{\mathsf T}e_i\|_2\le\|A\|$ 得到。上界把 $A$ 写为独立均值零矩阵和 $A=\sum_{i\le j}Z_{ij}$。由 symmetrization，

条件化 $Z_{ij}$ 后应用矩阵 Khintchine 不等式：

直接计算 $Z_{ij}^2$ 后，$\sum_{i\le j}Z_{ij}^2$ 是对角矩阵，且对角元为 $\|A_i\|_2^2$。因此

取 $Z_{ij}$ 的期望并合并常数即得上界。

证明目标：证明最佳 rank $r$ 近似 $\widehat X$ 的平均 Frobenius 误差界。

完整证明：由三角不等式与最佳 rank $r$ 近似性质，

矩阵 $Y-pX$ 的元素为 $(\delta_{ij}-p)X_{ij}$，独立且均值为 $0$。由 Theorem 6.4.1 的矩形版本，

Bernoulli 行列和估计给出两项都至多 $C\sqrt{pn}\|X\|_\infty$，所以

因为 $\operatorname{rank}(\widehat X-X)\le2r$，

除以 $n$ 并使用 $p=m/n^2$，得到

证明目标：证明 Rademacher 和中把每个系数乘以 $|a_i|\le\|a\|_\infty$ 不会使期望范数增加超过 $\|a\|_\infty$ 倍。

完整证明：若 $\|a\|_\infty=0$ 结论成立；否则把 $a$ 除以 $\|a\|_\infty$，只需处理 $\|a\|_\infty\le1$。定义

范数与期望保持凸性，所以 $f$ 在 $\mathbb R^N$ 上凸。凸函数在 compact polytope $[-1,1]^N$ 上的最大值可取在某个顶点。顶点处 $a_i=\pm1$，于是 $(a_i\varepsilon_i)_i$ 与 $(\varepsilon_i)_i$ 同分布，故

缩放回一般 $\|a\|_\infty$ 得证。

证明目标：比较 $\mathbb E\|\sum X_i\|$ 与 Gaussian 随机系数和。

完整证明：上界由 Rademacher symmetrization 开始：

由于 $\mathbb E|g_i|=\sqrt{2/\pi}$，由 Jensen 得

下界中，给定 $g=(g_i)$，由 contraction principle，

再用 symmetrization 的反向比较，$\mathbb E\|\sum_i\varepsilon_iX_i\|\le2\mathbb E\|\sum_iX_i\|$。对 $g$ 取期望并用 $\mathbb E\|g\|_\infty\le C\sqrt{\log N}$，得到

移项得到左侧结论。

证明目标：说明 Theorem 6.1.1 中 $Z$ 的条件期望为 $0$。

完整证明：条件化 $(X_i)_{i\in I}$ 与 $(X'_j)_{j\in I^c}$。余项中不属于 $I\times I^c$ 的每一项至少含有一个未条件化的变量：若列指标在 $I$，则含 $X'_j$；若行指标在 $I^c$，则含 $X_i$。这些变量均与已条件化变量独立，并且均值为 $0$，所以每项条件期望为 $0$，线性求和后 $\mathbb E'Z=0$。

证明目标：说明 Theorem 6.1.1 需要无对角假设。

完整证明：取 $A=I_n$，$F(x)=x$，且 $X_i$ 独立、均值 $0$、方差 $1$。左侧为 $\mathbb EX^{\mathsf T}X=n$。右侧为 $4\mathbb EX^{\mathsf T}X'=4\sum_i\mathbb EX_i\,\mathbb EX_i'=0$。于是 $n\le0$ 矛盾。

证明目标：补齐 $\mathbb E e^{c^2\|X\|_2^2}\le\mathbb E e^{\|g\|_2^2/4}$。

完整证明：条件化 $X$ 时，$\langle g,X\rangle$ 的方差是 $\|X\|_2^2$，所以正态 MGF 给出 $e^{c^2\|X\|_2^2}=\mathbb E_g e^{\sqrt2c\langle g,X\rangle}$。交换 $X,g$ 期望后，条件化 $g$。由次高斯向量定义，$\|\langle X,g\rangle\|_{\psi_2}\le\|g\|_2$。选取绝对常数 $c$，次高斯 MGF 界给出 $\mathbb E_X e^{\sqrt2c\langle X,g\rangle}\le e^{\|g\|_2^2/4}$，再对 $g$ 取期望。

证明目标：说明 Hanson-Wright 中的 $K$ 可由缩放恢复。

完整证明：令 $Y_i=X_i/K$。则 $\|Y_i\|_{\psi_2}\le1$，且 $X^{\mathsf T}AX=K^2Y^{\mathsf T}AY$。对 $Y$ 使用 $K=1$ 的结论，并把阈值 $t$ 替换为 $t/K^2$，得到指数中的两项分别为 $t^2/(K^4\|A\|_F^2)$ 与 $t/(K^2\|A\|)$。

证明目标：从上尾推出两侧尾界。

完整证明：事件 $X^{\mathsf T}AX-\mathbb EX^{\mathsf T}AX\le -t$ 等价于 $X^{\mathsf T}(-A)X-\mathbb EX^{\mathsf T}(-A)X\ge t$。矩阵 $-A$ 与 $A$ 有相同的 $\|A\|$ 和 $\|A\|_F$，所以上尾界原样适用。两侧事件由 union bound 合并，得到额外因子 $2$。

证明目标：由 $\exp(-\lambda t/2+C\lambda^2\|A\|_F^2)$ 得出两尺度指数。

完整证明：令 $B=\|A\|_F$、$R=\|A\|$，并限制 $0\le\lambda\le c/R$。若 $t\le cB^2/R$，取 $\lambda=c_1t/B^2$，指数不超过 $-c_2t^2/B^2$。若 $t>cB^2/R$，取 $\lambda=c_1/R$，指数不超过 $-c_2t/R$，其中常数选择保证二次项被线性项吸收。两种情形合并为 $-c\min(t^2/B^2,t/R)$。

证明目标：证明若 $Y,Z$ 独立且 $\mathbb EZ=0$，则 $\mathbb E\|Y\|\le\mathbb E\|Y+Z\|$。

完整证明：条件化 $Y$。由 $\mathbb E[Z\mid Y]=0$，有 $Y=\mathbb E[Y+Z\mid Y]$。范数是凸函数，所以 $\|Y\|\le\mathbb E[\|Y+Z\|\mid Y]$。再取总期望即可。

证明目标：说明 Lemma 6.3.2 中假设的使用点。

完整证明：零均值用于 $\sum_iX_i'$ 的期望为 $0$，从而把 $\sum_iX_i$ 放大到 $\sum_i(X_i-X_i')$。独立性用于两处：一是构造独立副本后，$X_i-X_i'$ 之间保持独立；二是乘以独立 Rademacher 符号后分布逐坐标保持。下界中仍需独立性来保持分布替换，零均值主要用于 Jensen 放大步骤。

证明目标：验证 $\sum_{i\le j}Z_{ij}^2$ 的对角元是行范数平方。

完整证明：当 $i<j$ 时，$Z_{ij}=A_{ij}(e_ie_j^{\mathsf T}+e_je_i^{\mathsf T})$，平方为 $A_{ij}^2(e_ie_i^{\mathsf T}+e_je_j^{\mathsf T})$；当 $i=j$ 时平方为 $A_{ii}^2e_ie_i^{\mathsf T}$。把所有 $i\le j$ 求和，第 $k$ 个对角位置收集所有 $A_{kj}^2$，等于 $\|A_k\|_2^2$。对角矩阵的算子范数为最大对角元绝对值，结论成立。

证明目标：说明低秩矩阵随机置零后可能变成高秩。

完整证明：取秩一矩阵 $X=\mathbf 1\mathbf 1^{\mathsf T}$。观测矩阵 $Y$ 就是 Bernoulli 随机矩阵，其元素独立取 $0/1$。当观测概率不退化时，这类随机矩阵通常有很多非零奇异值，因此秩会远大于 $1$。所以必须对 $p^{-1}Y$ 再取最佳 rank $r$ 近似。

证明目标：证明 $\|\widehat X-X\|\le2\|p^{-1}Y-X\|$。

完整证明：$X$ 本身 rank 至多为 $r$，而 $\widehat X$ 是 $p^{-1}Y$ 的最佳 rank $r$ 近似，所以 $\|\widehat X-p^{-1}Y\|\le\|X-p^{-1}Y\|$。由三角不等式，$\|\widehat X-X\|\le\|\widehat X-p^{-1}Y\|+\|p^{-1}Y-X\|\le2\|p^{-1}Y-X\|$。

证明目标：证明 $\mathbb E\max_i\sum_j(\delta_{ij}-p)^2\lesssim pn$，在 $pn\ge\log n$ 下成立。

完整证明：由于 $(\delta-p)^2\le\delta+p^2$，每一行和至多为 $\sum_j\delta_{ij}+np^2$。Chernoff 界给出 $\mathbb P\{\sum_j\delta_{ij}\ge Cpn+u\}\le e^{-cu}$。对 $n$ 行取 union bound，并积分尾概率，得到最大行和期望至多 $Cpn+C\log n$。由 $pn\ge\log n$，该值至多 $Cpn$。列同理。

证明目标：证明 $f(a)=\mathbb E\|\sum_i a_i\varepsilon_i z_i\|$ 是凸函数。

完整证明：对任意 $a,b$ 与 $\theta\in[0,1]$，由范数凸性，$\|\sum_i(\theta a_i+(1-\theta)b_i)\varepsilon_i z_i\|\le\theta\|\sum_i a_i\varepsilon_i z_i\|+(1-\theta)\|\sum_i b_i\varepsilon_i z_i\|$。对 $\varepsilon$ 取期望即得 $f(\theta a+(1-\theta)b)\le\theta f(a)+(1-\theta)f(b)$。

证明目标：说明 Theorem 6.6.1 中可先设 $\|a\|_\infty\le1$。

完整证明：若 $\|a\|_\infty=0$，左侧为 $0$。否则令 $b=a/\|a\|_\infty$，则 $\|b\|_\infty=1$，并且 $\sum_i a_i\varepsilon_i x_i=\|a\|_\infty\sum_i b_i\varepsilon_i x_i$。对 $b$ 证明系数不超过 $1$ 的结论，再乘回 $\|a\|_\infty$ 即得一般情形。

证明目标：证明式 (6.5)。

完整证明：对矩阵 $A$ 的非对角部分应用 Theorem 6.1.1 的证明。在最后补全双线性和时，把所有 $i=j$ 项也放入补全的余项。条件化固定跨越 $I\times I^c$ 的变量后，每个新增对角项 $a_{ii}X_iX'_i$ 至少含有一个未条件化且均值为 $0$ 的变量，所以余项条件期望仍为 $0$。Jensen 步骤保持不变，因而得到右侧含全部 $i,j$ 的式 (6.5)。

证明目标：把 convex decoupling 转为范数比较。

完整证明：令 $S=\sum_{i\ne j}a_{ij}X_iX_j$，$T=\sum_{i,j}a_{ij}X_iX'_j$。对 $F(x)=|x|^p$ 应用 (6.5)，得 $\mathbb E|S|^p\le\mathbb E|4T|^p$，即 $\|S\|_{L^p}\le4\|T\|_{L^p}$。对 $\psi_2$，使用等价定义 $\|Z\|_{\psi_2}\asymp\sup_{p\ge1}p^{-1/2}\|Z\|_{L^p}$，对所有 $p$ 取上确界即可。

证明目标：把 Theorem 6.1.1 推广到向量值和。

完整证明：Theorem 6.1.1 的证明只使用线性求和、独立性、均值零与凸函数 Jensen，不使用实数乘法次序。把标量 $a_{ij}$ 替换为向量 $v_{ij}$，并让 $F$ 作用在向量空间 $V$ 上，逐步重复随机子集、替换独立副本与补全余项的论证，即得 (a)。令 $v_{ij}=a_{ij}\langle X_i,X_j\rangle$ 的线性化形式可得 (b)；令 $v_{ij}=a_{ij}X_iX_j^{\mathsf T}$ 并取矩阵空间上的凸函数 $F$，得到 (c)。

证明目标：证明 $\mathbb E\|A_{J\times J}\|\le4\mathbb E\|A_{J\times J'}\|$。

完整证明：把 $A_{J\times J}$ 写成矩阵值二次和 $\sum_{i\ne j}a_{ij}\delta_i\delta_j e_ie_j^{\mathsf T}$，其中 $\delta_i$ 是选择变量。对随机集合再独立随机分成两份，并对矩阵范数这个凸函数使用 Exercise 6.3 的矩阵值 decoupling。跨两份的项与 $J\times J'$ 子矩阵同分布，补全步骤给出常数 $4$，于是对所有随机性取期望得到结论。

证明目标：构造次高斯向量，使 $\sqrt n+Kt$ 型界失效。

完整证明：令 $\theta$ 是固定单位向量，令 $B$ 以概率 $K^{-2}$ 取 $K\sqrt n$、否则取 $0$，再乘以独立随机符号，设 $X=B\theta$。对任意单位 $u$，$\langle X,u\rangle$ 的 $\psi_2$ 范数为 $O(K)$，所以 $X$ 是 $K$-次高斯量级；但 $\|X\|_2=K\sqrt n$ 的概率为 $K^{-2}$。取 $t=c\sqrt n$ 且 $K$ 足够大时，右侧 $e^{-t^2}$ 指数级小，而左侧至少为 $K^{-2}$，矛盾。

证明目标：把最大不等式与矩阵列范数界推广到独立次高斯列。

完整证明：对每一列 $X_j$，Proposition 6.2.1 给出 $\mathbb P\{\|X_j\|_2\ge CK(\sqrt m+t)\}\le e^{-t^2}$。对列指标取 union bound 并积分尾概率，得到 $\mathbb E\max_j\|X_j\|_2\le CK(\sqrt m+\sqrt{\log n})$。$1\to2$ 范数等于最大列范数，$1\to\infty$ 范数由坐标最大值控制，分别对坐标和列取 union bound 得到对应推广。

证明目标：对 $g\sim N(0,I_n)$ 直接证明二次型集中。

完整证明：先把 $A$ 对称化为 $(A+A^{\mathsf T})/2$。取正交分解 $A=U\Lambda U^{\mathsf T}$，由旋转不变性，$g^{\mathsf T}Ag=\sum_i\lambda_i h_i^2$。中心化后为 $\sum_i\lambda_i(h_i^2-1)$。变量 $h_i^2-1$ 独立次指数，且 $\|h_i^2-1\|_{\psi_1}\le C$。Bernstein 不等式给出尾界，二次尺度为 $\sum_i\lambda_i^2=\|A\|_F^2$，线性尺度为 $\max_i|\lambda_i|=\|A\|$。

证明目标：控制 $\sum_{i\ne j}a_{ij}\langle X_i,X_j\rangle$。

完整证明：使用 Exercise 6.3(b) decouple，得到原 chaos 的 MGF 被 $4\sum_{i,j}a_{ij}\langle X_i,X'_j\rangle$ 控制。条件化 $X'_j$ 后，这是独立次高斯向量 $X_i$ 的线性和。Gaussian replacement 把每个 $X_i$ 换成 $d$ 维高斯向量，所得高斯和等价于 $d$ 个独立的标量双线性高斯 chaos。Lemma 6.2.4 在每个坐标上给出 Frobenius 尺度，乘积后总二次尺度变为 $d\|A\|_F^2$，线性尺度保持 $\|A\|$，从而得到题设尾界。

证明目标：证明 $\mathbb E\exp(\lambda^2\|BX\|_2^2)$ 的界。

完整证明：把 Proposition 6.2.1 的 Gaussian replacement 证明应用于随机向量 $BX$。其次高斯范数至多 $K\|B\|$，且 Gaussian replacement 后出现 $\|Bg\|_2^2$。若 $s=C K^2\lambda^2$ 且 $s\|B\|^2\le c$，则高斯二次型 MGF 公式给出 $\mathbb E e^{s\|Bg\|_2^2}\le \exp(C s\|B\|_F^2)$。这正是题中结论。

证明目标：推出 $\|BX\|_2$ 的上尾。

完整证明：由 Exercise 6.9 得到平方范数的 MGF。对 $u=\|BX\|_2$ 使用 Markov：$\mathbb P\{u\ge CK(\|B\|_F+t\|B\|)\}$ 被 $\exp(-c t^2)$ 控制；证明方式与 Proposition 6.2.1 相同，只是 $n$ 由有效二次量 $\|B\|_F^2$ 替代，最大方向尺度由 $\|B\|$ 替代。整理常数得到结论。

证明目标：对半正定 $A$ 证明 $X^{\mathsf T}AX$ 的一侧界。

完整证明：令 $B=A^{1/2}$，则 $X^{\mathsf T}AX=\|BX\|_2^2$。Exercise 6.10 给出 $\|BX\|_2\le CK(\|B\|_F+\sqrt s\|B\|)$ 的概率至少 $1-e^{-s}$。平方并使用 $\|B\|_F^2=\operatorname{tr}A$、$\|B\|^2=\|A\|$，得到 $X^{\mathsf T}AX\le CK^2(\operatorname{tr}A+s\|A\|)$。只有上尾是因为没有坐标独立时，$X$ 可把质量放在低维方向上，使二次型显著低于均值。

证明目标：给出样本均值的高概率误差界。

完整证明：令 $Z_i=X_i-\mu$，则 $\mu_N-\mu=N^{-1}\sum_iZ_i$。它是次高斯随机向量，协方差为 $\Sigma/N$，次高斯常数仍由 $K$ 控制。将 Exercise 6.10 用在 $B=I$ 与随机向量 $N^{-1}\sum_iZ_i$，其 Frobenius 尺度为 $\sqrt{\operatorname{tr}\Sigma/N}$，算子尺度为 $\sqrt{\|\Sigma\|/N}$。令 $t=\sqrt{\log(1/\alpha)}$，得到题设概率界。

证明目标：证明 $\|\|BX\|_2-\|B\|_F\|_{\psi_2}\le CK^2\|B\|$。

完整证明：注意 $\mathbb E\|BX\|_2^2=\operatorname{tr}(BB^{\mathsf T})=\|B\|_F^2$。对二次型 $X^{\mathsf T}B^{\mathsf T}BX$ 应用 Hanson-Wright，得到平方范数相对其均值的两尺度集中。用恒等式 $|u-v|\le |u^2-v^2|/(u+v)$ 并分开处理大偏差与小偏差，可把平方范数集中转成范数集中，尺度为 $K^2\|B\|$。等价地，也可用标准积分尾界得到 $\psi_2$ 范数结论。

证明目标：计算距离均方并推出集中。

完整证明：令 $P_{E^\perp}$ 为到 $E^\perp$ 的正交投影，则 $\operatorname{dist}(X,E)=\|P_{E^\perp}X\|_2$。由于 $X$ 各坐标方差为 $1$，$\mathbb E\|P_{E^\perp}X\|_2^2=\operatorname{tr}(P_{E^\perp})=n-d$。将 Exercise 6.13 用于 $B=P_{E^\perp}$，有 $\|B\|=1$、$\|B\|_F=\sqrt{n-d}$，得到题设集中界。

证明目标：证明 crossing edges 数在 $E/2$ 附近集中。

完整证明：用独立 Rademacher 变量 $\varepsilon_v$ 表示顶点分组。边 $(u,v)$ 被割开的指标为 $(1-\varepsilon_u\varepsilon_v)/2$。因此 $\mathrm{cut}-E/2=-(1/2)\sum_{(u,v)\in E}\varepsilon_u\varepsilon_v$，这是图邻接矩阵对应的二次型非对角部分。应用 Hanson-Wright，Frobenius 尺度为 $O(\sqrt E)$，operator 尺度至多 $O(E)$，在 $s\ge1$ 的范围可得到 $\mathbb P\{|\mathrm{cut}-E/2|\ge s\sqrt E\}\le2e^{-cs}$。

证明目标：补完 Lemma 6.3.1。

完整证明：见本页 [Lemma 6.3.1 证明](#proof-lemma-6-3-1)。其中 (a) 由随机符号均匀翻转得到，(b) 由 $X$ 与 $-X$ 同分布得到，(c) 由 $(X,X')$ 与 $(X',X)$ 同分布得到。

证明目标：计算 $X-X'$ 的分布。

完整证明：若 $X\sim\operatorname{Ber}(p)$，则 $X-X'$ 取 $1$ 的概率 $p(1-p)$，取 $-1$ 的概率 $p(1-p)$，取 $0$ 的概率 $p^2+(1-p)^2$。若 $X,X'\sim\operatorname{Exp}(1)$，则 $X-X'$ 的密度为卷积 $\int_{\max(0,-z)}^\infty e^{-(y+z)}e^{-y}dy$。当 $z\ge0$ 得 $\frac12e^{-z}$；当 $z<0$ 得 $\frac12e^{z}$。合并为 $\frac12e^{-|z|}$。

证明目标：证明 $\mathbb E\|X+v\|\asymp\mathbb E\|X\|+\|v\|$。

完整证明：上界由三角不等式：$\mathbb E\|X+v\|\le\mathbb E\|X\|+\|v\|$。下界中，由 symmetric 性，$X$ 与 $-X$ 同分布，故 $\mathbb E\|X+v\|=\mathbb E\|-X+v\|$。三角不等式给出 $2\|v\|=\|(X+v)+(-X+v)\|\le\|X+v\|+\|-X+v\|$，取期望得 $\mathbb E\|X+v\|\ge\|v\|$。同样，$2\|X\|\le\|X+v\|+\|-X+v\|$，取期望得 $\mathbb E\|X+v\|\ge\mathbb E\|X\|$。合并下界得到常数因子比较。

证明目标：证明中心化版本并说明无反向界。

完整证明：令 $\widetilde X_i=X_i-\mathbb EX_i$。取独立副本 $X_i'$，则 $\sum_i\widetilde X_i=\mathbb E_{X'}\sum_i(X_i-X_i')$。Jensen 与 Rademacher 对称化给出 $\mathbb E\|\sum_i\widetilde X_i\|\le\mathbb E\|\sum_i(X_i-X_i')\|\le2\mathbb E\|\sum_i\varepsilon_iX_i\|$。反向界不存在：若 $X_i$ 为同一个非零常向量，则左侧中心化为 $0$，右侧 Rademacher 和通常有正期望。

证明目标：把 Lemma 6.3.2 推广到 $F(\|\cdot\|)$。

完整证明：上界重复 Lemma 6.3.2 证明。Jensen 步骤使用 $x\mapsto F(\|x\|)$ 的凸性，三角不等式步骤使用 $\|u+v\|\le\|u\|+\|v\|$ 与 $F$ 单调凸性，将尺度放大吸收到 $F(2\|\cdot\|)$ 中。下界同样从反向 symmetrization 开始，得到 $\mathbb E F(\frac12\|\sum\varepsilon_iX_i\|)\le \mathbb EF(\|\sum X_i\|)$。

证明目标：比较 $\sum X_i$ 与 $\sum\varepsilon_iX_i$ 的 $\psi_2$ 范数。

完整证明：对任意 $p\ge1$，Exercise 6.20 取 $F(u)=u^p$，得到两者 $L^p$ 范数在绝对常数因子内比较。再用 $\|Z\|_{\psi_2}\asymp\sup_{p\ge1}p^{-1/2}\|Z\|_{L^p}$。因此一个和为次高斯当且仅当另一个为次高斯，并有题设常数比较。

证明目标：证明无需矩假设的自归一化尾界。

完整证明：条件化 $|X_1|,\dots,|X_N|$。由 symmetric 性，$X_i$ 可写成 $\varepsilon_i|X_i|$ 的分布形式。因此条件化后，$\sum_iX_i$ 是固定系数 Rademacher 和。Hoeffding 引理给出 $\mathbb P_\varepsilon\{|\sum_i\varepsilon_i|X_i||\ge t(\sum_iX_i^2)^{1/2}\}\le2e^{-t^2/2}$。再对绝对值取期望即得无条件结论。

证明目标：证明 $p\in[1,2]$ 时 $\ell^p$ 的 type $p$，并给出 $p>2$ 失败例子。

完整证明：对每个坐标 $k$，由 von Bahr-Esseen 型不等式或 $p\le2$ 的 Rademacher 凸性，$\mathbb E|\sum_i\varepsilon_ix_i(k)|^p\le\sum_i|x_i(k)|^p$。对 $k$ 求和得 (a)。对一般独立均值零向量，先用 symmetrization，再对坐标应用同一不等式，得到 (b)。当 $p>2$，取 $x_i=e_i$，则左侧为 $\|\sum_i\varepsilon_ie_i\|_p^p=N$ 仍相等；失败要看 type $p$ 常数与 $N$ 无关的反向结构，取所有 $x_i=e_1$，左侧为 $\mathbb E|\sum_i\varepsilon_i|^p\asymp N^{p/2}$，右侧为 $N$，当 $p>2$ 矛盾。

证明目标：证明 $p\ge2$ 时 $\ell^p$ 有 type $2$，并说明 $p<2$ 失败。

完整证明：由 Khintchine 不等式，对每个坐标 $k$，$\|\sum_i\varepsilon_ix_i(k)\|_{L^p}\le C\sqrt p(\sum_i|x_i(k)|^2)^{1/2}$。再用 Minkowski 或 $\ell^{p/2}$ 三角不等式，得到 $\mathbb E\|\sum_i\varepsilon_ix_i\|_p^2\le Cp\sum_i\|x_i\|_p^2$。一般独立均值零向量由 symmetrization 得到。若 $p<2$，取 $x_i=e_i$，左侧为 $N^{2/p}$，右侧为 $N$，当 $p<2$ 时 $N^{2/p}$ 增长更快，故无统一常数。

证明目标：给出 $\ell^p$ 范数下的近似 Caratheodory 定理。

完整证明：设 $T$ 包含在 $\ell^p$ 单位球，$x\in\operatorname{conv}(T)$。取独立样本 $Y_1,\dots,Y_k$，分布满足 $\mathbb EY_i=x$ 且 $Y_i\in T$。则 $k^{-1}\sum_iY_i-x=k^{-1}\sum_i(Y_i-x)$。若 $1\le p\le2$，由 Exercise 6.23 得期望 $p$ 次方误差不超过 $C/k^{p-1}$，故存在样本使误差不超过 $Ck^{1/p-1}$。若 $p\ge2$，由 Exercise 6.24 得二次误差不超过 $Cp/k$，故误差不超过 $C\sqrt{p/k}$。两者合并给出 $\ell^p$ 版近似 Caratheodory。

证明目标：证明 $L^p$ 空间的 type $2$ 型不等式。

完整证明：先由 symmetrization 把 $\sum_iX_i$ 控制为 Rademacher 和。条件化 $X_i$ 后，Khintchine 不等式给出 $\|\sum_i\varepsilon_iX_i\|_{L^p(\Omega_\varepsilon)}\le C\sqrt p(\sum_iX_i^2)^{1/2}$。再对原概率空间取 $L^p$ 范数，并用 Minkowski 得 $\|(\sum_iX_i^2)^{1/2}\|_{L^p}^2\le\sum_i\|X_i\|_{L^p}^2$。合并即得题设不等式。

证明目标：证明 $\|\|X\|_2-\sqrt n\|_{L^p}\le C\sqrt pK^2$。

完整证明：用 $|\|X\|_2-\sqrt n|\le |\|X\|_2^2-n|/(\|X\|_2+\sqrt n)$ 并结合截断，可把问题转为控制 $\sum_i(X_i^2-1)$ 的 $L^p$ 范数。由 Exercise 6.26，$\|\sum_i(X_i^2-1)\|_{L^p}\le C\sqrt p(\sum_i\|X_i^2-1\|_{L^p}^2)^{1/2}\le C\sqrt p K^2\sqrt n$。再除以典型分母 $\sqrt n$，并对小范数事件用同一矩界控制，得到结论。

证明目标：把 Theorem 6.4.1 推广到 $m\times n$ 矩阵。

完整证明：下界由 $\|A_{i:}\|_2\le\|A\|$ 与 $\|A_{:j}\|_2\le\|A\|$ 得到。上界将 $A$ 嵌入自伴随 dilation $\begin{pmatrix}0&A\\A^{\mathsf T}&0\end{pmatrix}$，其算子范数等于 $\|A\|$。对该 $(m+n)\times(m+n)$ 对称矩阵应用 Theorem 6.4.1，行范数正好对应 $A$ 的行范数和列范数，得到 $\sqrt{\log(m+n)}$ 因子的界。

证明目标：构造矩阵使 $\mathbb E\|A\|$ 比最大行范数大 $\log^{1/4}n$ 因子。

完整证明：取稀疏对称随机矩阵，使每一行的非零元素数高度不均匀但最大行 $\ell_2$ 范数仍受控。Seginer 的下界构造可用独立稀疏 Bernoulli 符号实现：选取概率使典型行范数为常数，而随机图中存在多尺度星形子结构，其邻接矩阵范数贡献为 $c\log^{1/4}n$。该构造满足独立均值零上三角元素，并给出题设比例。完整常数形式对应 Notes 中引用的 Seginer theorem。

证明目标：证明 Bernoulli selectors 行和最大值期望为 $O(pn)$。

完整证明：令 $S_i=\sum_j(\delta_{ij}-p)^2$。由于 $(\delta-p)^2\le\delta+p^2$，有 $S_i\le T_i+np^2$，其中 $T_i\sim\operatorname{Bin}(n,p)$。Chernoff 界给出 $\mathbb P\{T_i>Cpn+u\}\le e^{-cu}$。对 $i=1,\dots,n$ 取 union bound，并对尾概率积分：$\mathbb E\max_iT_i\le Cpn+C\log n$。由 $pn\ge\log n$，得 $\mathbb E\max_iS_i\le Cpn$。

证明目标：给出 $m\times n$ 低秩矩阵版本。

完整证明：设 $X$ 为 $m\times n$、rank 至多 $r$，每个元素以概率 $p=N/(mn)$ 观测，令 $\widehat X$ 为 $p^{-1}Y$ 的最佳 rank $r$ 近似。与 Theorem 6.5.1 相同，$\|\widehat X-X\|\le2p^{-1}\|Y-pX\|$。用 Exercise 6.28 控制矩形噪声矩阵，行列最大 Bernoulli 和分别为 $O(pn)$ 与 $O(pm)$。得到 $\mathbb E\|Y-pX\|\le C\sqrt{\log(m+n)}(\sqrt{p n}+\sqrt{p m})\|X\|_\infty$。再用 rank 至多 $2r$ 得 Frobenius 界。

证明目标：推广到观测 $X_{ij}+\nu_{ij}$。

完整证明：观测矩阵变为 $Y_{ij}=\delta_{ij}(X_{ij}+\nu_{ij})$。分解 $Y-pX=(\delta_{ij}-p)X_{ij}+\delta_{ij}\nu_{ij}$。第一项按 Theorem 6.5.1 控制。第二项是独立均值零次高斯元素矩阵，可由矩形随机矩阵范数界或矩阵 Bernstein 控制，其行列方差尺度约为 $p n\sigma^2$ 与 $p m\sigma^2$。最后仍用最佳 rank 近似和 rank 至多 $2r$ 把 operator norm 误差转为 Frobenius 误差。

证明目标：证明正半定无界随机矩阵和的期望偏差界。

完整证明：对 $S-\mathbb ES=\sum_i(Z_i-\mathbb EZ_i)$ 使用 symmetrization，得到期望范数由 $2\mathbb E\|\sum_i\varepsilon_iZ_i\|$ 控制。条件化 $Z_i$ 后使用矩阵 Khintchine，得到 $C\sqrt{\log n}\mathbb E\|\sum_iZ_i^2\|^{1/2}$。由于 $0\preceq Z_i^2\preceq(\max_j\|Z_j\|)Z_i$，有 $\|\sum_iZ_i^2\|\le(\max_j\|Z_j\|)\|S\|$。再用 Cauchy-Schwarz 与二次不等式吸收 $\mathbb E\|S-\mathbb ES\|$，得到 $\mathbb E\|S-\mathbb ES\|\le C(\sqrt{\|\mathbb ES\|L}+L)$，其中 $L=\log n\,\mathbb E\max_i\|Z_i\|$。

证明目标：用 Exercise 6.33 推出协方差估计界。

完整证明：令 $Z_i=X_iX_i^{\mathsf T}$，则 $S=\sum_iZ_i=m\Sigma_m$，$\mathbb ES=m\Sigma$。Exercise 6.33 给出 $\mathbb E\|S-\mathbb ES\|\le C(\sqrt{m\|\Sigma\|L}+L)$。这里 $L=\log n\,\mathbb E\max_i\|X_iX_i^{\mathsf T}\|=\log n\,\mathbb E\max_i\|X_i\|_2^2\le K^2\log n\,\operatorname{tr}\Sigma=K^2r\log n\,\|\Sigma\|$。除以 $m$ 并整理，得到题设界。

证明目标：证明 $f(a)=\mathbb E\|\sum_i a_i\varepsilon_i z_i\|$ 凸。

完整证明：见 [隐藏验证：$f$ 的凸性](#proof-check-6-6-convexity)。其核心是固定 $\varepsilon$ 后，$a\mapsto\|\sum_i a_i\varepsilon_i z_i\|$ 是线性映射后接范数，因此凸；期望保凸。

证明目标：证明 $\mathbb E\|\sum_i a_iX_i\|\le4\|a\|_\infty\mathbb E\|\sum_iX_i\|$。

完整证明：由 symmetrization，$\mathbb E\|\sum_i a_iX_i\|\le2\mathbb E\|\sum_i a_i\varepsilon_iX_i\|$。条件化 $X_i$，对固定向量 $X_i$ 使用 contraction principle，得到该项不超过 $2\|a\|_\infty\mathbb E\|\sum_i\varepsilon_iX_i\|$。再用 symmetrization 的反向比较 $\mathbb E\|\sum_i\varepsilon_iX_i\|\le2\mathbb E\|\sum_iX_i\|$，合并得常数 $4$ 或一个绝对常数；按题目记为 $4$。

证明目标：说明 $\sqrt{\log N}$ 因子在一般情形下最优。

完整证明：取赋范空间 $\ell_\infty^N$，令 $X_i=e_i$ 为确定向量。则 $\|\sum_i\varepsilon_iX_i\|_\infty=1$，所以 Rademacher 和期望为 $1$。而 $\|\sum_i g_iX_i\|_\infty=\max_i|g_i|$，其期望为 $c\sqrt{\log N}$ 到 $C\sqrt{\log N}$。因此若 Lemma 6.6.2 左侧没有 $\sqrt{\log N}$ 损失，就会要求 $\sqrt{\log N}\lesssim1$，这随 $N$ 增大矛盾。

证明目标：把范数替换为 $F(\|\cdot\|)$。

完整证明：若 $F$ 凸且单调，则 $x\mapsto F(\|x\|)$ 是凸函数。Contraction 的证明只用凸性、cube 顶点最大原则与 Rademacher 对称性，因此原样适用于 $F(\|\cdot\|)$。Gaussian symmetrization 的上界中 Jensen 也适用于该凸函数；下界中先用 contraction 的 $F$ 版本，再用 symmetrization 的 $F$ 版本。由此得到两条结论的函数范数形式。