第十周作业
1. 最小二乘的目标是$\min{|Ax-b|_2}$，证明最小二乘的最优解$x^*$满足$A^TAx=A^Tb$
2. 在课上，我们介绍了一种求近似最小二乘的方法：
随机选择一个矩阵$S$，计算$SA$ 和$Sb$，然后求解$\min\limits_{x \in R^d} |SAx - Sb|_2$得到$x’$ 作为精确解$x^*$ 的近似解。
我们证明了如果$S$ 是$(d+1)$-维空间$[A, b]$ 的子空间嵌入（Subspace Embedding），那么$x’$ 有概率满足
之前我们要求$S$ 至少要有$d/\epsilon^2$ 行，现在我们将说明$S$ 可以只要$O(d/\epsilon)$ 行。
(a) 令$U \in R^{n \times r}$ 为$A$ 矩阵列向量张成空间的标准正交基（orthonormal basis），其中$r = \text{rank}(A)$。证明：
如果$x’ = \arg \min\limits_{x \in R^d} |SUx - Sb|_2$ 满足
那么$y’ = \arg \min\limits_{y \in R^d} |SAy - Sb|_2$ 满足
证：
由于 $U$ 是 $A$ 的列空间的标准正交基，我们有 $A = U R$，其中 $R$ 是一个满秩矩阵。因此，对于任意 $y$，可以找到一个 $x$ 使得 $y = Rx$，从而 $|Ay - b|_2 = |ARx - b|_2 = |Ux - b|_2$。
因此，$\min\limits_y |Ay - b|_2 = \min\limits_x |Ux - b|_2$。两边矩阵同乘$S$，有$\min\limits_y |S(Ay - b)|_2 = \min\limits_x |S(Ux - b*)|_2$，即$y’ = Rx’$。代入$|Ay - b|_2 = |Ux - b|_2$ 得 $|Ay’ - b|_2 = |Ux’ - b|_2$。
又因为 $|Ux’ - b|_2 \leq (1 + \epsilon) \min\limits_x |Ux - b|_2$，所以 $|Ay’ - b|_2 \leq (1 + \epsilon) \min\limits_y |Ay - b|_2$
(b)
因此我们只要证明对于$O(d/\epsilon)$ 行的矩阵$S$$x’ = \arg \min\limits_{x \in R^d} |SUx - Sb|_2$ 能够推出
令$x^* = \arg \min\limits_x |Ux - b|_2$，证明：
证：
记 $r = b - Ux^$ 为残差向量，即 $|Ux^ - b|_2 = |r|_2$。目标是最小化 $|Ux - b|_2$，而 $x^*$ 是最优解。
对于任意 $x’$，有$ |Ux’ - b|_2^2 = |r + U(x’ - x^*)|_2^2$。
由于 $U$ 的列是正交的，因此 $|Ux’ - b|_2^2 = |r|_2^2 + |U(x’ - x^)|_2^2$，即 $|Ux’ - b|^2_2 = |Ux^ - b|^2_2 + |U(x’ - x^*)|^2_2$，得证。
(c)* 证明：
如果$S$ 是一个由独立同分布（i.i.d., independent and identical distribution）均值为$0$，方差为$1/k$ 的高斯随机变量组成的$k \times n$ 的矩阵，其中$k = O(d/\epsilon)$，那么$|U(x’ - x^)|^2_2 = O(\epsilon)|Ux^ - b|^2_2。$
你在证明中会需要用到：
(1) $S$ 是一个任意确定的$d$-维子空间的$(1 \pm 1/2)$ 近似子空间嵌入；
(2) $S$ 满足近似矩阵乘（approximate matrix product），这两项可以作为结论直接使用。
你可能还需要用到$x$ 和$x’$ 的特定形式：$x’ = (SU)^{-}Sb, \quad x^* = U^Tb$，对于一个线性独立的矩阵$C$，$C^{-} = (C^TC)^{-1}C^T。$
证：
根据假设，$S$ 是一个任意确定的 $d$-维子空间的 $(1 \pm 1/2)$ 近似子空间嵌入，因此对任意向量 $v$，有$|Sv|_2^2 \approx (1 \pm \frac{1}{2}) |v|_2^2$
将 $v$ 替换为 $Ux’ - b$ 和 $Ux^* - b$，得到：
和
由于 $x’$ 是通过最小化 $|SUx - Sb|_2$ 得到的，所以有 $|SUx’ - Sb|_2^2 \leq |SUx^* - Sb|_2^2$，即：
所以，$\frac{1}{2} |Ux’ - b|_2^2 \leq |S (Ux’ - b)|_2^2 \leq |S (Ux^ - b)|_2^2 \leq \frac{3}{2} |Ux^ - b|_2^2$，即：
又因为由(b)得：$|Ux’ - b|^2_2 = |Ux^ - b|^2_2 + |U(x’ - x^)|^2_2$，所以
由(b)得：$|Ux’ - b|^2_2 = |Ux^ - b|^2_2 + |U(x’ - x^)|^2_2$，由(a)得$|Ux’ - b|_2 \leq |Ux^* - b|_2\text？$，所以
所以$|U(x’ - x^)|^2_2= O(\epsilon)|Ux^ - b|_2^2$
