证明目标：证明 $\mathbb E\sup_{x\in T}|\|Ax\|_2-\sqrt m\|x\|_2|\le CK^2\gamma(T)$。

完整证明：定义 $Z_x=\|Ax\|_2-\sqrt m\|x\|_2$。Theorem 9.1.2 给出 $\|Z_x-Z_y\|_{\psi_2}\le CK^2\|x-y\|_2$，并且 $Z_0=0$。对过程 $Z_x$ 和 $-Z_x$ 分别应用 Talagrand comparison 的几何形式，得到

二者合并等价于绝对值上确界，用 Gaussian complexity $\gamma(T)=\mathbb E\sup_{x\in T}|\langle g,x\rangle|$ 表示，得到结论。

证明目标：证明 $Z_x=\|Ax\|_2-\sqrt m\|x\|_2$ 的 $\psi_2$ 增量。

完整证明：第一步，若 $\|x\|_2=1$ 且 $y=0$，则 $Ax$ 的坐标独立、isotropic、subgaussian，norm concentration 给出 $\|\|Ax\|_2-\sqrt m\|_{\psi_2}\le CK^2$。第二步，若 $x,y$ 都是单位向量，展开

除以 $\|x-y\|_2$ 后得到独立均值零 subexponential 和，Bernstein inequality 给出该平方差除以 $\|x-y\|_2$ 的 tail 尺度为 $\sqrt m$。第三步，用

并把事件分成 $\|Ax\|_2\ge\sqrt m/2$ 与补事件；补事件由第一步控制，从而得到单位球面上的 $\psi_2$ 增量。第四步，对一般 $x,y$ 通过缩放令 $\|x\|_2=1\le\|y\|_2$，设 $\bar y=y/\|y\|_2$。三角不等式、齐次性和第一步给出

Figure 9.1 的几何验证给出括号不超过 $\sqrt2\|x-y\|_2$，结论成立。

证明目标：由 matrix deviation 控制 $\operatorname{diam}(PT)$。

完整证明：令 $P=A/\sqrt n$。对差集 $T-T$ 应用 Theorem 9.1.1，得到

除以 $\sqrt n$，并用 $\gamma(T-T)\le2\gamma(T)\asymp2\sqrt n\,w_s(T)$，得到

下界或双边形式同样由偏差界应用于实现直径的差向量得到。

证明目标：证明 effective rank 控制 subgaussian covariance estimation。

完整证明：写 $X=\Sigma^{1/2}Z$，其中 $Z$ isotropic subgaussian。令 $A$ 的行为 $Z_i$，则

Exercise 9.3 的 quadratic deviation 给出

对 ellipsoid，$\operatorname{rad}(T)=\|\Sigma\|^{1/2}$，$\gamma(T)\le(\operatorname{tr}\Sigma)^{1/2}$。代入并用 $r=\operatorname{tr}(\Sigma)/\|\Sigma\|$，得到 $CK^4(\sqrt{r/m}+r/m)\|\Sigma\|$。

证明目标：证明无限集合的 additive JL bound。

完整证明：对差集 $T=\mathcal X-\mathcal X$ 应用 Theorem 9.1.1 的高概率版本，得到

由 Lemma 7.5.11，$\gamma(\mathcal X-\mathcal X)\le Cw(\mathcal X)$。令 $Q=A/\sqrt m$，两边除以 $\sqrt m$，即得对所有 $x,y\in\mathcal X$ 的 additive error $\delta=CK^2w(\mathcal X)/\sqrt m$。

证明目标：控制随机截面 $T\cap\ker A$ 的直径。

完整证明：对差集 $T-T$ 应用 Theorem 9.1.1：

若 $x,y\in T\cap\ker A$，则 $A(x-y)=0$，所以上式内部等于 $\sqrt m\|x-y\|_2$。因此

证明目标：证明 $\ker A$ 以高概率避开 $T\subset S^{n-1}$。

完整证明：高概率 matrix deviation 给出

概率至少 $1-2e^{-u^2}$。取 $u=\sqrt m/(2C_1K^2)$。若存在 $x\in T\cap\ker A$，则左边至少 $\sqrt m$，从而 $\sqrt m\le C_1K^2w(T)+\sqrt m/2$。当 $m\ge CK^4w(T)^2$ 且 $C$ 充分大时矛盾。因此该事件上 $T\cap\ker A=\varnothing$，概率为 $1-2e^{-cm/K^4}$。

证明目标：证明约束恢复误差由 $w(T)/\sqrt m$ 控制。

完整证明：真实 $x$ 与恢复 $\hat x$ 都在 $T$ 中，且满足 $A\hat x=Ax$。因此误差 $h=\hat x-x$ 属于 $(T-T)\cap\ker A$。由 $M^*$ bound 应用于 $T$，

仿射版本可由对 $T-T$ 的同一证明得到。因此结论成立。

证明目标：由 constrained recovery 推出 sparse recovery。

完整证明：若 $x$ 是 $s$-sparse 且 $\|x\|_2\le1$，则 $\|x\|_1\le\sqrt s$，所以 $x\in T=\sqrt s B_1^n\cap B_2^n$。用 $\ell^1$ constrained program 等价于在该 convex feasible set 中恢复。由 Theorem 9.4.4，误差由 $w(T)/\sqrt m$ 控制。粗略估计 $w(\sqrt sB_1^n\cap B_2^n)\le\sqrt s\,w(B_1^n)\lesssim\sqrt{s\log n}$，得到

证明目标：证明 nuclear norm constrained recovery 的误差界。

完整证明：若 $\operatorname{rank}(X)\le r$ 且 $\|X\|_F\le1$，则 $\|X\|_*\le\sqrt r$。取 feasible set $T=\sqrt r B_*\cap B_F$。Theorem 9.4.4 的矩阵版给出误差由 $w(T)/\sqrt m$ 控制。Gaussian width 满足 $w(T)\lesssim\sqrt{rd}$，因为 nuclear norm ball 的 polar 是 operator norm ball，而 Gaussian matrix 的 operator norm 期望为 $O(\sqrt d)$。因此 $\mathbb E\|\hat X-X\|_F\lesssim\sqrt{rd/m}$。

