第 9 章精校翻译：集合上的随机矩阵偏差
第 9 章集合上的随机矩阵偏差
一个 $m\times n$ 随机矩阵会怎样作用在一般集合 $T\subset\mathbb R^n$ 上？第 9.1 节证明本章的核心结果：矩阵偏差不等式。随后我们把它应用到一系列高维问题中，其中既有前面已经见过的问题，也有新的问题。
第 9.2 节会快速推出随机矩阵的双边界、集合随机投影的更尖锐界、低维数据的协方差估计，以及 Johnson-Lindenstrauss 引理的无限集合版本。
第 9.3 节包含两个优雅结果：随机切片如何缩小高维集合，也就是 $M^*$ 界；以及随机子空间如何完全避开某些集合，也就是逃逸定理。
第 9.4-9.5 节把这些想法用于数据科学中的基础问题：学习结构化的高维线性模型。
第 9.6 节把矩阵偏差不等式推广到一般范数；第 9.7 节再用它强化 Chevet 不等式，并推出 Dvoretzky-Milman 定理。后者说明：高维集合的随机低维投影看起来近似圆。
习题会继续展开矩阵偏差和随机过程偏差界，例如 Exercise 9.5；也会进入高维估计方法，包括稀疏回归中的 Lasso，见 Exercises 9.20-9.21；还包括 Garnaev-Gluskin 定理关于 cross-polytope 的随机切片，见 Exercise 9.28；关于其他 $\ell^p$ 球的 Exercise 9.14；关于一般范数 Johnson-Lindenstrauss 引理的 Exercises 9.37-9.39，等等。
9.1 矩阵偏差不等式
取一个 $m\times n$ 随机矩阵 $A$，其行独立、各向同性且次高斯。范数集中（Theorem 3.1.1）告诉我们：对任意固定向量 $x\in\mathbb R^n$，近似
$$ \|Ax\|_2\approx \sqrt m\|x\|_2 \tag{9.1} $$
以高概率成立。
现在问一个更大的问题：是否可以让 (9.1) 同时对许多向量 $x\in\mathbb R^n$ 成立？为了量化“许多”，任取一个有界集合 $T\subset\mathbb R^n$，并要求该近似同时对所有 $x\in T$ 成立。结果表明，最大误差大约由 $\gamma(T)$ 控制；$\gamma(T)$ 是 $T$ 的高斯复杂度，它与第 7.5.3 节的高斯宽度密切相关。
令 $A$ 为 $m\times n$ 随机矩阵，其行 $A_i$ 独立、各向同性且次高斯。则对任意子集 $T\subset\mathbb R^n$，
$$ \mathbb E\sup_{x\in T}\left|\|Ax\|_2-\sqrt m\|x\|_2\right| \le CK^2\gamma(T), $$其中 $\gamma(T)$ 是高斯复杂度，$K=\max_i\|A_i\|_{\psi_2}$。
查看学习笔记：Theorem 9.1.1 完整证明证明计划是把
$$ Z_x=\|Ax\|_2-\sqrt m\|x\|_2 \tag{9.2} $$
看成由 $x\in\mathbb R^n$ 索引的随机过程，然后从 Talagrand 比较不等式（Corollary 8.5.8）推出结论。为此只需要检查这个随机过程具有次高斯增量。
令 $A$ 为 $m\times n$ 随机矩阵，其行 $A_i$ 独立、各向同性且次高斯。那么随机过程 (9.2) 具有次高斯增量：
$$ \|Z_x-Z_y\|_{\psi_2}\le CK^2\|x-y\|_2, \qquad x,y\in\mathbb R^n. \tag{9.3} $$这里 $K=\max_i\|A_i\|_{\psi_2}$。
查看学习笔记：Theorem 9.1.2 完整证明一旦 Theorem 9.1.2 成立，就把它代入 Talagrand 比较不等式（Corollary 8.5.8，更精确地说是 Exercise 8.37(a)），得到
$$ \mathbb E\sup_{x\in T}|Z_x| \le CK^2\gamma(T), $$
这正是 Theorem 9.1.1。因此剩下的任务只是证明 Theorem 9.1.2；这会容易一些，因为它只涉及固定的 $x,y$。
证明稍长，但思路是从简单情形逐步推广。
步骤 1：单位向量 $x$ 与零向量 $y$。 假设 $\|x\|_2=1$ 且 $y=0$。这时 (9.3) 变成
$$ \left\|\|Ax\|_2-\sqrt m\right\|_{\psi_2}\le CK^2. \tag{9.4} $$随机向量 $Ax\in\mathbb R^m$ 的坐标为 $\langle A_i,x\rangle$，它们独立、次高斯，并且由各向同性性有 $\mathbb E\langle A_i,x\rangle^2=1$。于是 (9.4) 直接来自范数集中（Theorem 3.1.1）。
步骤 2：单位向量 $x,y$ 与平方过程。 现在假设 $\|x\|_2=\|y\|_2=1$。此时 (9.3) 等价于
$$ \left\|\|Ax\|_2-\|Ay\|_2\right\|_{\psi_2} \le CK^2\|x-y\|_2. \tag{9.5} $$平方 $\ell^2$ 范数没有根号，更容易处理。直觉上，若 $\|Ax\|_2$ 和 $\|Ay\|_2$ 都大约为 $\sqrt m$，那么
$$ \begin{aligned} \|Ax\|_2^2-\|Ay\|_2^2 &=\bigl(\|Ax\|_2+\|Ay\|_2\bigr) \bigl(\|Ax\|_2-\|Ay\|_2\bigr)\\ &\approx \sqrt m\,\|x-y\|_2. \end{aligned} \tag{9.6} $$展开矩阵乘法：
$$ \|Ax\|_2^2-\|Ay\|_2^2 =\sum_{i=1}^m \left(\langle A_i,x\rangle^2-\langle A_i,y\rangle^2\right) =\sum_{i=1}^m \langle A_i,x+y\rangle\langle A_i,x-y\rangle. $$两边除以 $\|x-y\|_2$，记
$$ \Delta := \frac{\|Ax\|_2^2-\|Ay\|_2^2}{\|x-y\|_2} = \sum_{i=1}^m\langle A_i,u\rangle\langle A_i,v\rangle, \tag{9.7} $$其中
$$ u:=x+y,\qquad v:=\frac{x-y}{\|x-y\|_2}. $$目标是说明 $|\Delta|\lesssim\sqrt m$ 以高概率成立。式 (9.7) 是独立随机变量之和。每一项均值为零，因为
$$ \langle A_i,u\rangle\langle A_i,v\rangle = \frac{\langle A_i,x\rangle^2-\langle A_i,y\rangle^2}{\|x-y\|_2}, $$而各向同性性给出 $\mathbb E[\langle A_i,x\rangle^2-\langle A_i,y\rangle^2]=1-1=0$。并且这些项是次指数：由 Lemma 2.8.6 和 $A_i$ 的次高斯假设，
$$ \begin{aligned} \|\langle A_i,u\rangle\langle A_i,v\rangle\|_{\psi_1} &\le \|\langle A_i,u\rangle\|_{\psi_2} \|\langle A_i,v\rangle\|_{\psi_2}\\ &\le K\|u\|_2\cdot K\|v\|_2 \le 2K^2. \end{aligned} $$最后一步用了 $\|u\|_2\le\|x\|_2+\|y\|_2\le2$ 且 $\|v\|_2=1$。Bernstein 不等式（Theorem 2.9.1）于是给出：对任意 $0\le t\le\sqrt m$，
$$ \mathbb P\{|\Delta|\ge t\sqrt m\} \le 2\exp\left[ -c\min\left(\frac{t^2}{K^4},\frac{t\sqrt m}{K^2}\right) \right] \le 2\exp\left(-\frac{c_1t^2}{K^4}\right). \tag{9.8} $$步骤 3：单位向量 $x,y$ 与原始过程。 现在去掉平方，证明单位向量情形的 (9.5)。根据次高斯范数的定义，(9.5) 可写成尾界
$$ p(s):= \mathbb P\left\{ \frac{\left|\|Ax\|_2-\|Ay\|_2\right|}{\|x-y\|_2} \ge s \right\} \le 4\exp\left(-\frac{cs^2}{K^4}\right), \qquad s\gt 0. \tag{9.9} $$当 $s\le2\sqrt m$ 时，利用步骤 2。将定义 $p(s)$ 的不等式两边乘以 $\|Ax\|_2+\|Ay\|_2$，并用 $\Delta$ 的定义，得到
$$ p(s) \le \mathbb P\{|\Delta|\ge s\|Ax\|_2\}. $$由 (9.4)，$\|Ax\|_2$ 以高概率接近 $\sqrt m$。分成两种情形：常见事件 $\|Ax\|_2\ge\sqrt m/2$，以及罕见事件 $\|Ax\|_2\lt \sqrt m/2$。于是
$$ p(s)\le \mathbb P\left\{|\Delta|\ge\frac{s\sqrt m}{2}\right\} + \mathbb P\left\{\|Ax\|_2\lt \frac{\sqrt m}{2}\right\} =:p_1(s)+p_2(s). $$步骤 2 控制 $p_1$，步骤 1 控制 $p_2$，合起来得到 (9.9)。
当 $s\gt 2\sqrt m$ 时，由三角不等式
$$ \left|\|Ax\|_2-\|Ay\|_2\right| \le \|A(x-y)\|_2. $$令 $u=(x-y)/\|x-y\|_2$，则
$$ p(s) \le \mathbb P\{\|Au\|_2\ge s\} \le \mathbb P\{\|Au\|_2-\sqrt m\ge s/2\} \le 2\exp\left(-\frac{cs^2}{K^4}\right), $$其中最后一步再次使用步骤 1。因此单位向量情形成立。
步骤 4：一般情形。 现在令 $x,y\in\mathbb R^n$ 任意。由缩放，不妨假设 $\|x\|_2=1$ 且 $\|y\|_2\ge1$。把 $y$ 投影到单位球面，记
$$ \bar y:=\frac{y}{\|y\|_2}. $$三角不等式给出
$$ \|Z_x-Z_y\|_{\psi_2} \le \|Z_x-Z_{\bar y}\|_{\psi_2} + \|Z_{\bar y}-Z_y\|_{\psi_2}. $$第一项由步骤 3 控制，因为 $x$ 和 $\bar y$ 都是单位向量：
$$ \|Z_x-Z_{\bar y}\|_{\psi_2} \le CK^2\|x-\bar y\|_2. $$第二项利用 $\bar y$ 与 $y$ 共线以及齐次性：
$$ \|Z_{\bar y}-Z_y\|_{\psi_2} = \|\bar y-y\|_2\,\|Z_{\bar y}\|_{\psi_2}. $$由于 $\bar y$ 是单位向量，步骤 1 给出 $\|Z_{\bar y}\|_{\psi_2}\le CK^2$。因此
$$ \|Z_x-Z_y\|_{\psi_2} \le CK^2\left(\|x-\bar y\|_2+\|\bar y-y\|_2\right). \tag{9.10} $$这看起来不妙，因为我们希望右边被 $\|x-y\|_2$ 控制，而通常三角不等式方向相反。幸运的是，在当前几何关系中，三角不等式可以近似反向使用：
$$ \|x-\bar y\|_2+\|\bar y-y\|_2 \le \sqrt2\,\|x-y\|_2. $$这正是 Exercise 9.1 要验证的内容。代入 (9.10)，得到
$$ \|Z_x-Z_y\|_{\psi_2} \le \sqrt2\,CK^2\|x-y\|_2, $$Theorem 9.1.2 得证。
一个快速的 centering 技巧可以把 Theorem 9.1.1 变成围绕均值 $\mathbb E\|Ax\|_2$ 的 deviation inequality。请在 Exercise 9.2 中验证。
查看 Exercise 9.2我们只把 Theorem 9.1.1 表述为期望界；但借助 Talagrand inequality 的高概率版本（见 Exercise 8.37(b)），它会自动升级为尾界。对任意 $u\ge0$，事件
$$ \sup_{x\in T} \left|\|Ax\|_2-\sqrt m\|x\|_2\right| \le CK^2\left[w(T)+u\,\operatorname{rad}(T)\right] \tag{9.11} $$以至少 $1-2\exp(-u^2)$ 的概率成立。这里 $\operatorname{rad}(T)=\sup_{x\in T}\|x\|_2$ 是 $T$ 的半径。你可以检查为什么 (9.11) 推出期望界。
如果关心二次过程 $\|Ax\|_2^2$ 的偏差，也可以容易地从 Theorem 9.1.1 推出：
$$ \mathbb E\sup_{x\in T} \left|\|Ax\|_2^2-m\|x\|_2^2\right| \le CK^4\gamma(T)^2 + CK^2\sqrt m\,\operatorname{rad}(T)\gamma(T). $$请在 Exercise 9.3 中检查这个推导。
查看 Exercise 9.3作为练习，可以把矩阵偏差不等式推广到经验过程（Exercise 9.5），并证明随机投影的一个版本（Exercise 9.6，这题有挑战性）。
9.2 随机矩阵、协方差估计与 Johnson-Lindenstrauss
矩阵偏差不等式有很多直接后果。下面几节会依次快速说明。
9.2.1 随机矩阵的奇异值
把矩阵偏差不等式应用于欧氏单位球面 $T=S^{n-1}$，就得到第 4.6 节的奇异值界。
快速检查如下：对球面有
$$ \operatorname{rad}(T)=1,\qquad w(T)\le\sqrt n. $$
因此矩阵偏差不等式 (9.11) 说明事件
$$ \sqrt m-CK^2(\sqrt n+u) \le \|Ax\|_2 \le \sqrt m+CK^2(\sqrt n+u), \qquad x\in S^{n-1} $$
以至少 $1-2\exp(-u^2)$ 的概率成立。利用 (4.14)，这等价于
$$ \sqrt m-CK^2(\sqrt n+u) \le s_n(A) \le s_1(A) \le \sqrt m+CK^2(\sqrt n+u), $$
从而重新得到 Theorem 4.6.1。我们此前用另一种方法证明过它。
9.2.2 集合的随机投影
令 $T\subset\mathbb R^n$ 为有界集合，令 $A$ 为 $m\times n$ 矩阵，其行 $A_i$ 独立、各向同性且次高斯。则缩放矩阵
$$ P=\frac1{\sqrt n}A $$作为次高斯投影满足
$$ \mathbb E\operatorname{diam}(PT) \le \sqrt{\frac mn}\operatorname{diam}(T)+CK^2w_s(T). $$这里 $K=\max_i\|A_i\|_{\psi_2}$，$w_s(T)$ 是 $T$ 的球面宽度。
查看学习笔记：Proposition 9.2.1 完整证明这比我们之前的界（Theorem 7.6.1 和 Exercise 7.25）略尖锐：在 $\sqrt{m/n}$ 前面没有额外常数。
Theorem 9.1.1 与三角不等式给出
$$ \mathbb E\sup_{x\in T}\|Ax\|_2 \le \sqrt m\sup_{x\in T}\|x\|_2 + CK^2\gamma(T). $$用半径写就是
$$ \mathbb E\operatorname{rad}(AT) \le \sqrt m\,\operatorname{rad}(T)+CK^2\gamma(T). $$把这个界应用到差集 $T-T$，得到
$$ \mathbb E\operatorname{diam}(AT) \le \sqrt m\,\operatorname{diam}(T)+2CK^2w(T), $$其中使用了 Lemma 7.5.11(a)，从高斯复杂度转到高斯宽度。两边除以 $\sqrt n$ 即得结论。
现在可以尝试两件事：把 Proposition 9.2.1 的期望界升级为高概率界（Exercise 9.7）；以及在 Exercise 9.8 中分析真正的随机投影，而不是这里的 “高斯” 投影。
9.2.3 低维分布的协方差估计
若 $X$ 是次高斯随机向量，$\Sigma=\mathbb EXX^{\mathsf T}$，$\Sigma_m=m^{-1}\sum_{i=1}^mX_iX_i^{\mathsf T}$，且 $r=\operatorname{tr}(\Sigma)/\|\Sigma\|$，则
$$\mathbb E\|\Sigma_m-\Sigma\|\le CK^4\left(\sqrt{\frac rm}+\frac rm\right)\|\Sigma\|.$$ 查看学习笔记：Theorem 9.2.2 完整证明证明回到第 4.7 节的协方差估计问题。我们希望从 $m$ 个独立样本估计 $n$ 维分布的协方差矩阵
$$ \Sigma=\mathbb EXX^{\mathsf T}, \qquad \Sigma_m=\frac1m\sum_{i=1}^mX_iX_i^{\mathsf T}. $$
一般情形中，$m=O(n\log n)$ 个样本足够（第 5.6 节）；对次高斯分布，$m=O(n)$ 足够（第 4.7 节）。如果分布近似低维，例如集中在某个 $r$ 维子空间附近，Remark 5.6.3 说明 $m=O(r\log n)$ 足够。下面的定理说明：对次高斯分布，实际上 $m=O(r)$ 就够。
像 Theorem 4.7.1 的证明一样，把分布放到各向同性位置：写
$$ X=\Sigma^{1/2}Z, \qquad X_i=\Sigma^{1/2}Z_i, $$其中 $Z$ 和 $Z_i$ 是各向同性。于是
$$ \begin{aligned} \|\Sigma_m-\Sigma\| &= \|\Sigma^{1/2}R_m\Sigma^{1/2}\|, \qquad R_m=\frac1m\sum_{i=1}^mZ_iZ_i^{\mathsf T}-I_n\\ &= \max_{x\in S^{n-1}} \left|x^{\mathsf T}\Sigma^{1/2}R_m\Sigma^{1/2}x\right|\\ &= \max_{x\in T}|x^{\mathsf T}R_mx|, \qquad T:=\Sigma^{1/2}S^{n-1}\\ &= \frac1m \max_{x\in T} \left| \|Ax\|_2^2-m\|x\|_2^2 \right|, \end{aligned} $$其中 $A$ 是以 $Z_i$ 为行的 $m\times n$ 矩阵。与 Theorem 4.7.1 中一样，$Z_i$ 各向同性，并满足 $\|Z_i\|_{\psi_2}\lesssim1$；为了简化记号，这里把对 $K$ 的依赖隐藏起来。
对 $A$ 使用矩阵偏差不等式的二次型版本（Exercise 9.3），得到
$$ \mathbb E\|\Sigma_m-\Sigma\| \lesssim \frac1m \left(\gamma(T)^2+\sqrt m\,\operatorname{rad}(T)\gamma(T)\right). $$椭球 $T=\Sigma^{1/2}S^{n-1}$ 的半径和高斯复杂度满足
$$ \operatorname{rad}(T)=\|\Sigma\|^{1/2}, \qquad \gamma(T)\le(\operatorname{tr}\Sigma)^{1/2}. $$因此
$$ \mathbb E\|\Sigma_m-\Sigma\| \lesssim \frac1m \left( \operatorname{tr}\Sigma + \sqrt{m\|\Sigma\|\operatorname{tr}\Sigma} \right). $$代入 $\operatorname{tr}(\Sigma)=r\|\Sigma\|$ 并化简，即得定理。
和之前一样（见 Remarks 4.7.3 与 5.6.5），Theorem 9.2.2 的期望界可以升级为高概率界。对任意 $u\ge0$，有
$$ \|\Sigma_m-\Sigma\| \le CK^4 \left( \sqrt{\frac{r+u}{m}}+\frac{r+u}{m} \right) \|\Sigma\| $$以至少 $1-2e^{-u}$ 的概率成立。请在 Exercise 9.9 中证明这个结论。
查看学习笔记：Exercise 9.99.2.4 Johnson-Lindenstrauss 引理（无限集合）
矩阵偏差不等式很快可以重新推出第 5.3 节的 Johnson-Lindenstrauss 引理，并把它推广到一般甚至无限集合。
先看有限集合。固定一个 $N$ 点集 $\mathcal X\subset\mathbb R^n$，考虑归一化差集
$$ T= \left\{ \frac{x-y}{\|x-y\|_2}: x,y\in\mathcal X,\ x\ne y \right\}. $$
和 Example 7.5.9 一样，$T$ 的高斯复杂度满足
$$ \gamma(T)\le C\sqrt{\log N}. \tag{9.12} $$
Theorem 9.1.1 说明，以高概率，
$$ \sup_{x,y\in\mathcal X} \left| \frac{\|Ax-Ay\|_2}{\|x-y\|_2} -\sqrt m \right| \lesssim \sqrt{\log N}. $$
改写后，随机矩阵 $Q=A/\sqrt m$ 是 $\mathcal X$ 上的近似 isometry：
$$ (1-\varepsilon)\|x-y\|_2 \le \|Qx-Qy\|_2 \le (1+\varepsilon)\|x-y\|_2, \qquad x,y\in\mathcal X, $$
其中 $\varepsilon\asymp\sqrt{\log(N)/m}$。等价地，如果固定 $\varepsilon\gt 0$ 并取
$$ m\gtrsim \varepsilon^{-2}\log N, $$
则 $Q$ 以高概率成为 $\mathcal X$ 上的 $\varepsilon$-等距映射。这就恢复了经典 Johnson-Lindenstrauss 引理（Theorem 5.3.1）的一个版本。
上面的论证并不真正依赖 $\mathcal X$ 有限；关键量是高斯宽度。因此可推广为下面的 additive 版本。
令 $\mathcal X\subset\mathbb R^n$ 为有界集，令 $A$ 是 $m\times n$ 随机矩阵，其行 $A_i$ 独立、各向同性且次高斯。则以高概率（例如 $0.99$），缩放后的矩阵 $Q=A/\sqrt m$ 满足
$$ \left| \|Qx-Qy\|_2-\|x-y\|_2 \right| \le \delta \quad\text{for all }x,y\in\mathcal X, $$其中
$$ \delta=\frac{CK^2w(\mathcal X)}{\sqrt m}, \qquad K=\max_i\|A_i\|_{\psi_2}. $$ 查看学习笔记：Lemma 9.2.4 完整证明对差集
$$ T=\mathcal X-\mathcal X = \{x-y:x,y\in\mathcal X\} $$应用矩阵偏差不等式（Theorem 9.1.1）。以高概率，
$$ \sup_{x,y\in\mathcal X} \left| \|Ax-Ay\|_2-\sqrt m\|x-y\|_2 \right| \le CK^2\gamma(\mathcal X-\mathcal X). $$由 Lemma 7.5.11(a)，$\gamma(\mathcal X-\mathcal X)=2w(\mathcal X)$。两边除以 $\sqrt m$ 即得结论。
和经典 Johnson-Lindenstrauss 引理对有限集给出的相对误差不同，Lemma 9.2.4 给的是绝对误差 $\delta$。这个差别看起来小，但一般不可避免；Exercise 9.11 会要求你说明原因。
为了更好地理解加性 Johnson-Lindenstrauss 引理，可以用数据的有效维数来重写它。令
$$ d(\mathcal X) \asymp \frac{w(\mathcal X)^2}{\operatorname{diam}(\mathcal X)^2}, $$参见 Definition 7.5.12。若选择
$$ m\gtrsim \varepsilon^{-2}d(\mathcal X) $$并暂时忽略对 $K$ 的依赖，则 Lemma 9.2.4 中的误差可以做到
$$ \delta=\varepsilon\,\operatorname{diam}(\mathcal X). $$也就是说，$Q$ 会把所有距离保持到数据直径的一个小比例误差以内；换句话说，它把数据的维数降到了有效维数的量级。
9.3 随机截面：$M^*$ 界与逃逸定理
9.3.1 $M^*$ 界
令 $E=\ker A$，其中 $A$ 的行独立、各向同性且次高斯。则任意有界 $T\subset\mathbb R^n$ 满足
$$\mathbb E\operatorname{diam}(T\cap E)\le \frac{CK^2w(T)}{\sqrt m}.$$ 查看学习笔记：Theorem 9.3.1 完整证明这里有一个有些惊人的高维事实：若用一个余维为 $m$ 的随机子空间 $E$ 去切一个凸集 $T\subset\mathbb R^n$，切片 $T\cap E$ 往往很小，即使 $m\ll n$、$E$ 几乎仍是全维的。下面看它如何从矩阵偏差不等式推出。
建模随机子空间的方便方式是把它写成随机矩阵的核：
$$ E=\ker A. $$
总有 $\dim(E)\ge n-m$；如果 $A$ 有连续分布，则几乎必然 $\dim(E)=n-m$。例如，当 $A$ 是 i.i.d. $N(0,1)$ 高斯矩阵时，由旋转不变性，
$$ E=\ker(A)\sim\operatorname{Unif}(G_{n,n-m}). $$
对差集 $T-T$ 应用 Theorem 9.1.1，得到
$$ \mathbb E\sup_{z\in T-T} \left| \|Az\|_2-\sqrt m\|z\|_2 \right| \le CK^2\gamma(T-T) \le 2CK^2w(T). $$若 $x,y\in T\cap E$，则 $z=x-y\in T-T$ 且 $Az=0$。因此
$$ \sqrt m\|x-y\|_2 = \left|\|Az\|_2-\sqrt m\|z\|_2\right|. $$对 $x,y\in T\cap E$ 取上确界，再取期望，就得到
$$ \mathbb E\operatorname{diam}(T\cap E) \le \frac{CK^2w(T)}{\sqrt m}. $$把 $M^*$ 界应用于 cross-polytope $B_1^n$，也就是 $\ell^1$ 范数的单位球。由 (7.19)，它的高斯宽度约为 $\sqrt{\log n}$，所以
$$ \mathbb E\operatorname{diam}(B_1^n\cap E) \lesssim \sqrt{\frac{\log n}{m}}. $$例如，如果 $m=0.01n$，则
$$ \mathbb E\operatorname{diam}(B_1^n\cap E) \lesssim \sqrt{\frac{\log n}{n}}. \tag{9.13} $$也就是说，一个随机的 $0.99n$ 维切片会把 cross-polytope 切得非常小。
直观上，回忆 Figure 7.4a 中对 cross-polytope 的示意：$B_1^n$ 的主体集中在半径 $1/\sqrt n$ 的内切欧氏球附近，而其余部分沿坐标轴伸出细长尖刺。随机子空间通常会避开这些尖刺，只穿过主体，所以切片直径大约是 $O(1/\sqrt n)$，至多多一个如 (9.13) 中的对数因子。这个直觉也适用于一般凸集。
为了获得更多直觉，可以用有效维数重写 $M^*$ 界。令
$$ d(T)\asymp \frac{w(T)^2}{\operatorname{diam}(T)^2} $$参见 Definition 7.5.12。$M^*$ 界说明，只要
$$ m\gtrsim d(T), $$随机切片就会显著缩小直径，例如
$$ \mathbb E\operatorname{diam}(T\cap E) \le 0.01\,\operatorname{diam}(T) $$在常数适当时成立。由于 $\dim(E)=n-m$，这个条件等价于
$$ \dim(E)+c\,d(T)\le n. $$这与线性代数直觉一致：如果 $T$ 是某个子空间 $F\subset\mathbb R^n$ 中以原点为中心的欧氏球，那么只有当 $\dim E+\dim F\le n$ 时，切片才可能真正缩小 $T$ 的直径。
练习 9.12、9.13、9.14 分别要求把 $M^*$ 界推广到仿射截面、推出高概率版本，并计算 $\ell^p$ 球的随机切片直径。
9.3.2 逃逸定理
$M^*$ 界说明随机切片通常很小。另一个相关问题是：随机子空间什么时候会完全避开一个集合？
令 $T\subset S^{n-1}$ 为任意集合，令 $A$ 为 $m\times n$ 矩阵，其行 $A_i$ 独立、各向同性且次高斯。若
$$ m\ge CK^4w(T)^2, \tag{9.14} $$则随机子空间 $E=\ker A$ 满足
$$ T\cap E=\varnothing $$的概率至少为 $1-2\exp(-cm/K^4)$。这里 $K=\max_i\|A_i\|_{\psi_2}$。
查看学习笔记：Theorem 9.3.4 完整证明使用矩阵偏差不等式的高概率版本（见 Remark 9.1.4）：以至少 $1-2\exp(-u^2)$ 的概率，
$$ \sup_{x\in T} \left| \|Ax\|_2-\sqrt m \right| \le C_1K^2\bigl(w(T)+u\bigr). \tag{9.15} $$假设事件 (9.15) 发生。若 $T\cap E\ne\varnothing$，则对任意 $x\in T\cap E$ 都有 $Ax=0$，于是
$$ \sqrt m \le C_1K^2\bigl(w(T)+u\bigr). $$取
$$ u=\frac{\sqrt m}{2C_1K^2}, $$上式化简为
$$ \sqrt m\le 2C_1K^2w(T). $$如果 (9.14) 中的绝对常数 $C$ 取得足够大，这与假设矛盾。因此，在这个 $u$ 的选择下，事件 (9.15) 蕴含 $T\cap E=\varnothing$。其概率至少为
$$ 1-2\exp\left(-\frac{m}{4C_1^2K^4}\right) \ge 1-2\exp\left(-\frac{cm}{K^4}\right), $$这就证明了逃逸定理。
9.4 应用：高维线性模型
现在把工具用于一个经典的数据科学问题：在高维中学习线性模型。设有一个未知向量 $x\in\mathbb R^n$，我们想从 $m$ 个线性、可能带噪的观测中学习它：
$$ y_i=\langle A_i,x\rangle+w_i,\qquad i=1,\ldots,m. $$
这里 $A_i\in\mathbb R^n$ 已知，$w_i$ 是未知噪声。用矩阵写就是
$$ y=Ax+w, \tag{9.16} $$
其中 $A$ 是已知的 $m\times n$ 矩阵，$w\in\mathbb R^m$ 是未知噪声。目标是从 $y$ 和 $A$ 尽可能准确地恢复 $x$。
我们假设 $A$ 的行 $A_i$ 随机且独立。这在许多统计场景中是合理的，例如 i.i.d. observations；同时也非常适合使用高维概率工具。
在信号处理中，$x$ 可以是数字化音频信号，而 $y$ 是在 $m$ 个随机时间点采样得到的结果。
统计学中的核心问题之一是线性回归：我们希望从 $m$ 个样本中学习 $n$ 个预测变量与响应变量之间的线性关系。模型写成
$$ Y=X\theta+w, $$其中 $X$ 是 $m\times n$ 预测矩阵，$Y\in\mathbb R^m$ 是响应向量，$\theta\in\mathbb R^n$ 是要学习的参数向量，$w$ 是噪声。例如在遗传学中，可以用基因表达数据预测疾病：收集 $m$ 个病人的数据，$X_{ij}$ 表示第 $i$ 个病人第 $j$ 个基因的活跃程度，$Y_i$ 表示该病人是否患病。目标是学习参数向量 $\theta$，它描述每个基因如何影响疾病。
现代问题中，数据量经常少于参数量：
$$ m\ll n. $$例如典型遗传学研究可能只有约 $100$ 个病人，却有约 $10,000$ 个基因。在这种高维设定中，即使是无噪声问题 $y=Ax$ 也无法直接求解，因为解太多，通常形成一个维数至少为 $n-m$ 的大子空间。
不过，如果我们有关于 $x$ 结构的先验信息，仍然可能恢复 $x$。把这种信息写成
$$ x\in T \tag{9.17} $$其中 $T\subset\mathbb R^n$ 已知。例如，若 $x$ 稀疏，就取 $T$ 为稀疏向量集合；若 $x$ 是带限信号，就取 $T$ 为带限信号的集合。下面看这种结构如何提供帮助。
9.4.1 约束恢复
先考虑 noiseless case：
$$ y=Ax,\qquad x\in T. $$
如何求解这个高维约束线性问题？一个简单想法是：在 $T$ 中找任意一个与观测匹配的向量：
$$ \text{find }x': \quad y=Ax', \quad x'\in T. \tag{9.18} $$
如果 $T$ 是 convex 集合，那么这是一个 convex program，可以用许多数值算法求解。下面检查这个解有多准确。
假设 $A$ 的行 $A_i$ 独立、各向同性且次高斯。则程序 (9.18) 的任意解 $\hat x$ 满足
$$ \mathbb E\|\hat x-x\|_2 \le \frac{CK^2w(T)}{\sqrt m}, \tag{9.19} $$其中 $K=\max_i\|A_i\|_{\psi_2}$。
查看学习笔记：Theorem 9.4.4 完整证明由于 $x,\hat x\in T$ 且 $Ax=A\hat x=y$，有
$$ x,\hat x\in T\cap E_x, \qquad E_x=x+\ker A. $$于是仿射 $M^*$ 界（Exercise 9.12）给出
$$ \mathbb E\|\hat x-x\|_2 \le \mathbb E\operatorname{diam}(T\cap E_x) \le \frac{CK^2w(T)}{\sqrt m}. $$
为了获得直觉，把 (9.19) 用有效维数
$$ d(T)\asymp \frac{w(T)^2}{\operatorname{diam}(T)^2} $$重写。只要观测数满足
$$ m\gtrsim d(T), $$就能得到非平凡误差界。由于 $d(T)$ 可能远小于环境维数 $n$，即使在 $m\ll n$ 的高维情形中，恢复也可能成功。
如果 $T$ 非凸，可以把它替换为凸包 $\operatorname{conv}(T)$。这样 (9.18) 变成凸优化问题；而 Theorem 9.4.4 的恢复保证不变，因为 Proposition 7.5.2(c) 给出 $w(\operatorname{conv}(T))=w(T)$。
这个方法很灵活。可以在 Exercise 9.17 中分析均方误差，在 Exercise 9.18 中分析 optimization recovery，在 Exercise 9.19 中处理 noisy case (9.16)。
像 (9.18) 那样强制要求 $y=Ax'$ 且 $x'\in T$ 可能过于僵硬：噪声或者错误的 $T$ 都可能导致无解。更稳妥的做法是放松约束，用惩罚项惩罚违反约束的程度。
给定带噪观测
$$ y=Ax+w, $$一个常用恢复方式是求解无约束凸优化问题：
$$ \text{minimize } \|y-Ax'\|_2^2+\lambda\|x'\|_T \quad\text{over all }x'\in\mathbb R^n. \tag{9.20} $$这里 $\|\cdot\|_T$ 是选择的范数，$\lambda\gt 0$ 控制拟合观测 $y$ 与保持解结构化之间的权衡。Exercise 9.20 会证明：若 $A$ 是随机矩阵且 $\lambda$ 选择合适，那么解 $\hat x$ 满足
$$ \mathbb E\|\hat x-x\|_2 \lesssim \frac{w(T)\|x\|_T+\|w\|_2}{\sqrt m}, $$其中 $T$ 是 $\|\cdot\|_T$ 的单位球。也就是说，如果 $x$ 结构好、$\|x\|_T$ 小，并且噪声 $w$ 小，那么从约 $m\asymp d(T)$ 个观测中就能准确恢复。
9.4.2 例：稀疏恢复
有时我们相信 $x$ 是稀疏的，即多数坐标为零或近似为零。例如在遗传学问题中，也许只有约 $10$ 个基因真正影响疾病；在其他应用中，$x$ 也可能在某个基底下稀疏：Example 9.4.1 中的音频信号在时域不稀疏，但它的 Fourier transform 可能集中在少量频率上。
用非零坐标数衡量稀疏性：
$$ \|x\|_0:=|\operatorname{supp}(x)| =|\{i:x_i\ne0\}|. \tag{9.21} $$
若 $\|x\|_0\le s$，称 $x$ 为 $s$-稀疏。这个 $\ell^0$ “范数” 不是真正的范数，但它可看作 $\ell^p$ 范数在 $p\to0$ 时的极限（见 Exercise 9.23）。
快速维数计数说明：若 $A$ 处于一般位置且观测数足够多，$m\ge2\|x\|_0$ 时可以从 $y=Ax$ 恢复 $x$（见 Exercise 9.22）。听起来很好，但若不知道 $x$ 的支撑集，直接搜索所有支撑集计算上不可行：需要检查的支撑集至少有 $\binom ns\ge2^s$ 个。随机观测可以帮助解决这个问题。
如果相信 $x$ 是 $s$-稀疏，自然想取
$$ T=\{x\in\mathbb R^n:\|x\|_0\le s\} $$
作为先验。但 $T$ 高度非凸，求解 (9.18) 仍然很难。一个简单修复是把 $\ell^0$ “范数” 换成最接近它且真正为范数的 $\ell^1$ 范数。由于所有满足 $\|x\|_2\le1$ 的 $s$-稀疏向量都有 $\|x\|_1\le\sqrt s$，取凸集合
$$ T:=\sqrt s\,B_1^n \tag{9.22} $$
作为先验是合理的。程序 (9.18) 变成
$$ \text{find }x': \quad y=Ax', \quad \|x'\|_1\le\sqrt s, \tag{9.23} $$
这是 convex 且可计算的。
假设 $A$ 的行 $A_i$ 独立、各向同性且次高斯。若未知 $s$-稀疏向量 $x\in\mathbb R^n$ 满足 $\|x\|_2\le1$，则程序 (9.23) 的任意解 $\hat x$ 满足
$$ \mathbb E\|\hat x-x\|_2 \le CK^2\sqrt{\frac{s\log n}{m}}, $$其中 $K=\max_i\|A_i\|_{\psi_2}$。
查看学习笔记：Corollary 9.4.8 完整证明取 $T=\sqrt s\,B_1^n$。结论由 Theorem 9.4.4 和 $\ell^1$ 球的高斯宽度界 (7.19) 得到：
$$ w(T)=\sqrt s\,w(B_1^n)\le C\sqrt{s\log n}. $$Corollary 9.4.8 说明，只要
$$ m\gtrsim s\log n, \tag{9.24} $$误差就会很小。这意味着当 $s\ll n$ 时，可以用远少于完整维数 $n$ 的观测数有效恢复稀疏向量。Exercise 9.24 会把结论推广到近似稀疏向量。
单位 $s$-稀疏向量的集合 $S_{n,s}$ 可以更紧地 convexify。与其用 (9.22) 中的 $T=\sqrt s\,B_1^n$，可以用截断 $\ell^1$ 球
$$ T_{n,s}:=\sqrt s\,B_1^n\cap B_2^n. $$这个 relaxation 很紧。Exercise 9.25 会证明
$$ \operatorname{conv}(S_{n,s}) \subset T_{n,s} \subset 2\operatorname{conv}(S_{n,s}). $$这个更紧的集合把 (9.24) 中的对数因子改进为
$$ m\gtrsim s\log(en/s). $$详见 Exercises 9.26-9.27。Exercise 9.28 给出 Garnaev-Gluskin 定理，它刻画 $\ell^1$ 球的随机切片；Exercise 9.21 则介绍 Lasso，它是 (9.20) 在 $\ell^1$ 范数下的特例。
9.4.3 例：低秩恢复
再看一个高维线性问题：从 $m$ 个线性观测恢复一个 $d\times d$ 矩阵 $X$：
$$ y_i=\langle A_i,X\rangle,\qquad i=1,\ldots,m, \tag{9.25} $$
其中 $A_i$ 是已知的独立随机矩阵，内积为 $\langle A,B\rangle=\operatorname{tr}(A^{\mathsf T}B)$。一般需要 $d^2$ 个观测，也就是每个元素一个观测。若想用更少观测，就需要 $X$ 有结构；常见结构是 low rank。
rank 是奇异值的 $\ell^0$ “范数”，高度非凸。与稀疏恢复中的做法类似，把它 convex relax 为奇异值的 $\ell^1$ 范数，也就是 nuclear 范数：
$$ \|X\|_*:=\sum_{i=1}^d s_i(X). $$
若矩阵 $X$ 的 rank 至多 $r$ 且 $\|X\|_F\le1$，则它的奇异值向量至多有 $r$ 个非零坐标且欧氏范数至多 $1$，因此 $\|X\|_*\le\sqrt r$。于是取 $T=\sqrt r\,B_*$，其中
$$ B_*:=\{X\in\mathbb R^{d\times d}:\|X\|_*\le1\} $$
是核范数单位球。恢复程序为
$$ \text{find }X': \quad y_i=\langle A_i,X'\rangle\ \forall i=1,\ldots,m, \quad \|X'\|_*\le\sqrt r. \tag{9.26} $$
设 $A_i$ 是独立高斯随机矩阵，所有元素独立同分布为 $N(0,1)$。若未知 $d\times d$ 矩阵 $X$ 的 rank 至多为 $r$ 且 $\|X\|_F\le1$，则程序 (9.26) 的任意解 $\hat X$ 满足
$$ \mathbb E\|\hat X-X\|_F \le C\sqrt{\frac{rd}{m}}. $$ 查看学习笔记：Corollary 9.4.11 完整证明由核范数与算子范数的对偶性（Exercise 7.18(a)），对 $d\times d$ 高斯矩阵 $G$，
$$ w(B_*) = \mathbb E\sup_{\|X\|_*\le1}\langle G,X\rangle = \mathbb E\|G\| \le 2\sqrt d, $$最后一步来自 Theorem 7.3.1。对 $T=\sqrt r\,B_*$ 使用 Theorem 9.4.4 即得结论。
Corollary 9.4.11 在
$$ m\gtrsim rd $$时给出小误差。若 $r\ll d$，这远少于元素数量 $d^2$。这和第 6.5 节的矩阵补全类似，后者用大约 $rd\log d$ 个随机观测恢复低秩矩阵。Exercise 9.29 会把低秩恢复推广到矩形矩阵和近似低秩矩阵。
9.5 应用：精确稀疏恢复
在 noiseless case 中，还可以做得更强：从 $y=Ax$ 精确恢复稀疏向量 $x$，而且算法有效。我们看两条路线：
- 使用逃逸定理（Theorem 9.3.4）。
- 找到一个保证精确恢复的确定性条件，也就是限制等距性质，再证明随机矩阵以高概率满足它。
9.5.1 基于逃逸定理的精确恢复
先建立几何直觉。设要通过凸优化程序 (9.23) 从 $y=Ax$ 恢复未知 $s$-稀疏单位向量 $x$。解 $\hat x$ 位于先验集合 $T=\sqrt s\,B_1^n$ 与仿射子空间 $E_x=x+\ker A$ 的交中。
$T$ 是 cross-polytope，而 $x$ 位于它的某个 $(s-1)$ 维边上。若随机子空间 $E_x$ 在 $x$ 处与多胞体相切，那么 $T$ 与 $E_x$ 只在 $x$ 相交，从而解必然精确：
$$ \hat x=x. $$
要证明这个论证，需要说明随机子空间 $E_x$ 以高概率与 $\ell^1$ 球在 $x$ 处相切。放大看 $x$ 附近：这等价于切锥的球面部分与 $E_x$ 不相交，而逃逸定理正是用来保证这种不相交的工具。
现在形式化。我们希望从
$$ y=Ax $$
通过优化问题
$$ \text{minimize }\|x'\|_1 \quad\text{subject to }y=Ax' \tag{9.27} $$
恢复 $x$。
设 $A$ 是 $m\times n$ 随机矩阵，其行 $A_i$ 独立、各向同性且次高斯。若
$$ m\ge CK^4s\log n, $$则以至少 $1-2\exp(-cm/K^4)$ 的概率，对任意 $s$-稀疏向量 $x\in\mathbb R^n$，程序 (9.27) 的解是精确的：
$$ \hat x=x. $$这里 $K=\max_i\|A_i\|_{\psi_2}$。
查看学习笔记：Theorem 9.5.1 完整证明证明要说明 recovery error 为零：
$$ h:=\hat x-x=0. $$
先证明一个弱结论：误差 $h$ 在 $x$ 的支撑集上更重。
令 $S:=\operatorname{supp}(x)$，并令 $h_S$ 表示 $h$ 限制在 $S$ 上的向量，$h_{S^c}$ 类似。则
$$ \|h_{S^c}\|_1\le\|h_S\|_1. $$ Lemma 9.5.2因为 $\hat x$ 是 (9.27) 的 minimizer，
$$ \|\hat x\|_1\le\|x\|_1. \tag{9.28} $$另一方面，由三角不等式且 $x_S=x$、$x_{S^c}=0$，有
$$ \|\hat x\|_1 = \|x+h\|_1 = \|x_S+h_S\|_1+\|x_{S^c}+h_{S^c}\|_1 \ge \|x\|_1-\|h_S\|_1+\|h_{S^c}\|_1. $$与 (9.28) 合并并化简，即得结论。
误差向量满足
$$ \|h\|_1\le2\sqrt s\,\|h\|_2. $$ Lemma 9.5.3由 Lemma 9.5.2 和 Cauchy-Schwarz inequality，
$$ \|h\|_1 = \|h_S\|_1+\|h_{S^c}\|_1 \le 2\|h_S\|_1 \le 2\sqrt s\,\|h_S\|_2 \le 2\sqrt s\,\|h\|_2. $$假设 $h=\hat x-x\ne0$。Lemma 9.5.3 给出
$$ \frac{h}{\|h\|_2} \in T_s:= \left\{ z\in S^{n-1}:\|z\|_1\le2\sqrt s \right\}. $$又因为 $Ah=A\hat x-Ax=y-y=0$，所以
$$ \frac{h}{\|h\|_2} \in T_s\cap\ker A. \tag{9.29} $$逃逸定理（Theorem 9.3.4）说明，只要 $m\ge C_1K^4w(T_s)^2$，该交集就以高概率为空。另一方面，由 $T_s\subset2\sqrt s\,B_1^n$ 和 (7.19)，
$$ w(T_s) \le 2\sqrt s\,w(B_1^n) \le C_2\sqrt{s\log n}. \tag{9.30} $$因此若 $m\ge CK^4s\log n$，则 (9.29) 中的交集以高概率为空，与 $h\ne0$ 矛盾。所以 $h=0$，证明完成。
稍微改进 (9.30)，可把 Theorem 9.5.1 中充分的观测数改进为
$$ m\ge CK^4s\log(en/s). $$这来自 Exercise 9.26。Exercise 9.30 会让你几何化理解精确恢复证明，Exercise 9.31 处理带噪声情形，Exercise 9.32 则给出精确恢复的零空间性质。
9.5.2 受限等距性
下面寻找一个保证稀疏恢复的确定性条件，并证明随机矩阵以高概率满足它。这个条件称为限制等距性质。
一个 $m\times n$ 矩阵 $A$ 满足参数为 $\alpha,\beta,s$ 的限制等距性质 (RIP)，若对所有至多有 $s$ 个非零坐标的 $v\in\mathbb R^n$，都有
$$ \alpha\|v\|_2\le\|Av\|_2\le\beta\|v\|_2. $$RIP 等价于说 $A$ 的所有 $m\times s$ 子矩阵 $A_I$ 的奇异值满足
$$ \alpha\le s_s(A_I)\le s_1(A_I)\le\beta. \tag{9.31} $$
若 $\alpha\approx\beta\approx1$，则所有这些子矩阵都是近似等距映射。
假设 $m\times n$ 矩阵 $A$ 满足参数 $\alpha,\beta,(1+\lambda)s$ 的 RIP，其中 $\lambda\gt (\beta/\alpha)^2$。那么每个 $s$-稀疏向量 $x\in\mathbb R^n$ 都可由 (9.27) 从 $y=Ax$ 精确恢复，即 $\hat x=x$。
查看学习笔记：Theorem 9.5.6 完整证明和 Theorem 9.5.1 的证明一样，需要证明误差 $h=\hat x-x$ 为零。
步骤 1：分解支撑集。 令 $I_0=\operatorname{supp}(x)$。令 $I_1$ 为 $h_{I_0^c}$ 中绝对值最大的 $\lambda s$ 个元素的指标集合，$I_2$ 为接下来 $\lambda s$ 个，依此类推。记 $I_{01}=I_0\cup I_1$。由于 $Ah=A\hat x-Ax=0$，三角不等式给出
$$ 0=\|Ah\|_2 \ge \|A_{I_{01}}h_{I_{01}}\|_2 - \|A_{I_{01}^c}h_{I_{01}^c}\|_2. \tag{9.32} $$步骤 2：使用 RIP。 因为 $|I_{01}|\le(1+\lambda)s$，RIP 给出
$$ \|A_{I_{01}}h_{I_{01}}\|_2 \ge \alpha\|h_{I_{01}}\|_2. $$同时由三角不等式和 RIP，
$$ \|A_{I_{01}^c}h_{I_{01}^c}\|_2 \le \sum_{i\ge2}\|A_{I_i}h_{I_i}\|_2 \le \beta\sum_{i\ge2}\|h_{I_i}\|_2. $$代入 (9.32)，得到
$$ \beta\sum_{i\ge2}\|h_{I_i}\|_2 \ge \alpha\|h_{I_{01}}\|_2. \tag{9.33} $$步骤 3：求和估计。 按照 $I_i$ 的定义，$h_{I_i}$ 的每个元素绝对值都不超过前一块平均绝对值，即对 $i\ge2$，
$$ \|h_{I_i}\|_2 \le \frac1{\sqrt{\lambda s}}\|h_{I_{i-1}}\|_1. $$求和并使用 Lemma 9.5.2，得到
$$ \sum_{i\ge2}\|h_{I_i}\|_2 \le \frac1{\sqrt{\lambda s}}\|h_{I_0^c}\|_1 \le \frac1{\sqrt{\lambda s}}\|h_{I_0}\|_1 \le \frac1{\sqrt\lambda}\|h_{I_0}\|_2 \le \frac1{\sqrt\lambda}\|h_{I_{01}}\|_2. $$代入 (9.33)：
$$ \frac{\beta}{\sqrt\lambda}\|h_{I_{01}}\|_2 \ge \alpha\|h_{I_{01}}\|_2. $$由于 $\beta/\sqrt\lambda\lt \alpha$，只能有 $h_{I_{01}}=0$。而 $I_{01}$ 包含 $h$ 的最大元素，因此 $h=0$。
虽然我们不知道如何构造具有好参数的 deterministic RIP 矩阵，但可以证明随机矩阵以高概率满足 RIP。
设 $A$ 是 $m\times n$ 随机矩阵，其行 $A_i$ 独立、各向同性且次高斯。若
$$ m\ge CK^4s\log(en/s), $$其中 $K=\max_i\|A_i\|_{\psi_2}$，则以至少 $1-2\exp(-cm/K^4)$ 的概率，$A$ 满足参数 $\alpha=0.9\sqrt m$、$\beta=1.1\sqrt m$ 和 $s$ 的 RIP。
查看学习笔记：Theorem 9.5.7 完整证明需要对所有 $m\times s$ 子矩阵 $A_I$ 检查 (9.31)。先固定 $I$。由 Theorem 4.6.1，
$$ 0.9\sqrt m \le s_s(A_I) \le s_1(A_I) \le 1.1\sqrt m \tag{9.34} $$以至少 $1-2\exp(-2cm/K^4)$ 的概率成立；这里是在 Theorem 4.6.1 中取 $t=\sqrt{2cm}/K^2$，并用 $m$ 的假设适当选择 absolute constants $c,C$。
现在对所有 $\binom ns$ 个 $s$ 元子集 $I\subset\{1,\ldots,n\}$ 做并集界。于是 (9.34) 同时对所有 $I$ 成立的概率至少为
$$ 1 - 2\exp\left(-\frac{2cm}{K^4}\right)\binom ns. $$再由
$$ \binom ns\le\exp(s\log(en/s)) $$以及 $m\ge CK^4s\log(en/s)$，上面的概率下界进一步变成
$$ 1-2\exp\left(-\frac{cm}{K^4}\right). $$因此所有 $m\times s$ 子矩阵同时满足 (9.34)，也就是 $A$ 满足所需 RIP。
由 Theorem 9.5.7，随机矩阵 $A$ 以高概率对 $3s$ 阶满足 RIP，且参数可取
$$ \alpha=0.9\sqrt m,\qquad \beta=1.1\sqrt m. $$在 Theorem 9.5.6 中取 $\lambda=2$，因为此时 $(1+\lambda)s=3s$，并且在常数选择下满足 $\lambda\gt (\beta/\alpha)^2$。于是 Theorem 9.5.6 保证 (9.27) 的解精确恢复 $x$。
所以 Theorem 9.5.1 成立；事实上，这一路线还给出 Remark 9.5.4 中的对数因子改进。
Exercise 9.33 会让你证明随机投影满足 RIP。
9.6 一般范数下的随机矩阵偏差
下面把矩阵偏差不等式推广到任意范数，而不仅是欧氏范数。事实上，甚至不要求函数非负；正齐次性和三角不等式型的次可加性已经足够。
线性空间 $V$ 上的实值函数 $f$ 称为正齐次，若对所有 $\alpha\ge0$ 和 $x\in V$，
$$ f(\alpha x)=\alpha f(x). $$称为次可加，若对所有 $x,y\in V$，
$$ f(x+y)\le f(x)+f(y). $$以下函数都是正齐次且次可加：
(a) 任意范数；
(b) 任意实值 linear 函数，也叫 linear 泛函；
(c) 特别地，对固定 $y\in\mathbb R^m$，函数 $f(x)=\langle x,y\rangle$；
(d) 任意有界集合 $S\subset\mathbb R^m$ 的支撑函数
$$ f(x):=\sup_{y\in S}\langle x,y\rangle,\qquad x\in\mathbb R^m. \tag{9.35} $$下面的 Theorem 9.1.1 版本适用于所有范数，甚至适用于正齐次、次可加函数；代价是这里只处理高斯矩阵。
令 $A$ 为 $m\times n$ 随机矩阵，其元素独立同分布为 $N(0,1)$。设 $f:\mathbb R^m\to\mathbb R$ 是有界、正齐次且次可加的函数，并且存在 $b\in\mathbb R$ 使得
$$ f(x)\le b\|x\|_2,\qquad x\in\mathbb R^m. \tag{9.36} $$则对任意 $T\subset\mathbb R^n$，
$$ \mathbb E\sup_{x\in T} \left|f(Ax)-\mathbb Ef(Ax)\right| \le Cb\gamma(T). $$ 查看学习笔记：Theorem 9.6.3 完整证明和第 9.1 节一样，只要证明随机过程
$$ Z_x:=f(Ax)-\mathbb Ef(Ax) \tag{9.37} $$
具有次高斯增量，就可以由 Talagrand 比较推出 Theorem 9.6.3。
令 $A$ 为 $m\times n$ 高斯随机矩阵，元素独立同分布为 $N(0,1)$。设 $f:\mathbb R^m\to\mathbb R$ 正齐次、次可加且满足 (9.36)。则过程 (9.37) 满足
$$ \|Z_x-Z_y\|_{\psi_2} \le Cb\|x-y\|_2,\qquad x,y\in\mathbb R^n. \tag{9.38} $$ 查看学习笔记：Theorem 9.6.4 完整证明不妨设 $b=1$。先假设 $\|x\|_2=\|y\|_2=1$，此时要证
$$ \|f(Ax)-f(Ay)\|_{\psi_2} \le C\|x-y\|_2. \tag{9.39} $$步骤 1：制造独立性。 设
$$ u:=\frac{x+y}{2},\qquad v:=\frac{x-y}{2}. \tag{9.40} $$于是 $x=u+v$、$y=u-v$，从而
$$ Ax=Au+Av,\qquad Ay=Au-Av. $$由于 $u$ 与 $v$ 正交，高斯随机向量 $Au$ 和 $Av$ 独立。
步骤 2：使用高斯集中。 条件在 $a:=Au$ 上，考察
$$ f(Ax)=f(a+Av). $$由独立性，$a+Av$ 的条件分布可写成
$$ a+Av=a+\|v\|_2g, \qquad g\sim N(0,I_m). $$函数 $z\mapsto f(a+\|v\|_2z)$ 的 Lipschitz 范数至多为 $\|v\|_2$。事实上，对任意 $t,s\in\mathbb R^m$，由次可加性、正齐次性和 (9.36)，
$$ \begin{aligned} f(a+\|v\|_2t)-f(a+\|v\|_2s) &\le f(\|v\|_2(t-s))\\ &=\|v\|_2f(t-s)\\ &\le\|v\|_2\|t-s\|_2. \end{aligned} $$高斯集中（Theorem 5.2.3）给出条件尾界
$$ \left\| f(a+Av)-\mathbb E_a f(a+Av) \right\|_{\psi_2(a)} \le C\|v\|_2. \tag{9.41} $$步骤 3：去掉条件。 随机向量 $a-Av$ 与 $a+Av$ 同分布，因此也满足
$$ \left\| f(a-Av)-\mathbb E_a f(a-Av) \right\|_{\psi_2(a)} \le C\|v\|_2. \tag{9.42} $$将 (9.42) 从 (9.41) 中相减，使用三角不等式，并注意两个条件期望相同，得到
$$ \|f(a+Av)-f(a-Av)\|_{\psi_2(a)} \le 2C\|v\|_2. $$该条件界对每个固定 $a$ 都成立，因此无条件也成立。回到 $x,y$ 记号，并用 $\|v\|_2=\|x-y\|_2/2$，得到 (9.39)。一般 $x,y$ 的情形与 Theorem 9.1.2 证明中的步骤 4 相同。
Theorem 9.6.3 是否对一般次高斯矩阵 $A$ 成立，是一个开放问题。Exercises 9.35 和 9.36 分别给出各向异性版本和高概率版本。
9.7 双侧 Chevet 不等式与 Dvoretzky-Milman 定理
和本章原始的矩阵偏差不等式一样，更一般的 Theorem 9.6.3 有很多应用。比如，你现在可以在任意范数中得到 Johnson-Lindenstrauss 型引理，而不仅是欧氏范数；见 Exercises 9.37-9.39。
9.7.1 双侧 Chevet 不等式
general 矩阵偏差的另一个结果是 Chevet 不等式的更尖锐版本。我们在第 8.6 节已经见过 Chevet 不等式。
令 $A$ 为 $m\times n$ 高斯随机矩阵，元素独立同分布为 $N(0,1)$。令 $T\subset\mathbb R^n$、$S\subset\mathbb R^m$ 为任意有界集合。则
$$ \mathbb E\sup_{x\in T} \left| \sup_{y\in S}\langle Ax,y\rangle - w(S)\|x\|_2 \right| \le C\gamma(T)\operatorname{rad}(S). $$ 查看学习笔记：Theorem 9.7.1 完整证明由三角不等式可见，Theorem 9.7.1 给出 Chevet 不等式（Theorem 8.6.1）的更强双侧版本。
对 $S$ 的支撑函数使用 Theorem 9.6.3：
$$ f(x)=\sup_{y\in S}\langle x,y\rangle. $$由 Cauchy-Schwarz inequality，
$$ f(x) \le \sup_{y\in S}\|x\|_2\|y\|_2 = \operatorname{rad}(S)\|x\|_2. \tag{9.43} $$另一方面，$Ax$ 与 $g\|x\|_2$ 同分布，其中 $g\sim N(0,I_m)$。由正齐次性，
$$ \begin{aligned} \mathbb Ef(Ax) &= \|x\|_2\mathbb Ef(g)\\ &= \|x\|_2\mathbb E\sup_{y\in S}\langle g,y\rangle\\ &= \|x\|_2w(S). \tag{9.44} \end{aligned} $$把 (9.43) 与 (9.44) 代入 Theorem 9.6.3，即得结论。
9.7.2 Dvoretzky-Milman 定理
现在证明一个令人惊讶的结果：把任意有界集合随机投影到低维空间后，它会以高概率看起来近似圆。
令 $A$ 为 $m\times n$ 高斯随机矩阵，元素独立同分布为 $N(0,1)$，令 $T\subset\mathbb R^n$ 有界。则以至少 $0.99$ 的概率，
$$ r_-B_2^m \subset \operatorname{conv}(AT) \subset r_+B_2^m, \tag{9.45} $$其中 $B_2^m$ 是 $\mathbb R^m$ 中的欧氏单位球，
$$ r_\pm=w(T)\pm C\sqrt m\,\operatorname{rad}(T). $$左侧包含关系只在 $r_-\ge0$ 时有意义；右侧包含关系总成立。
查看学习笔记：Theorem 9.7.2 完整证明
先把 two-sided Chevet 不等式（Theorem 9.7.1）写成如下形式：
$$ \mathbb E\sup_{y\in S} \left| \sup_{x\in T}\langle Ax,y\rangle - w(T)\|y\|_2 \right| \le C\gamma(S)\operatorname{rad}(T). $$这是把 Theorem 9.7.1 应用于 $A^{\mathsf T}$ 并交换 $T,S$ 得到的。
令 $S=S^{m-1}$。由于 $\gamma(S)\le\sqrt m$，Markov inequality 给出：以至少 $0.99$ 的概率，对所有 $y\in S^{m-1}$，
$$ \left| \sup_{x\in T}\langle Ax,y\rangle - w(T) \right| \le C\sqrt m\,\operatorname{rad}(T). $$由 $r_\pm$ 的定义，这意味着
$$ r_- \le \sup_{x\in T}\langle Ax,y\rangle \le r_+, \qquad y\in S^{m-1}. $$把 $\sup_{x\in T}\langle Ax,y\rangle$ 写成 $\sup_{z\in AT}\langle z,y\rangle$，并利用齐次性，得到对所有 $y\in\mathbb R^m$，
$$ r_-\|y\|_2 \le \sup_{z\in AT}\langle z,y\rangle \le r_+\|y\|_2. $$按支撑函数的对偶性，这正等价于 (9.45)。Exercise 9.40 会让你写出这个对偶性细节。
设 $T$ 有界、convex 且包含原点，且
$$ m\le cd(T), $$其中
$$ d(T)\asymp \frac{w(T)^2}{\operatorname{rad}(T)^2}. $$若常数 $c$ 足够小，则 $C\sqrt m\,\operatorname{rad}(T)\le0.01w(T)$，因此 Theorem 9.7.2 给出
$$ 0.99B\subset AT\subset1.01B, $$其中 $B=w(T)B_2^m$。也就是说，把有界凸集 $T$ 随机投影到维数约为 $d(T)$ 的子空间后，它看起来几乎像圆球。
考虑 cube $T=[-1,1]^n$。由 (7.18)，$w(T)=\sqrt{2/\pi}\,n$，而 $\operatorname{diam}(T)=2\sqrt n$，所以有效维数满足 $d(T)\asymp n$。因此若 $m\le cn$，则以高概率
$$ 0.99B \subset A[-1,1]^n \subset 1.01B, $$其中 $B$ 是半径为 $\sqrt{2/\pi}\,n$ 的欧氏球。也就是说，把 $n$ 维立方体投影到 $m=cn$ 维子空间后，它看起来几乎像圆球。Figure 9.9 展示了这一现象。
第 7.6 节和第 9.2.2 节说明：集合 $T$ 到 $\mathbb R^n$ 中 $m$ 维随机子空间的随机投影 $P$ 会经历相变。
在高维情形，也就是 $m\gtrsim d(T)$ 时，投影会按 $\sqrt{m/n}$ 的量级缩小直径：
$$ \operatorname{diam}(PT) \asymp \sqrt{\frac mn}\operatorname{diam}(T). $$此外，additive Johnson-Lindenstrauss Lemma 9.2.4 说明，在这个 regime 中，随机投影近似保持 $T$ 的几何，即所有点间距离大约按同一比例缩小。
在 low-dimensional regime，也就是 $m\lesssim d(T)$ 时，缩小停止：
$$ \operatorname{diam}(PT) \asymp w_s(T) \asymp \frac{w(T)}{\sqrt n}, $$无论 $m$ 多小都如此。Dvoretzky-Milman 定理解释了原因：此时 $PT$ 近似为一个半径约为 $w_s(T)$ 的圆球，而圆球在进一步投影下不会继续按原集合直径缩小。Exercises 9.41-9.43 会分别处理 Dvoretzky-Milman 的高概率版本、高斯点云的低维近圆性，以及真正随机投影版本。
9.8 Notes
矩阵偏差不等式（Theorem 9.1.1）及其证明来自 [213]，不过很多相关结果更早就已经存在。对高斯矩阵 $A$ 以及单位球面上的集合 $T$，它可以从高斯比较不等式推出：上界来自 Sudakov-Fernique（Theorem 7.2.8），下界来自 Gordon（Theorem 7.2.9）。Schechtman [295] 证明了高斯 $A$ 与一般范数情形下的矩阵偏差不等式；我们在第 9.6 节中介绍了这一版本。对于次高斯 $A$，相关版本见 [187, 236, 103]；可参见 [213, Section 3] 中的比较。关于二次型过程，一个特别干净的结果见 [79, Theorem 3.2.1]。其他推广还包括稀疏 $A$ 的版本 [54]、$\ell^p$ 范数的版本 [301]，以及独立列的版本 [277]。
Theorem 9.1.1 中关于 $K$ 的二次依赖后来在 [176] 中改进为最优的 $K\sqrt{\log K}$。这会自动改进所有从 Theorem 9.1.1 推出的结果里对次高斯范数的依赖，例如 Theorems 3.1.1、4.6.1、5.3.1、9.3.1、9.3.4、9.4.4，Proposition 9.2.1，Corollary 9.4.8，等等。
关于集合随机投影的界（Proposition 9.2.1）的一个版本可追溯到 V. Milman [245]；见 [21, Proposition 5.7.1]。
低维分布协方差估计的 Theorem 9.2.2 归功于 V. Koltchinskii 与 K. Lounici [190]；他们使用了另一种同样基于主控测度定理的方法。R. van Handel [331] 对高斯分布给出了另一个证明，使用解耦、条件化和 Slepian 引理。对高斯矩阵，Theorem 9.2.2 的界是紧的；现在已有许多推广，参考文献见第 4 章末尾。
加性 Johnson-Lindenstrauss 引理（Lemma 9.2.4）的一个版本来自 [213]。
$M^*$ 界（Theorem 9.3.1）在几何泛函分析中已有较长历史。早期版本来自 V. Milman [243, 244]；Pajor 和 Tomczak [269] 证明了一个对 $m$ 依赖正确的版本，Gordon 后来给出了具有精确常数的更尖锐形式 [143]。更多内容，包括证明与变体，可见 [21, Sections 7.3-7.4, 9.3]、[143, 233, 341]。本书 Theorem 9.3.1 的版本来自 [213]。
逃逸定理（Theorem 9.3.4）也称为 “网格逃逸”。它最早由 Y. Gordon [143] 对高斯矩阵证明，并利用他的比较不等式（Theorem 7.2.9）在 (9.14) 中得到尖锐常数。对球面凸集，已有匹配的下界 [308, 18]；在这种情形中，甚至可以用积分几何的工具精确计算击中概率 [18]。Oymak 和 Tropp [267] 说明了如何把该结果推广到高斯情形之外。本书 Theorem 9.3.4 的版本来自 [213]。
第 9.4-9.5 节中的应用来自高维统计学与信号处理，特别是压缩感知。教程 [341] 对这两类问题给出了统一处理，本章遵循了其中的思路。书籍 [67, 157, 344, 137] 讨论统计方面，综述 [91] 与书籍 [127] 侧重信号处理方面。
第 9.4.1 节中基于 $M^*$ 界的恢复方法源于 [341]，其中包含 Theorem 9.4.4 与 Corollary 9.4.8 的多种版本。
综述 [93] 对第 9.4.3 节中讨论的低秩矩阵恢复问题作了全面综述。我们的表述基于 [341, Section 10]。
第 9.5 节中的精确稀疏恢复发现于压缩感知领域；见 [91] 以及书籍 [127]。通过逃逸定理的方法（第 9.5.1 节）最早发现于 [290]；这里我们大致遵循 [341, Section 9]。另见 [80, 307]，尤其是 [322]，其中有逃逸定理在稀疏恢复中的应用。关于精确恢复所需观测数的尖锐界最早由 [112] 证明，随后在 [111, 108, 109, 110] 中推广。更一般的集合 $T$ 和矩阵 $A$ 的相变见 [18, 266, 267]。
基于 RIP 的稀疏恢复方法（第 9.5.2 节）由 E. Candes 和 T. Tao [73] 开创；全面介绍见 [127, Chapter 6]。Theorem 9.5.6 的一个版本出现在他们的工作中，而我们的证明基于 Y. Plan 的一个论证，类似于 [70]。随机矩阵满足 RIP（Theorem 9.5.7）是压缩感知的基石之一；见 [127, 340]。
关于二次型过程的偏差（Exercise 9.5），见 [79, Theorem 3.2.1]，那是一个非常相近的结果。
Exercises 9.19-9.21 讨论稀疏线性回归中的一个常用工具，即统计文献中的 Lasso（least absolute shrinkage and selection operator）。它由 R. Tibshirani [319] 开创。书籍 [157, 67, 344] 对带稀疏约束的统计问题作了全面介绍；这些书也讨论 Lasso 及其许多变体。
基于零空间性质的稀疏恢复（Exercise 9.32）可追溯到 Cohen、Dahmen 和 DeVore [88]，见 [281, 127, 344]。
Garnaev-Gluskin 界（Exercise 9.28）最早由 [132] 证明，另见 [222] 与 [127, Chapter 10]。
一般矩阵偏差不等式（Theorem 9.6.3）及其证明归功于 G. Schechtman [295]。
Chevet 不等式的原始版本由 S. Chevet [84] 证明，其中的常数因子由 Y. Gordon [140] 改进；另见 [21, Section 9.4]、[210, Theorem 3.20] 与 [321, 7]。我们在 Theorem 9.7.1 中陈述的 Chevet 不等式版本可以从 Y. Gordon [140, 142] 的工作中重构出来；见 [210, Corollary 3.21]。
Dvoretzky-Milman 定理在泛函分析中有很长历史。A. Dvoretzky [117, 118] 证明了 A. Grothendieck 的一个猜想：任意 $n$ 维赋范空间都有一个 $m$ 维近似欧氏子空间，其中 $m=m(n)$ 随 $n$ 增大而趋于无穷。V. Milman 给出了该定理的概率证明 [242]，并开创了对最佳依赖 $m(n)$ 的研究。Theorem 9.7.2 归功于 V. Milman [242]；它是最优的 [247]，见 [21, Theorem 5.3.3]。教程 [23] 对 Dvoretzky-Milman 定理作了轻量介绍。关于 Dvoretzky-Milman 定理及其许多影响的完整阐述，可见 [21, Chapter 5 and Section 9.2]、[210, Section 9.1] 及其中参考文献。Dvoretzky-Milman 定理还有一种“分布式”版本，问题是 $n$ 维分布的随机 $m$ 维边缘分布是否近似正态；这一路线由 B. Klartag [186] 在对数凹分布中开创（凸体的中心极限定理），并由 E. Meckes [230] 在离散分布中开创。
Remark 9.7.5 中提到的相变现象由 V. Milman [245] 提出；见 [21, Proposition 5.7.1]。
Exercises
验证 Theorem 9.1.2 证明中用到的几何观察。设 $x,y\in\mathbb R^n$ 满足 $1=\|x\|_2\le\|y\|_2$，并令 $\bar y=y/\|y\|_2$。证明
$$ \|x-y\|_2 \le \|x-\bar y\|_2+\|\bar y-y\|_2 \le \sqrt2\,\|x-y\|_2. $$ 查看学习笔记：Exercise 9.1 证明从 Theorem 9.1.1 推出矩阵偏差的中心化版本：
$$ \mathbb E\sup_{x\in T} \left| \|Ax\|_2-\mathbb E\|Ax\|_2 \right| \le CK^2\gamma(T). $$ 查看学习笔记：Exercise 9.2 证明证明 Remark 9.1.5 中的结论：在 Theorem 9.1.1 的条件下，
$$ \mathbb E\sup_{x\in T} \left| \|Ax\|_2^2-m\|x\|_2^2 \right| \le CK^4\gamma(T)^2 + CK^2\sqrt m\,\operatorname{rad}(T)\gamma(T). $$ 查看学习笔记：Exercise 9.3 证明Theorem 9.1.1 假设随机矩阵的行是各向同性。现在去掉这个假设。令 $B$ 为 $m\times n$ 随机矩阵，其独立行 $B_i$ 满足
$$ \mathbb E B_iB_i^\mathsf T=\Sigma,\qquad \|\langle B_i,x\rangle\|_{\psi_2} \le K\|\langle B_i,x\rangle\|_{L^2} \quad\text{for any }x\in\mathbb R^n. $$证明对任意 $T\subset\mathbb R^n$，有
$$ \mathbb E\sup_{x\in T} \left| \|Bx\|_2-\sqrt m\,\|\Sigma^{1/2}x\|_2 \right| \le CK^2\gamma(\Sigma^{1/2}T). $$ 查看学习笔记：Exercise 9.4 证明Exercise 8.36 曾对次高斯过程证明经验均值偏离样本均值的界。现在通过扩展 Theorem 9.1.1，为 $L^2$ 均值做同类估计。
设 $\mathcal F$ 是定义在某个定义域 $\Omega$ 上的一族实值函数，并且是 star-shaped：若 $f\in\mathcal F$，则任意 $a\in[0,1]$ 都有 $af\in\mathcal F$。令 $X,X_1,\ldots,X_m$ 是 $\Omega$ 中的 i.i.d. 随机点。考虑 $\mathcal F$ 上的 $L^2$ metric
$$ d(f,g):=\bigl(\mathbb E(f(X)-g(X))^2\bigr)^{1/2}, $$并假设
$$ \|f(X)-g(X)\|_{\psi_2}\le Kd(f,g) \quad\text{for all }f,g\in\mathcal F. $$证明
$$ \mathbb E\sup_{f\in\mathcal F} \left| \left(\frac1m\sum_{i=1}^m f(X_i)^2\right)^{1/2} - \left(\mathbb Ef(X)^2\right)^{1/2} \right| \le \frac{CK^2\gamma_2(\mathcal F,d)}{\sqrt m}, $$右侧的 $\gamma_2$ 是第 8.5 节中的泛函。说明当 $T\subset S^{n-1}$ 时，这个结果如何包含 Theorem 9.1.1。
查看学习笔记：Exercise 9.5 证明证明 Theorem 9.1.1 对随机投影的版本。令 $P$ 是 $\mathbb R^n$ 到一个 $m$ 维随机子空间上的正交投影，该子空间在 Grassmannian $G_{n,m}$ 上均匀分布。证明对任意 $T\subset\mathbb R^n$，
$$ \mathbb E\sup_{x\in T} \left| \|Px\|_2-\sqrt{\frac mn}\|x\|_2 \right| \le \frac{C\gamma(T)}{\sqrt n}. $$ 查看学习笔记：Exercise 9.6 证明证明 Proposition 9.2.1 的高概率版本。令 $T\subset\mathbb R^n$ 为有界集，令 $A$ 是 $m\times n$ 随机矩阵，其行 $A_i$ 独立、各向同性且次高斯，并考虑次高斯投影 $P=A/\sqrt n$。证明对 $\varepsilon\gt 0$，
$$ \operatorname{diam}(PT) \le (1+\varepsilon)\sqrt{\frac mn}\operatorname{diam}(T) + CK^2w_s(T) $$以概率至少 $1-\exp(-c\varepsilon^2m/K^4)$ 成立。这里 $K=\max_i\|A_i\|_{\psi_2}$，$w_s(T)$ 是 $T$ 的球面宽度。
查看学习笔记：Exercise 9.7 证明为第 7.6 节中的原始模型证明 Proposition 9.2.1 的版本：令 $P$ 是到随机 $m$ 维子空间 $E\sim\operatorname{Unif}(G_{n,m})$ 上的正交投影。
查看学习笔记：Exercise 9.8 证明验证 Remark 9.2.3 中提到的协方差估计高概率保证。
查看学习笔记：Exercise 9.9 证明使用矩阵偏差不等式给出 Exercise 5.14 的另一种解法。请量化成功概率以及对次高斯范数的依赖。
查看学习笔记：Exercise 9.10 证明说明 Lemma 9.2.4 结论中的误差一般必须是绝对误差，而不能改成相对误差。
查看学习笔记：Exercise 9.11 证明我们已经对经过原点的随机截面证明了 $M^*$ 界（Theorem 9.3.1）。把它推广到所有仿射截面：
$$ \mathbb E\max_{z\in\mathbb R^n} \operatorname{diam}\bigl(T\cap(z+\ker A)\bigr) \le \frac{CK^2w(T)}{\sqrt m}. $$ 查看学习笔记：Exercise 9.12 证明证明 $M^*$ 界（Theorem 9.3.1）的高概率版本。
查看学习笔记：Exercise 9.13 证明令 $B_p^n$ 是 $\mathbb R^n$ 中的 unit $\ell^p$ 球。令 $E$ 是随机 $k$ 维子空间，其中 $1\le k\le0.99n$。
(a) 证明对所有 $p\in(1,\infty)$，
$$ \mathbb E\operatorname{diam}(B_p^n\cap E) \asymp_p n^{1/2-1/p}, $$其中 $\asymp_p$ 隐含的正数常数只允许依赖于 $p$。
(b) 验证：当 $p\le2$ 时，这个量等价于 $B_p^n$ 的内切欧氏球半径；当 $p\ge2$ 时，它等价于外接欧氏球半径。你能给出直观解释吗？
查看学习笔记：Exercise 9.14 证明通过令 $T$ 为 $\mathbb R^n$ 中某个子空间里的单位球面，说明逃逸定理（Theorem 9.3.4）对所有 $m\le n$ 在一般情形下都是最优的。
查看学习笔记：Exercise 9.15 证明这是逃逸定理的另一个版本。令 $T\subset S^{n-1}$ 为任意集合，并令 $\mathcal X\subset S^{n-1}$ 为一个 $N$ 点集。假设
$$ \sigma_{n-1}(T)\lt \frac1N, $$其中 $\sigma_{n-1}$ 是球面上的 normalized 表面积。证明存在一个 rotation $U\in O(n)$，使得
$$ UT\cap\mathcal X=\varnothing. $$ 查看学习笔记：Exercise 9.16 证明把 Theorem 9.4.4 的误差界推广到更强的均方误差：
$$ \mathbb E\|\hat x-x\|_2^2. $$ 查看学习笔记：Exercise 9.17 证明令 $T$ 是 $\mathbb R^n$ 中某个范数 $\|\cdot\|_T$ 的单位球。证明 Theorem 9.4.4 的结论也适用于如下优化程序：
$$ \text{minimize }\|x'\|_T \quad\text{subject to}\quad y=Ax'. $$ 查看学习笔记：Exercise 9.18 证明把约束恢复结果（Theorem 9.4.4）推广到带噪声模型 (9.16)：
$$ y=Ax+w,\qquad x\in T, $$其中 $w$ 是未知噪声向量，甚至可以依赖于 $A$。为了恢复 $x$，在 $T$ 中找一个尽可能拟合观测 $y$ 的向量：
$$ \text{minimize }\|y-Ax'\|_2 \quad\text{subject to}\quad x'\in T. $$证明解 $\hat x$ 满足
$$ \mathbb E\|\hat x-x\|_2 \lesssim \frac{K^2w(T)+\|w\|_2}{\sqrt m}. $$ 查看学习笔记：Exercise 9.19 证明把 Remark 9.4.7 更严谨地写出来。令 $x\in\mathbb R^n$ 为任意向量，令 $A$ 是 $m\times n$ 随机矩阵，其行 $A_i$ 独立、各向同性且次高斯。考虑带噪线性模型
$$ y=Ax+w, $$其中 $w\in\mathbb R^m$ 是任意噪声向量，可以依赖于 $A$。从 $y$ 和 $A$ 恢复 $x$ 时，考虑无约束凸优化问题
$$ \text{minimize }\|y-Ax'\|_2^2+\lambda\|x'\|_T \quad\text{over all }x'\in\mathbb R^n, $$其中 $\|\cdot\|_T$ 是任意范数，$\lambda\gt 0$ 是调节参数。证明如果选择
$$ \lambda\asymp\frac{\|w\|_2^2}{\|x\|_T}, $$则解 $\hat x$ 满足
$$ \mathbb E\|\hat x-x\|_2 \lesssim \frac{K^2w(T)\|x\|_T+\|w\|_2}{\sqrt m}, $$其中 $T$ 是范数 $\|\cdot\|_T$ 的单位球，$K=\max_i\|A_i\|_{\psi_2}$。
查看学习笔记：Exercise 9.20 证明把 Exercise 9.20 专门化到 $\ell^1$ 范数，分析稀疏回归中常用的 Lasso。设 $x\in\mathbb R^n$ 是 $s$-稀疏，且 $A$ 是 $m\times n$ 随机矩阵，其行 $A_i$ 独立、各向同性且次高斯。考虑带噪线性模型
$$ y=Ax+w. $$从 $y$ 和 $A$ 恢复 $x$ 时，考虑无约束凸优化问题
$$ \text{minimize }\|y-Ax'\|_2^2+\lambda\|x'\|_1 \quad\text{over all }x'\in\mathbb R^n. $$证明如果选择 $\lambda\asymp\|w\|_2^2/\|x\|_1$，则解 $\hat x$ 满足
$$ \mathbb E\|\hat x-x\|_2 \lesssim \frac{K^2\sqrt{s\log n}+\|w\|_2}{\sqrt m}, $$其中 $K=\max_i\|A_i\|_{\psi_2}$。
查看学习笔记：Exercise 9.21 证明令 $A$ 是一个处于一般位置的 $m\times n$ 矩阵。你可以自行选择一个方便的一般位置定义。
(a) 证明如果 $m\ge2\|x\|_0$，那么方程 $y=Ax$ 的解如果存在就是唯一的。
(b) 在这种情况下，如果你已知 $x$ 的支撑集，也就是哪些元素非零，那么如何高效地算法求出 $x$？
查看学习笔记：Exercise 9.22 证明在 (9.21) 中，我们把 $\|x\|_0$ 定义为向量 $x$ 的非零坐标个数。
(a) 验证 $\|\cdot\|_0$ 不是 $\mathbb R^n$ 上的范数。
(b) 验证当 $0\lt p\lt 1$ 时，$\|\cdot\|_p$ 不是 $\mathbb R^n$ 上的范数。Figure 9.10 说明此时单位球不是 convex。
(c) 证明对每个 $x\in\mathbb R^n$，
$$ \|x\|_0 = \lim_{p\to0+}\|x\|_p^p. $$
把稀疏恢复（Corollary 9.4.8）推广到近似稀疏信号。
(a) 证明任意 $s$-稀疏信号 $x$ 都可以从观测 $y=Ax$ 中通过求解
$$ \text{minimize }\|x'\|_1 \quad\text{subject to}\quad y=Ax' $$来恢复，其解 $\hat x$ 满足
$$ \mathbb E\|\hat x-x\|_2 \le CK^2\sqrt{\frac{s\log n}{m}}\,\|x\|_2. $$(b) 说明近似稀疏信号也有类似结果。请陈述并证明一个这样的保证。
查看学习笔记：Exercise 9.24 证明考虑 unit $s$-稀疏向量的集合
$$ S_{n,s}:= \{x\in\mathbb R^n:\|x\|_0\le s,\ \|x\|_2\le1\}, \tag{9.46} $$以及 truncated $\ell^1$ 球
$$ T_{n,s}:=\sqrt s B_1^n\cap B_2^n = \{x\in\mathbb R^n:\|x\|_1\le\sqrt s,\ \|x\|_2\le1\}. \tag{9.47} $$证明
$$ \operatorname{conv}(S_{n,s}) \subset T_{n,s} \subset 2\operatorname{conv}(S_{n,s}). $$为了证明第二个包含关系，固定 $x\in T_{n,s}$，并把 $x$ 的支撑集分解成互不相交的子集 $I_1,I_2,\ldots$，其中 $I_1$ 对应 $x$ 中绝对值最大的 $s$ 个系数，$I_2$ 对应接下来 $s$ 个系数，依此类推。证明
$$ \sum_{i\ge1}\|x_{I_i}\|_2\le2, $$其中 $x_I$ 表示 $x$ 限制在坐标集合 $I$ 上的向量。
查看学习笔记：Exercise 9.25 证明使用 Exercise 9.25 证明
$$ w(T_{n,s}) \le 2w(S_{n,s}) \le C\sqrt{s\log(en/s)}. $$把稀疏恢复保证（Corollary 9.4.8）中的对数因子改进为
$$ \mathbb E\|\hat x-x\|_2 \le CK^2\sqrt{\frac{s\log(en/s)}{m}}, $$从而说明 $m\gtrsim s\log(en/s)$ 个观测足够。
查看学习笔记：Exercise 9.26 证明证明 unit $s$-稀疏向量集合 (9.46) 及其近似凸包 (9.47) 具有如下高斯宽度：
$$ w(T_{n,s}) \asymp w(S_{n,s}) \asymp \sqrt{s\log(en/s)}, $$其中 $\asymp$ 隐含 absolute positive constants。
查看学习笔记：Exercise 9.27 证明改进 Example 9.3.2 中随机切片 $\ell^1$ 球的对数因子：
$$ \mathbb E\operatorname{diam}(B_1^n\cap E) \lesssim \sqrt{\frac{\log(en/m)}{m}}. $$特别地，(9.13) 中的对数因子可以被去掉。
查看学习笔记：Exercise 9.28 证明为第 9.4.3 节中的低秩恢复推出若干版本。
(a) 证明 Corollary 9.4.11 的结论也适用于如下优化程序：
$$ \text{minimize }\|X'\|_* \quad\text{subject to}\quad y_i=\langle A_i,X'\rangle,\quad i=1,\ldots,m. $$(b) 把矩阵恢复结果推广到近似低秩矩阵。
(c) 把矩阵恢复结果推广到 $d_1\times d_2$ 矩阵。
查看学习笔记：Exercise 9.29 证明给出 Theorem 9.5.1 证明的几何解释，参见 Figure 9.7b。该证明对切锥 $T(x)$ 及其球面部分 $S(x)$ 说明了什么？
查看学习笔记：Exercise 9.30 证明把精确稀疏恢复结果（Theorem 9.5.1）推广到带噪观测 $y=Ax+w$。请相应修改恢复程序 (9.27)。
查看学习笔记：Exercise 9.31 证明下面是保证精确恢复的一个有用条件。称一个 $m\times n$ 矩阵 $A$ 满足阶 $s$ 的零空间性质，如果对任意非零 $h\in\ker(A)$ 和任意 $s$ 元子集 $S\subset\{1,\ldots,n\}$，都有
$$ \|h_S\|_1\lt \|h_{S^c}\|_1. $$(a) 证明 $A$ 满足零空间性质当且仅当每个 $s$-稀疏向量 $x\in\mathbb R^n$ 都是 (9.27) 在 $y=Ax$ 时的唯一解。
(b) 证明当 $m\gtrsim s\log(en/s)$ 时，随机矩阵 $A$ 以高概率满足零空间性质。请像 Theorem 9.5.7 那样把该结论精确表述出来。
查看学习笔记：Exercise 9.32 证明令 $P$ 是 $\mathbb R^n$ 到一个随机 $m$ 维子空间上的正交投影，该子空间在 Grassmannian 上均匀分布。
(a) 证明 $P$ 满足 RIP，形式与 Theorem 9.5.7 类似，只差一个归一化。
(b) 推出来自随机投影的 Theorem 9.5.1 精确恢复版本。
查看学习笔记：Exercise 9.33 证明令 $f:V\to\mathbb R$ 是向量空间 $V$ 上的次可加函数。证明
$$ f(x)-f(y)\le f(x-y) \quad\text{for all }x,y\in V. $$ 查看学习笔记：Exercise 9.34 证明把 Theorem 9.6.3 推广到 $m\times n$ 矩阵 $A$ 的行是独立 $N(0,\Sigma)$ 随机向量的情形。证明
$$ \mathbb E\sup_{x\in T} \left| f(Ax)-\mathbb Ef(Ax) \right| \le Cb\,\gamma(\Sigma^{1/2}T). $$ 查看学习笔记：Exercise 9.35 证明证明 Theorem 9.6.3 的高概率版本。
查看学习笔记：Exercise 9.36 证明使用一般矩阵偏差不等式（Theorem 9.6.3），为 $\mathbb R^m$ 上任意范数推出 Johnson-Lindenstrauss 引理的版本，而不仅限于欧氏范数。
查看学习笔记：Exercise 9.37 证明把 Exercise 9.37 专门化到 $\ell^1$ 范数。取 $\mathcal X$ 为 $\mathbb R^n$ 中 $N$ 个点组成的集合，令 $A$ 为 $m\times n$ 高斯矩阵，其元素独立且服从 $N(0,1)$，并取任意 $\varepsilon\in(0,1)$。假设
$$ m\ge C(\varepsilon)\log N. $$证明以高概率，矩阵
$$ Q=\sqrt{\frac\pi2}\,\frac1m A $$满足
$$ (1-\varepsilon)\|x-y\|_2 \le \|Qx-Qy\|_1 \le (1+\varepsilon)\|x-y\|_2 \quad\text{for all }x,y\in\mathcal X. $$ 查看学习笔记：Exercise 9.38 证明把 Exercise 9.37 专门化到 $\ell^\infty$ 范数。取 $\mathcal X$ 为 $\mathbb R^n$ 中 $N$ 个点组成的集合，令 $A$ 为 $m\times n$ 高斯矩阵，其元素独立且服从 $N(0,1)$，并取任意 $\varepsilon\in(0,1)$。假设
$$ m\ge N^{C(\varepsilon)}. $$证明以高概率，矩阵
$$ Q=C(\log m)^{-1/2}A $$满足
$$ (1-\varepsilon)\|x-y\|_2 \le \|Qx-Qy\|_\infty \le (1+\varepsilon)\|x-y\|_2 \quad\text{for all }x,y\in\mathcal X, $$其中绝对常数 $C$ 可适当选择。注意在此情形下 $m\ge N$，所以 $Q$ 不是降维映射，而是嵌入。
查看学习笔记：Exercise 9.39 证明证明：对闭且有界的集合 $V\subset\mathbb R^m$，它的支撑函数接近欧氏范数当且仅当其凸包接近欧氏球。具体地，对 $r_-,r_+\ge0$，证明
$$ r_-B_2^m\subset\operatorname{conv}(V)\subset r_+B_2^m $$当且仅当
$$ r_-\|y\|_2 \le \sup_{x\in V}\langle x,y\rangle \le r_+\|y\|_2 \quad\text{for all }y\in\mathbb R^m. $$ 查看学习笔记：Exercise 9.40 证明陈述并证明 Dvoretzky-Milman 定理的高概率版本。
查看学习笔记：Exercise 9.41 证明考虑 i.i.d. 随机向量 $g_1,\ldots,g_n\sim N(0,I_m)$。假设
$$ m\le c\log n. $$证明这些点的凸包以高概率近似为半径 $\asymp\sqrt{\log n}$ 的欧氏球，参见 Figure 9.9。
查看学习笔记：Exercise 9.42 证明我们把 Dvoretzky-Milman 定理表述为 “高斯 projections” 的版本。请证明它对真正的随机投影也成立：令 $P$ 是 $\mathbb R^n$ 到一个随机 $m$ 维子空间上的正交投影。在相同假设下，结论应为
$$ (1-\varepsilon)B \subset \operatorname{conv}(PT) \subset (1+\varepsilon)B, $$其中 $B$ 是半径为 $w_s(T)$ 的欧氏球，$w_s(T)$ 是 $T$ 的球面宽度（回忆 Definition 7.5.4）。
查看学习笔记：Exercise 9.43 证明