信数 Notes

未分类

---

贪心的证明：

Thm. 对于任意 $k$ ，贪心算法给出的解都是最优解。

考虑对 $k$ 归纳， $k=1$ 时显然， $k\neq 1$ 时假设最优解是 $W$ ，贪心算法给出的解是 $v_1,v_2,\ldots v_k$ ，选 $W$ 的一组正交基 $w_1,\ldots w_k$ ，使得 $w_k$ 与 $v_1,\ldots v_{k-1}$ 正交（总是可以选出这样的 $w_k$ ，令 $v'_i$ 是 $v_i$ 在 $W$ 上的投影，从 $\langle v'_1,v'_2,\ldots v'_{k-1}\rangle^{\perp}$ 中选 $w_k$ 即可），可以看出 $\sqrt{\sum_{i=1}^k (\alpha\cdot w_i)^2}$ 就是 $\alpha$ 投影到 $W$ 上的长度。因此我们所证明的事情与 $\sum_{i=1}^k |Aw_i|^2\leq \sum_{i=1}^k |Av_i|^2$ 等价。

故根据归纳 $\sum_{i=1}^{k-1} |Aw_i|^2\leq \sum_{i=1}^{k-1}|Av_i|^2$ ，根据 $v_k$ 的定义有 $|Aw_k|\leq |Av_k|$ ，于是 $\sum_{i=1}^k |Aw_i|^2\leq \sum_{i=1}^k |Av_i|^2$ 。证毕

3.4

令 $u_i=\frac{1}{\sigma_i}v_i$ ，则由 $\forall 1\leq k\leq r, (\sum_{i=1}^r \sigma_i u_i v_i^T) v_k = \sigma_k u_k=Av_k$ ，以及 $\langle v_1,v_2,\ldots v_r\rangle^{\perp}=\ker A$ ，可知 $A= \sum_{i=1}^r \sigma_i u_i v_i^T$ ，称为 $A$ 的奇异值分解

注：当奇异值互异时奇异向量唯一(只差正负号)，否则从子空间中任选一组基

3.5

令 $A_k=\sum_{i=1}^k \sigma_i u_i v_i^T$ ，则 $A_k$ 在 Frobenius norm 下是 $A$ 的最佳 $k$ 阶逼近（即 $||A-A_k||_F$ 是最小的 ）。

Lemma. $A_k$ 的列向量是 $A$ 的列向量 $\alpha_1,\alpha_2,\ldots ,\alpha_n$ 在 $\langle v_1,v_2,\ldots v_{k}\rangle$ 上的投影。

由 $(\sum_{i=1}^k \sigma_i u_i v_i^T)\alpha=\sum_{i=1}^k Av_iv_i^T\alpha$ 容易看出。

假设 $B$ 是 Frobenius norm 下 $A$ 的最佳 $k$ 阶逼近，由 Frobenius norm 的定义可知 $B$ 的列向量一定是 $A$ 的列向量在 $\mathrm{col}\ B$ 下的投影（否则改成投影一定更优）。而 $\langle v_1,v_2,\ldots v_{k}\rangle$ 是 $k$ 维子空间中 $\sum_{i=1}^n|\alpha'_i|^2$ 最小的（ $\alpha'_i$ 为 $\alpha_i$ 在 $\langle v_1,v_2,\ldots v_{k}\rangle$ 上的投影），而 $A_k$ 的列向量 $\alpha_1,\alpha_2,\ldots ,\alpha_n$ 在 $\langle v_1,v_2,\ldots v_{k}\rangle$ 上的投影，故 $B=A_k$ 。

由于我们在计算 $Ax$ 的时候可以用 $A_kx=(\sum_{i=1}^k \sigma_i u_i v_i^T)x$ 来近似代替，从而把复杂度从 $O(nd)$ 降为 $O(k(n+d))$ ，因此我们会比较关心此时产生的误差，即 $A-A_k$ 的 2-norm ，定义为 $||A||_2=\max_{|x|\leq 1} |Ax|$ 。

3.6

Thm. $u_1,\ldots u_r$ 是正交向量组。

证明：若 $\delta=u_i\cdot u_j\neq 0(i<j)$ ，则令 $v'_i=\frac{v_i+\varepsilon v_j}{|v_i+\varepsilon v_j|}$ ，则 $Av_i'=\frac{\sigma_iu_i+\varepsilon \sigma_j v_j}{\sqrt{1+\varepsilon^2}}$ ，于是

$$u_i^T\left(\frac{\sigma_iu_i+\varepsilon \sigma_j v_j}{\sqrt{1+\varepsilon^2}}\right)>(\sigma_i+\varepsilon\sigma_j\delta)(1-\varepsilon^2/2)>\sigma_i-\varepsilon^2\sigma_i/2+\varepsilon\sigma_j\delta-\varepsilon^3\sigma_j\delta/2$$
通过适当选取 $\varepsilon$ 可使上式 $>\sigma_i$ ，故 $|Av_i'|>|Av_i|$ ，矛盾。

Lemma. $||A-A_k||_2=\sigma_{k+1}$

令 $x=\sum_{i=1}^n c_iv_i$ 容易看出 $|(A-A_k)x|=|\sum_{i=1}^n c_i\sum_{i=k+1}^n \sigma_i u_i v_i^Tv_i|=|\sum_{i=k+1}^n c_i\sigma_iu_i|$ 由于 $u_1,u_2,\ldots u_n$ 使正交向量组故显然 $c_{k+1}=1$ 时取到最大，为 $\sigma_{k+1}$ 。

Thm. $A_k$ 是 $A$ 在 2-norm 下的最佳 $k$ 阶近似（即 $||A-A_k||_2$ 最小 ）。

假设 $B$ 是 2-norm 下 $A$ 的最佳 $k$ 阶逼近，易知 $\dim \ker B\geq d-k$ ，故 $\ker B\cap\langle v_1,v_2,\ldots v_{k+1}\rangle$ 不为空，从中任取单位向量 $z$ ，有 $||A-B||_2\geq |(A-B)z|=|Az|$ ，易得 $|Az|=|(\sum_{i=1}^{k+1} \sigma_i u_i v_i^T)|\geq \sigma_{k+1}$ 。证毕。

由向量组 $u,v$ 正交，我们可以看出 $Av_i=\sigma_iu_i,A^Tu_i=\sigma_iv_i$ 。

3.7

考虑 $B=A^TA=\sum_{i,j} \sigma_i\sigma_jv_iu_i^Tu_jv_j^T=\sum_i \sigma_i^2 v_iv_i^T$ ， $B^2=\sum_{i,j}\sigma_i^2\sigma_j^2v_iv_i^Tv_jv_j^T=\sum_i \sigma_i^4 v_iv_i^T$。

故 $B^k=\sum_i \sigma_i^{2k} v_iv_i^T$ ，故若 $\sigma_1>\sigma_2$ ， $\frac{1}{\sigma_1^{2k}}B_k\to v_1v_1^T$ 。取 $x$ 使得 $c=x\cdot v_1\neq 0$ ，则 $\frac{1}{\sigma_1^{2k}}B_kx\to c\cdot v_1$ 。