证明目标：用 escape theorem 证明 basis pursuit 精确恢复。

完整证明：设 $x$ 为 $s$-sparse，$\hat x$ 为 $\ell^1$ minimization 解，$h=\hat x-x$。若 $h\ne0$，则 $Ah=0$ 且 $\|x+h\|_1\le\|x\|_1$。Lemma 9.5.2 和 Lemma 9.5.3 说明归一化误差 $h/\|h\|_2$ 属于一个 approximate sparse spherical set $S$，且 $w(S)^2\lesssim s\log(en/s)$。若 $m\ge CK^4s\log(en/s)$，escape theorem 给出 $\ker A$ 与 $S$ 不相交。由于 $h/\|h\|_2\in\ker A\cap S$ 会矛盾，故 $h=0$，精确恢复成立。

证明目标：证明误差在 support 外的 $\ell^1$ 质量受 support 内控制。

完整证明：令 $S=\operatorname{supp}(x)$。由 $\ell^1$ 最小化，$\|x+h\|_1\le\|x\|_1$。分解 support 得

三角不等式给出 $\|x_S+h_S\|_1\ge\|x_S\|_1-\|h_S\|_1$，代入得到 $\|h_{S^c}\|_1\le\|h_S\|_1$。

证明目标：由 support inequality 推出误差属于 approximate sparse set。

完整证明：由 Lemma 9.5.2，$\|h\|_1=\|h_S\|_1+\|h_{S^c}\|_1\le2\|h_S\|_1$。Cauchy-Schwarz 给出 $\|h_S\|_1\le\sqrt s\|h_S\|_2\le\sqrt s\|h\|_2$。因此 $\|h\|_1\le2\sqrt s\|h\|_2$。若归一化 $\|h\|_2=1$，则 $h\in2\sqrt sB_1^n\cap S^{n-1}$，这就是 approximate sparse spherical set。

证明目标：由 RIP 推出 $\ell^1$ exact recovery。

完整证明：令 $h=\hat x-x\in\ker A$，$S=\operatorname{supp}(x)$。按系数大小把 $S^c$ 分块，每块大小约为 $\lambda s$。Cone inequality 给出 $\|h_{S^c}\|_1\le\|h_S\|_1$，从而 tail blocks 的 $\ell^2$ 总量被 $\|h_S\|_2$ 控制。RIP 对 $S$ 与首个 tail block 的并集给出 $\|Ah_{S\cup T_1}\|_2$ 的下界，对剩余 tail blocks 给出上界。由于 $Ah=0$，两边比较并利用 $\lambda>(\beta/\alpha)^2$，得到 $\|h_S\|_2=0$，进而 $h=0$。

证明目标：证明 subgaussian matrices 在 sparse set 上满足 RIP。

完整证明：令 $T=S_{n,s}=\{x:\|x\|_0\le s,\|x\|_2=1\}$。Matrix deviation 的高概率版本给出 $\sup_{x\in T}|\|Ax\|_2-\sqrt m|$ 由 $K^2(w(T)+u)$ 控制。Gaussian width 满足 $w(T)\lesssim\sqrt{s\log(en/s)}$。若 $m\ge CK^4s\log(en/s)$，取 $u\asymp\sqrt m/K^2$ 的小常数倍即可使偏差小于 $\varepsilon\sqrt m$，从而得到所有 sparse vectors 上的 norm preservation，即 RIP。

证明目标：证明 $f(Ax)$ 的 uniform centered deviation。

完整证明：定义 $Z_x=f(Ax)-\mathbb Ef(Ax)$。Theorem 9.6.4 证明 $\|Z_x-Z_y\|_{\psi_2}\le Cb\|x-y\|_2$。并且 $Z_0=0$。对 $Z_x$ 和 $-Z_x$ 用 Talagrand comparison 的几何形式，得到 $\mathbb E\sup_{x\in T}|Z_x|\le Cb\gamma(T)$。

证明目标：证明 $Z_x=f(Ax)-\mathbb Ef(Ax)$ 的 $\psi_2$ 增量。

完整证明：先设 $b=1$ 且 $\|x\|_2=\|y\|_2=1$。令 $u=(x+y)/2$、$v=(x-y)/2$，则 $u\perp v$，所以 Gaussian vectors $Au$ 与 $Av$ 独立。条件在 $a=Au$ 上，$Ax=a+Av$ 与 $Ay=a-Av$。函数 $z\mapsto f(a+\|v\|_2z)$ 是 $\|v\|_2$-Lipschitz，因为 subadditivity 给出 $f(r)-f(s)\le f(r-s)\le\|r-s\|_2$。Gaussian concentration 给出 $f(a+Av)$ 与其条件期望的 $\psi_2$ 范数至多 $C\|v\|_2$；$f(a-Av)$ 同样成立且条件期望相同。相减后得到 $\|f(Ax)-f(Ay)\|_{\psi_2}\le C\|x-y\|_2$。一般 $x,y$ 按 Theorem 9.1.2 的齐次化步骤处理；恢复 $b$ 得结论。

证明目标：由 general matrix deviation 推出 two-sided Chevet。

完整证明：取 support function $f(z)=\sup_{y\in S}\langle z,y\rangle$。它 positive homogeneous、subadditive，且 $f(z)\le\operatorname{rad}(S)\|z\|_2$。Theorem 9.6.3 给出

由于 $Ax\sim\|x\|_2g$，$\mathbb Ef(Ax)=\|x\|_2\mathbb E\sup_{y\in S}\langle g,y\rangle=\|x\|_2w(S)$。代入即得。

证明目标：证明 $\operatorname{conv}(AT)$ 夹在两个 Euclidean balls 之间。

完整证明：把 Theorem 9.7.1 应用于 $A^{\mathsf T}$，并取 $S=S^{m-1}$，得到

Markov inequality 给出概率至少 $0.99$ 的同阶界。于是对所有单位 $y$，support function $h_{\operatorname{conv}(AT)}(y)$ 位于 $w(T)\pm C\sqrt m\operatorname{rad}(T)$。Support function 与 convex body inclusion 的对偶关系给出

其中 $r_\pm=w(T)\pm C\sqrt m\operatorname{rad}(T)$。

证明目标：证明 $\|x-\bar y\|_2+\|\bar y-y\|_2\le\sqrt2\|x-y\|_2$。

完整证明：设 $\|x\|_2=1$，$r=\|y\|_2\ge1$，$\bar y=y/r$，并令 $\theta$ 为 $x$ 与 $\bar y$ 的夹角。则

而 $\|x-\bar y\|_2^2=2(1-\cos\theta)$、$\|\bar y-y\|_2=r-1$。由 Cauchy-Schwarz，

因为 $r\ge1$ 使 $2r(1-\cos\theta)\ge2(1-\cos\theta)$。

证明目标：计算 $T=\Sigma^{1/2}S^{n-1}$ 的两个量。

完整证明：半径为 $\sup_{\|x\|=1}\|\Sigma^{1/2}x\|_2=\|\Sigma\|^{1/2}$。Gaussian complexity 满足

证明目标：说明 exact recovery 等价于 null space 避开 tangent cone。

完整证明：若存在非零 $h\in\ker A$ 使 $x+h$ 仍在 $\ell^1$ ball 中，则 $A(x+h)=Ax$ 且 $\ell^1$ minimization 至少有另一个可行解，精确性失败。反过来，若精确性失败，则 $\hat x\ne x$ 且 $h=\hat x-x\in\ker A$，并且 $\|x+h\|_1\le\|x\|_1$，所以 $h$ 属于从 $x$ 指向 $\ell^1$ ball 的 tangent cone。归一化后就是 cone 的 spherical part 与 null space 相交。

证明目标：证明单位向量 $x,y$ 给出的 $u,v$ 正交。

完整证明：计算内积：

因此 Gaussian matrix 作用后 $Au$ 与 $Av$ 是 independent Gaussian vectors。

证明目标：说明 $h_K(y)$ 夹住 Euclidean norm 等价于 $K$ 夹在 Euclidean balls 中。

完整证明：若 $K\subset r_+B_2$，则 $h_K(y)=\sup_{x\in K}\langle x,y\rangle\le r_+\|y\|_2$。若 $r_-B_2\subset K$，则 $h_K(y)\ge\sup_{\|x\|\le r_-}\langle x,y\rangle=r_-\|y\|_2$。反向使用 separation theorem：若某点 $z\in K$ 满足 $\|z\|>r_+$，取 $y=z$ 得 $h_K(y)>r_+\|y\|$；若 $r_-B_2$ 中有点不在 $K$，可用 separating hyperplane 找到某个 $y$ 使 $h_K(y)<r_-\|y\|$。

证明目标：证明 Figure 9.1 的几何不等式。

完整证明：见 [隐藏验证](#proof-check-9-1-reverse-triangle)。核心是把 $\|x-y\|^2$ 写成 radial part $(\|y\|-1)^2$ 与 angular part，再用 Cauchy-Schwarz 合并两段路径长度。

证明目标：由 Theorem 9.1.1 推出 centered version。

完整证明：对任意 $x$，

对 $x\in T$ 取 supremum 和期望，第二项由 Jensen 和 Theorem 9.1.1 控制，得到同阶 $CK^2\gamma(T)$。

证明目标：推出 $\|Ax\|_2^2-m\|x\|_2^2$ 的上界。

完整证明：令 $\Delta_x=\|Ax\|_2-\sqrt m\|x\|_2$。则

上确界由 $\sup|\Delta_x|^2+2\sqrt m\,\operatorname{rad}(T)\sup|\Delta_x|$ 控制。对期望用 Theorem 9.1.1 及高概率版本积分得到 $\mathbb E\sup|\Delta_x|^2\le CK^4\gamma(T)^2$，并得到题设 bound。

证明目标：去掉 isotropic 假设。

完整证明：写 $B_i=\Sigma^{1/2}A_i$，其中 $A_i$ 在 $\Sigma$ 的 range 上 isotropic。则 $\|Bx\|_2=\|A(\Sigma^{1/2}x)\|_2$，而 deterministic target 为 $\sqrt m\|\Sigma^{1/2}x\|_2$。把 isotropic matrix deviation 应用于集合 $\Sigma^{1/2}T$，得到

证明目标：把 matrix deviation 推广到函数类的 $L^2$ norm。

完整证明：把每个 $f\in\mathcal F$ 映到向量 $(f(X_1),\dots,f(X_m))$。目标偏差为 empirical $L^2$ norm 与 population $L^2$ norm 的差。假设给出过程在 metric $d(f,g)$ 下的 subgaussian increments；按 Theorem 9.1.2 的证明，norm deviation process 具有 $CK^2d(f,g)/\sqrt m$ 尺度的 increments。Talagrand comparison 给出

线性函数类 $f_x(z)=\langle z,x\rangle$ 且 $x\in T\subset S^{n-1}$ 时回到 Theorem 9.1.1。

证明目标：证明 Haar 随机正交投影的 matrix deviation 版本：

完整证明：先处理单位球面上的增量。令 $P=U^\mathsf T P_mU$，其中 $U$ 为 Haar 正交矩阵，$P_m$ 是前 $m$ 个坐标的正交投影。对固定单位向量 $x,y$，函数

在正交群上是 $C\|x-y\|_2$-Lipschitz。由正交群上的 concentration inequality，

这一步也可按原书提示直接验证：由旋转不变性令 $x=e_1$、$y=\sqrt{1-\varepsilon^2}e_1+\varepsilon e_2$，展开 $\|Px\|_2^2-\|Py\|_2^2$，主随机项由投影矩阵元素 $P_{12}$ 控制，而 $P_{12}$ 在 Haar 投影下具有 $O(1/\sqrt n)$ 的 subgaussian 尺度。

令

上一步给出 $\|Z_x-Z_y\|_{\psi_2}\le C\|x-y\|_2/\sqrt n$。对过程 $Z_x$ 和 $-Z_x$ 用 Talagrand comparison 的几何形式，得到

最后处理均值偏差。对固定 $x$，$\|Px\|_2/\|x\|_2$ 与随机球面点前 $m$ 个坐标长度同分布，其平方均值为 $m/n$，且方差尺度为 $O(1/n)$；因此

这里的 $\gamma(T)$ 是本书定义的 Gaussian complexity $\mathbb E\sup_{x\in T}|\langle g,x\rangle|$，因此 $\gamma(T)\ge c\sup_{x\in T}\|x\|_2$。所以均值项也被 $C\gamma(T)/\sqrt n$ 控制。合并随机中心化项与均值项，即得结论。

证明目标：证明 Proposition 9.2.1 的高概率版本。

完整证明：对 $T-T$ 使用 matrix deviation 高概率形式：

令 $P=A/\sqrt n$，取 $u=c\varepsilon\sqrt m/K^2$，并用 $w(T-T)\le2\sqrt n\,w_s(T)$。整理得到题设直径上界，概率为 $1-\exp(-c\varepsilon^2m/K^4)$。

证明目标：把 Proposition 9.2.1 改成真正随机子空间投影。

完整证明：用 Exercise 9.6 的 random projection deviation 代替 subgaussian matrix deviation。对差集 $T-T$ 应用该结果，得到 $\operatorname{diam}(PT)$ 与 $\sqrt{m/n}\operatorname{diam}(T)$ 的偏差由 $\gamma(T-T)/\sqrt n\asymp w_s(T)$ 控制。

证明目标：证明 Theorem 9.2.2 的 tail version。

完整证明：在 Theorem 9.2.2 的 proof 中，把 quadratic deviation 的 expectation version 换成 high-probability version。对 ellipsoid $T$，tail 参数 $u$ 把 $\gamma(T)^2$ 替换为 $\gamma(T)^2+u\operatorname{rad}(T)^2$，把 $\sqrt m\operatorname{rad}(T)\gamma(T)$ 替换为 $\sqrt m\operatorname{rad}(T)(\gamma(T)+\sqrt u\,\operatorname{rad}(T))$。代入 $\operatorname{rad}(T)^2=\|\Sigma\|$ 与 $\gamma(T)^2\le r\|\Sigma\|$，得到 $CK^4(\sqrt{(r+u)/m}+(r+u)/m)\|\Sigma\|$。

证明目标：用 matrix deviation 推出有限集 JL。

完整证明：对 normalized differences $T=\{(x-y)/\|x-y\|:x,y\in\mathcal X,x\ne y\}$ 应用 matrix deviation 高概率形式。该集合大小至多 $N^2$，所以 $\gamma(T)\le C\sqrt{\log N}$。若 $m\ge C K^4\varepsilon^{-2}\log N$，则所有差向量满足 $\left|\|A z\|_2/\sqrt m-1\right|\le\varepsilon$。这等价于 $Q=A/\sqrt m$ 是 $\varepsilon$-isometry。

证明目标：说明 infinite set 不能期待 uniform relative error。

完整证明：若 $\mathcal X$ 含有一条线段或有聚点，则存在任意接近的 $x,y$。对任意非等距线性映射 $Q$，在某些极小差向量上相对误差不会因距离缩小而改善。若要求所有非零差向量的 relative error 很小，就要求 $Q$ 在 $\mathcal X-\mathcal X$ 的 span 上近等距；当该 span 维度超过 $m$ 时不可能。因此无限集自然得到 additive error。

证明目标：证明所有 affine sections 的 $M^*$ bound。

完整证明：若 $x,y\in T\cap(z+\ker A)$，则 $x-y\in T-T$ 且 $A(x-y)=0$。因此任意 affine section 的直径都被 $\sup\{\|h\|_2:h\in T-T,Ah=0\}$ 控制。对 $T-T$ 重复 Theorem 9.3.1 证明，即得 $\mathbb E\max_z\operatorname{diam}(T\cap(z+\ker A))\le CK^2w(T)/\sqrt m$。

证明目标：证明 $M^*$ bound 的 tail version。

完整证明：在 affine proof 中使用 matrix deviation 高概率形式作用于 $T-T$。得到概率至少 $1-2e^{-u^2}$ 的界

对所有 $z$ 同时成立。

证明目标：若 $E$ 是随机 $k$ 维子空间且 $1\le k\le0.99n$，证明

完整证明：先证上界。设 $m=n-k$ 为余维，则 $m\ge0.01n$。对 $T=B_p^n$ 使用 $M^*$ bound，

由对偶性，$w(B_p^n)=\mathbb E\|g\|_{p'}$，其中 $1/p+1/p'=1$。Gaussian $p'$-范数的矩估计给出 $\mathbb E\|g\|_{p'}\asymp_p n^{1/p'}$。因此

再证下界。随机子空间 $E$ 中取一条 Haar 随机直线 $L=\operatorname{span}(u)$，其方向 $u$ 在 $S^{n-1}$ 上均匀。因此

写 $u=g/\|g\|_2$，则

以正概率同时有 $\|g\|_2\ge c\sqrt n$ 且 $\|g\|_p\le C_p n^{1/p}$，所以

上下界合并即得。几何解释也随之清楚：当 $p\le2$ 时，$B_p^n$ 的最大 Euclidean 内球半径是 $n^{1/2-1/p}$；当 $p\ge2$ 时，$B_p^n$ 的 Euclidean 外接半径是同一尺度。随机大维截面看到的正是这个 Euclidean 尺度。

证明目标：说明 escape theorem 中 $m\gtrsim w(T)^2$ 的采样阈值一般不能改进。

完整证明：固定一个 $d$ 维线性子空间 $F\subset\mathbb R^n$，令 $T=S^{n-1}\cap F$。则

令 $E=\ker A$ 为随机余维 $m$ 子空间。无论 $E$ 是否随机，都有线性代数维数下界

如果 $m<d$，则 $E\cap F$ 含有非零向量，归一化后得到 $T\cap E\ne\varnothing$。也就是说，当 $m<w(T)^2$ 的常数倍时，escape 结论必然失败。取 $d$ 与 $m$ 同阶即可说明 Theorem 9.3.4 的 $w(T)^2$ 阈值在一般情形下是 sharp 的。

证明目标：证明存在旋转使 $UT$ 避开有限点集 $\mathcal X$。

完整证明：随机取 Haar rotation $U$。对固定 $x\in\mathcal X$，$U^{-1}x$ 在球面均匀分布，所以 $\mathbb P\{x\in UT\}=\sigma_{n-1}(T)<1/N$。Union bound 给出 $\mathbb P\{UT\cap\mathcal X\ne\varnothing\}<1$。因此存在一个旋转满足 $UT\cap\mathcal X=\varnothing$。

证明目标：把 Theorem 9.4.4 的一阶误差界升级为 mean squared error。

完整证明：设 $h=\hat x-x$。和 Theorem 9.4.4 一样，$h$ 属于某个 affine section 的差集，因此 high-probability $M^*$ bound 给出：对所有 $u\ge0$，以概率至少 $1-2e^{-u^2}$，

令 $a=CK^2w(T)/\sqrt m$，$b=CK^2\operatorname{diam}(T)/\sqrt m$。上式等价于 $\mathbb P\{\|h\|_2>a+bu\}\le2e^{-u^2}$。由 tail integration，

若 $T$ 已按半径或直径为常数归一化，这就是对应的 MSE 形式；一般尺度由同一个公式保留。

证明目标：把 constrained recovery 写成 norm minimization。

完整证明：若 $T$ 是 norm unit ball，且真实 $x$ 满足 $\|x\|_T\le1$，则 program $\min\|x'\|_T$ subject to $Ax'=y$ 的解 $\hat x$ 满足 $\|\hat x\|_T\le\|x\|_T\le1$，所以 $\hat x,x\in T$ 且 $A\hat x=Ax$。直接应用 Theorem 9.4.4。

证明目标：证明 noisy constrained recovery bound。

完整证明：最优性给出 $\|A\hat x-y\|_2\le\|Ax-y\|_2=\|w\|_2$。因此 $\|A(\hat x-x)\|_2\le2\|w\|_2$。Matrix deviation 在 $T-T$ 上给出 $\|Ah\|_2\ge\sqrt m\|h\|_2-CK^2w(T)$。合并并取期望得 $\mathbb E\|h\|_2\lesssim(K^2w(T)+\|w\|_2)/\sqrt m$。

证明目标：证明 penalized least squares 在 $\lambda\asymp\|w\|_2^2/\|x\|_T$ 时满足

完整证明：记 $R=\|x\|_T$，$h=\hat x-x$。若 $R=0$，结论退化为纯噪声情形，按同样论证去掉 $Rw(T)$ 项即可。下面设 $R>0$，并取 $\lambda=c\|w\|_2^2/R$ 到常数因子。由最优性，

因此 $\|\hat x\|_T\le C R$，且 $\|A\hat x-y\|_2\le C\|w\|_2$。由 $y=Ax+w$，

同时 $\|h\|_T\le\|\hat x\|_T+\|x\|_T\le CR$，所以 $h\in CR\,T$，其中 $T$ 是该 norm 的单位球。对集合 $CR\,T$ 使用 matrix deviation，得到期望意义下的 uniform lower bound

于是

两边除以 $\sqrt m$ 即得结论。

证明目标：把 Exercise 9.20 专门化到 $\ell^1$ norm。

完整证明：若 $x$ 为 $s$-sparse，则 $\|x\|_1\le\sqrt s\|x\|_2$。Exercise 9.20 中 $T=B_1^n$，但有效集合缩放到 $\|x\|_1B_1^n$。Gaussian width 为 $\|x\|_1w(B_1^n)\lesssim\sqrt{s\log n}\|x\|_2$。归一化 $\|x\|_2\le1$ 后得到 $\mathbb E\|\hat x-x\|_2\lesssim(K^2\sqrt{s\log n}+\|w\|_2)/\sqrt m$。

证明目标：证明 general position 下唯一性与已知 support 的求解。

完整证明：若两个 $s$-sparse 解 $x,x'$ 满足 $Ax=Ax'$，则 $h=x-x'$ 是 $2s$-sparse 且在 $\ker A$ 中。General position 假设任意 $2s$ 列线性无关；当 $m\ge2s$ 时，这迫使 $h=0$。若 support 已知为 $S$，只需解 $A_Sx_S=y$ 的最小二乘或线性方程；$A_S$ 满列秩时解唯一且可高效计算。

证明目标：说明 $\ell^0$ 与 $0<p<1$ 不是 norm，并证明极限。

完整证明：$\|2x\|_0=\|x\|_0$，不满足 norm 的齐次性。对 $0<p<1$，unit ball 非凸，例如 $(1,0)$ 与 $(0,1)$ 在 ball 中，但中点的 $p$-quasi norm 可超过 $1$，三角不等式失败。最后，若 $x_i\ne0$，则 $|x_i|^p\to1$；若 $x_i=0$，则 $|x_i|^p=0$。有限求和后 $\lim_{p\to0+}\|x\|_p^p=\#\{i:x_i\ne0\}=\|x\|_0$。

证明目标：把 sparse recovery 从 exactly sparse 推广到 approximately sparse。

完整证明：先看 exactly sparse。若 $x$ 是 $s$-sparse，则 $\|x\|_1\le\sqrt s\|x\|_2$。$\ell^1$ minimization 的解 $\hat x$ 满足 $\|\hat x\|_1\le\|x\|_1$，所以 $x,\hat x$ 都属于 $\sqrt s\|x\|_2B_1^n$。对该集合应用 constrained recovery，并用 $w(B_1^n)\lesssim\sqrt{\log n}$，得到

更精细地用 Exercise 9.26 的 truncated sparse hull，可把 $\log n$ 改成 $\log(en/s)$。

对 approximately sparse 的版本，令 $x_s$ 为 $x$ 的最佳 $s$-term approximation，$r=x-x_s$。把观测写成

即把 $Ar$ 视为噪声。使用带噪约束版本：在 $\|z\|_1\le\|x_s\|_1$ 中最小化 residual，得到

由于行各向同性，$\mathbb E\|Ar\|_2\le\sqrt m\|r\|_2$。对最佳 $s$-term tail，按坐标大小分块有 $\|r\|_2\le \|r\|_1/\sqrt s$。因此

这就是 approximately sparse recovery：第一项是估计 $s$-sparse 主体的随机测量误差，第二项是不可避免的稀疏近似误差。

证明目标：证明 $\operatorname{conv}(S_{n,s})\subset T_{n,s}\subset2\operatorname{conv}(S_{n,s})$。

完整证明：第一包含来自 convexity：$S_{n,s}$ 中向量满足 $\|x\|_1\le\sqrt s$ 且 $\|x\|_2\le1$，所以其 convex hull 在 $T_{n,s}$ 中。反向，取 $x\in T_{n,s}$，按坐标绝对值每 $s$ 个一组分块 $I_j$。有 $\sum_{j\ge1}\|x_{I_j}\|_2\le\|x_{I_1}\|_2+s^{-1/2}\sum_{j\ge2}\|x_{I_{j-1}}\|_1\le1+s^{-1/2}\|x\|_1\le2$。每个非零 $x_{I_j}/\|x_{I_j}\|_2$ 属于 $S_{n,s}$，所以 $x$ 是这些点的非负组合，总系数至多 $2$，得到第二包含。

证明目标：改进 sparse recovery 的 logarithmic factor。

完整证明：由 Exercise 9.25，$w(T_{n,s})\le2w(S_{n,s})$。对 $S_{n,s}$，按 support union bound：每个 support 上 width 为 $\sqrt s$，support 数为 $\binom ns$，最大值估计给出 $w(S_{n,s})\le C\sqrt{s\log(en/s)}$。代入 constrained recovery 得 $m\gtrsim s\log(en/s)$ 的改进界。

证明目标：证明 sparse set width 的上下界。

完整证明：上界见 Exercise 9.26。下界取 $\binom ns$ 个 support 中的 packing，或取前 $s$ 大 Gaussian 坐标：$\sup_{x\in S_{n,s}}\langle g,x\rangle=(\sum_{i=1}^s g_{(i)}^2)^{1/2}$，其中 $g_{(i)}$ 为绝对值降序。order statistics 给出期望 $\gtrsim\sqrt{s\log(en/s)}$。convexified set 与 $S_{n,s}$ 同阶由 Exercise 9.25 得到。

证明目标：把 $M^*$ bound 对 $B_1^n$ 随机切片给出的粗略 $\sqrt{\log n/m}$ 改进为

其中 $E=\ker A$ 是随机余维 $m$ 子空间。

完整证明：记 $T=B_1^n$，并对 $0<\rho\le1$ 定义截断 cross-polytope

第一步是把全局半径问题化为截断半径问题。若某个 $\delta\le\rho$ 满足 $\operatorname{rad}(T_\rho\cap E)\le\delta$，则 $\operatorname{rad}(T\cap E)\le\delta$。证明如下：若存在 $x\in T\cap E$ 且 $\|x\|_2>\delta$，分两种情况。若 $\|x\|_2\le\rho$，则 $x\in T_\rho\cap E$，与截断半径界矛盾；若 $\|x\|_2>\rho$，令 $y=\rho x/\|x\|_2$，则 $y\in E$、$\|y\|_2=\rho>\delta$，且 $\|y\|_1=(\rho/\|x\|_2)\|x\|_1\le1$，所以 $y\in T_\rho\cap E$，仍矛盾。

第二步估计 $T_\rho$ 的 Gaussian width。设 $s=\lceil\rho^{-2}\rceil$。由于

Exercise 9.26 给出

这里最后一步用 $s\asymp\rho^{-2}$，并把 ceiling 带来的常数吸收进绝对常数中。

第三步使用高概率 $M^*$ bound。对 $T_\rho$ 有 $\operatorname{rad}(T_\rho)\le\rho$，因此 Exercise 9.13 型 tail 形式给出

以概率至少 $1-2e^{-u^2}$ 成立。选择 $u=c\sqrt m\,\rho$。只要

并取常数 $C_0$ 足够大，就有

于是事件上 $\operatorname{rad}(T_\rho\cap E)\le\rho/2$，由第一步推出 $\operatorname{rad}(T\cap E)\le\rho/2$。

最后选择参数。令

其中 $A$ 是足够大的绝对常数。若 $\rho>1$，则右侧目标已经是常数阶，结论由 $\operatorname{diam}(B_1^n)\le2$ 平凡成立。下面假设 $\rho\le1$。此时

所以 $m\rho^2=AL$ 可以压过 $\log(en\rho^2)$。由上一步，除概率至多 $2e^{-c m\rho^2}\le2e^{-cAL}$ 的坏事件外，$\operatorname{rad}(T\cap E)\le\rho/2$。坏事件上只用 $\operatorname{rad}(T\cap E)\le1$，得到

乘以 $2$ 把半径换成直径，即得

这个证明的核心是截断、稀疏凸包宽度估计与 $M^*$ tail bound 的自洽参数选择：选 $\rho$ 时必须让截断切片先落回 $\rho B_2^n$ 内，再把这个半径传回整个 $B_1^n$。

证明目标：把 Corollary 9.4.11 扩展到 nuclear norm minimization、approximately low-rank 和矩形矩阵。

完整证明：(a) 若真实矩阵 $X$ 满足 $\operatorname{rank}(X)\le r$ 且 $\|X\|_F\le1$，则 $\|X\|_*\le\sqrt r$。nuclear norm minimization 的解 $\hat X$ 满足 $\|\hat X\|_*\le\|X\|_*\le\sqrt r$。因此 $X,\hat X$ 都落在 $\sqrt r B_*$ 中，且 $A(\hat X-X)=0$。对 $T=\sqrt r B_*$ 应用 constrained recovery，

由于 nuclear norm ball 的 polar 是 operator norm ball，

在 $d\times d$ 情形成立，故得到 $\mathbb E\|\hat X-X\|_F\lesssim\sqrt{rd/m}$。

(b) 若 $X$ 不是 rank-$r$，令 $X_r$ 为最佳 rank-$r$ approximation，$R=X-X_r$。把观测写成 $y_i=\langle A_i,X_r\rangle+\langle A_i,R\rangle$，把尾部看成噪声。由带噪 constrained recovery，

各向同性给出 $\mathbb E\|A(R)\|_2\le\sqrt m\|R\|_F$，而奇异值尾部满足 $\|R\|_F\le\|R\|_*/\sqrt r$。于是误差增加

(c) 对 $d_1\times d_2$ 矩阵，仍有 $w(\sqrt r B_*)=\sqrt r\,\mathbb E\|G\|$，而 Gaussian 矩阵 operator norm 满足 $\mathbb E\|G\|\lesssim\sqrt{d_1}+\sqrt{d_2}$。因此

代入 constrained recovery 得

approximately low-rank 的矩形版本同理再加 $\|X-X_r\|_*/\sqrt r$。

证明目标：解释 Theorem 9.5.1 的 tangent cone 图像。

完整证明：见 [隐藏验证](#proof-check-9-5-tangent-cone)。证明说明 basis pursuit 成功当且仅当 $\ker A$ 不包含任何从 $x$ 进入 $\ell^1$ ball 的非零方向；归一化后，就是 $\ker A$ 避开 tangent cone 的 spherical part。

证明目标：把 Theorem 9.5.1 的 noiseless exact sparse recovery 改成 noisy measurements $y=Ax+w$ 的稳定恢复。

完整证明：设已知噪声上界 $\eta\ge\|w\|_2$，考虑 basis pursuit denoising：

真实 $x$ 可行，所以解 $\hat x$ 满足 $\|\hat x\|_1\le\|x\|_1$。令 $h=\hat x-x$，若 $S=\operatorname{supp}(x)$ 且 $|S|=s$，与 Lemma 9.5.2 同样的三角不等式给出 cone constraint

因此 $\|h\|_1\le2\sqrt s\|h\|_2$，也就是说 $h/\|h\|_2$ 落在 approximate sparse spherical set

另一方面，$\hat x$ 和 $x$ 都满足噪声约束，所以

当 $m\ge CK^4s\log(en/s)$ 时，matrix deviation 或 RIP 证明给出 uniform lower bound：对所有 $u\in T_s$，$\|Au\|_2\ge c\sqrt m$，概率至少 $1-2e^{-cm/K^4}$。若 $h\ne0$，代入 $u=h/\|h\|_2$ 得

从而

若 $x$ 只是 approximately sparse，把 $S$ 取为最大 $s$ 个坐标集合，则 cone constraint 变为 $\|h_{S^c}\|_1\le\|h_S\|_1+2\|x_{S^c}\|_1$，同一论证额外产生 tail 项 $C\|x_{S^c}\|_1/\sqrt s$。

证明目标：证明 NSP 等价于所有 $s$-sparse exact recovery，并证明随机矩阵满足。

完整证明：若 NSP 成立，任取 $s$-sparse $x$ 和非零 $h\in\ker A$，令 $S=\operatorname{supp}(x)$。则 $\|x+h\|_1\ge\|x\|_1-\|h_S\|_1+\|h_{S^c}\|_1>\|x\|_1$，故 $x$ 是唯一 minimizer。反向，若 NSP 失败，存在 $h$ 与 $S$ 使 $\|h_S\|_1\ge\|h_{S^c}\|_1$，取 $x=-h_S$，则 $x+h=h_{S^c}$ 也是可行且 $\ell^1$ 不大，唯一恢复失败。随机矩阵部分由 Theorem 9.5.1 对所有 supports 的 uniform statement 给出。

证明目标：证明 Grassmannian projections 的 sparse RIP 与 exact recovery。

完整证明：对 sparse set $S_{n,s}$ 使用 Exercise 9.6 的 random projection deviation。若 $m\gtrsim s\log(en/s)$，则所有 $s$-sparse unit vectors 满足 $\|Px\|_2\approx\sqrt{m/n}$。归一化 $\sqrt{n/m}P$ 后得到 RIP。再应用 Theorem 9.5.6 或 nullspace property，得到 random projections 下的 exact recovery。

证明目标：证明 $f(x)-f(y)\le f(x-y)$。

完整证明：由 subadditivity，$f(x)=f((x-y)+y)\le f(x-y)+f(y)$。移项即得 $f(x)-f(y)\le f(x-y)$。

证明目标：推广 Theorem 9.6.3 到 $N(0,\Sigma)$ rows。

完整证明：写 $A=G\Sigma^{1/2}$，其中 $G$ 为 standard Gaussian matrix。于是 $f(Ax)=f(G(\Sigma^{1/2}x))$。对集合 $\Sigma^{1/2}T$ 应用 Theorem 9.6.3，得到 $Cb\gamma(\Sigma^{1/2}T)$。

证明目标：证明 Theorem 9.6.3 的 tail version。

完整证明：Theorem 9.6.4 给出 increments，generic chaining high-probability 或 Talagrand comparison tail 给出

概率至少 $1-2e^{-u^2}$。

证明目标：用 Theorem 9.6.3 得到一般 norm 的 JL。

完整证明：令 $f=\|\cdot\|$，假设 $f(z)\le b\|z\|_2$。对 normalized differences $T$ 应用 general deviation：$f(Az)$ 同时接近 $\mathbb Ef(Az)=\|z\|_2\mathbb Ef(g)$。若 $T$ 来自 $N$ 点集，则 $\gamma(T)\le C\sqrt{\log N}$。当 $m$ 或 norm 参数使 $b\sqrt{\log N}$ 小于 $\varepsilon\mathbb Ef(g)$ 时，得到一般 norm 中的 JL embedding。

证明目标：证明 Gaussian map 到 $\ell^1$ 的 JL。

完整证明：取 $f(z)=\|z\|_1$，则 $b=\sqrt m$，且 $\mathbb E\|g\|_1=m\sqrt{2/\pi}$。对 normalized differences 应用 Theorem 9.6.3 的高概率版本，偏差为 $C\sqrt m\sqrt{\log N}$。除以 $m\sqrt{2/\pi}$ 后相对误差为 $C\sqrt{\log N/m}$。若 $m\ge C(\varepsilon)\log N$，则 $Q=\sqrt{\pi/2}\,A/m$ 满足题设双边界。

证明目标：证明 Gaussian map 到 $\ell^\infty$ 的 embedding。

完整证明：取 $f(z)=\|z\|_\infty$，则 $b=1$，且 $\mathbb E\|g\|_\infty\asymp\sqrt{\log m}$。对 $N^2$ 个 normalized differences 应用 general deviation，偏差为 $C\sqrt{\log N}$。要使其小于 $\varepsilon\sqrt{\log m}$，需 $\log m\ge C(\varepsilon)\log N$，即 $m\ge N^{C(\varepsilon)}$。取 $Q=C(\log m)^{-1/2}A$ 得题设结论。

证明目标：证明 support function 与 Euclidean ball inclusion 等价。

完整证明：见 [隐藏验证](#proof-check-9-7-support-duality)。关键是 $h_{\operatorname{conv}(V)}=h_V$，以及 closed convex body 可由其所有 supporting halfspaces 表示。

证明目标：给 Theorem 9.7.2 加入 tail 参数，得到随机 Gaussian projection 后凸包夹在两个 Euclidean balls 之间的高概率版本。

完整证明：令 $A$ 为 $m\times n$ Gaussian matrix。对任意 $y\in S^{m-1}$，support function 满足

由于 $A^\top y\sim N(0,I_n)$，有 $\mathbb Eh_{AT}(y)=w(T)$。Theorem 9.7.1 的高概率版本应用到索引集 $S^{m-1}$ 给出：对所有 $u\ge0$，以概率至少 $1-2e^{-u^2}$，

记

如果 $r_-<0$，内含球半径按 $0$ 理解。对每个 $y\in S^{m-1}$，上式等价于

support function 的对偶刻画说明 $h_{\operatorname{conv}(AT)}=h_{AT}$，并且对闭凸集 $K$，$K\subset r_+B_2^m$ 等价于 $h_K(y)\le r_+$ 对所有 $y\in S^{m-1}$，而 $r_-B_2^m\subset K$ 等价于 $h_K(y)\ge r_-$ 对所有 $y$。因此

以概率至少 $1-2e^{-u^2}$ 成立。这就是 Theorem 9.7.2 的 high-probability 形式。

证明目标：证明 $n$ 个 Gaussian points 的 convex hull 近似 Euclidean ball。

完整证明：令 $T=\{e_1,\dots,e_n\}\subset\mathbb R^n$，Gaussian matrix $A$ 的列就是 $g_1,\dots,g_n$。有 $w(T)=\mathbb E\max_i g_i\asymp\sqrt{\log n}$，$\operatorname{rad}(T)=1$。Theorem 9.7.2 给出 $\operatorname{conv}\{g_i\}$ 夹在半径 $\sqrt{\log n}\pm C\sqrt m$ 的 balls 中。若 $m\le c\log n$ 且 $c$ 小，误差项被吸收，得到半径 $\asymp\sqrt{\log n}$ 的近圆性。

证明目标：把 Gaussian projection 版 Dvoretzky-Milman 改成真正的随机正交投影 $P:\mathbb R^n\to E$，其中 $E$ 在 Grassmannian 上均匀。

完整证明：令 $G$ 为 $m\times n$ standard Gaussian matrix。它的 row space 在 Grassmannian $G_{n,m}$ 上均匀分布。把 $G$ 写成极分解

其中 $P$ 是到随机 $m$ 维 row space 的正交投影再识别到 $\mathbb R^m$，$R=(GG^\top)^{1/2}$ 是 $\mathbb R^m$ 上的随机正定算子；$P$ 的方向与径向部分独立。Wishart 奇异值集中给出，当 $m\le c\varepsilon^2 n$ 时，以高概率

也就是说，$G T=R(PT)$ 与 $\sqrt n\,PT$ 只差一个 $(1\pm\varepsilon)$ 的线性畸变。

对 Gaussian projection $G$ 应用 Theorem 9.7.2 或 Exercise 9.41 的高概率版本，若 $m\le c\varepsilon^2 w(T)^2/\operatorname{rad}(T)^2$，则

用上面的奇异值比较把 $G T$ 除以 $\sqrt n$ 转换为 $PT$。由于 $w_s(T)=w(T)/\sqrt n$，并吸收两个 $(1\pm\varepsilon)$ 因子，得到

重新命名 $\varepsilon$，得到题设的 true random projection 版本：

其中 $B$ 是半径 $w_s(T)$ 的 Euclidean ball。