EE263 Lecture 17 Symmetric matrices, quadratic forms, matrix norm and SVD

课程主页：https://see.stanford.edu/Course/EE263

这次回顾第十七讲，这一讲介绍了SVD。

奇异值分解

矩阵增益的完全情形由$A$的SVD给出：

$$A=U \Sigma V^{T}$$

其中

• $A \in \mathbb{R}^{m \times n}, {\operatorname {Rank}}(A)=r$
• $U \in \mathbb{R}^{m \times r}, U^{T} U=I$
• $V \in \mathbb{R}^{n \times r}, V^{T} V=I$
• $\Sigma=\operatorname{diag}\left(\sigma_{1}, \ldots, \sigma_{r}\right)$，其中$\sigma_{1} \geq \cdots \geq \sigma_{r}>0$

记

$$U=\left[u_{1} \cdots u_{r}\right], V=\left[v_{1} \cdots v_{r}\right]$$

那么

$$A=U \Sigma V^{T}=\sum_{i=1}^{r} \sigma_{i} u_{i} v_{i}^{T}$$

• $\sigma_i$是$A$的非零奇异值
• $v_i$是$A$的右（输入）奇异向量
• $u_i$是$A$的左（输出）奇异向量

注意到我们有

$$A^{T} A=\left(U \Sigma V^{T}\right)^{T}\left(U \Sigma V^{T}\right)=V \Sigma^{2} V^{T}$$

因此：

• $v_i$是$A^TA$的特征向量（对应于非零特征值）
• $\sigma_{i}=\sqrt{\lambda_{i}\left(A^{T} A\right)}$以及$\lambda_{i}\left(A^{T} A\right)=0,i>r$
• $|A|=\sigma_{1}$

类似的，

$$A A^{T}=\left(U \Sigma V^{T}\right)\left(U \Sigma V^{T}\right)^{T}=U \Sigma^{2} U^{T}$$

因此：

• $u_i$是$AA^T$的特征向量（对应于非零特征值）
• $\sigma_{i}=\sqrt{\lambda_{i}\left(A A^{T}\right)}$以及$\lambda_{i}\left(A A^{T}\right)=0,i>r$

不难看出我们有如下结论：

• $u_{1}, \dots u_{r}$为$\operatorname{range}(A)$的正交基
• $v_{1}, \dots v_{r}$为$\mathcal{N}(A)^{\perp}$的正交基

解释

奇异值分解

$$A=U \Sigma V^{T}=\sum_{i=1}^{r} \sigma_{i} u_{i} v_{i}^{T}$$

对应的框图为

从上图中可以看出，线性映射$y=Ax$可以分解为

• 计算$x$关于输入方向$v_{1}, \dots, v_{r}$的系数
• 对系数缩放$\sigma_i $
• 沿着输出方向$u_{1}, \dots, u_{r}$重构

和对称矩阵$A$的特征值分解不同，奇异值分解的输入和输出方向不同

• $v_1$为最敏感（最大收益）的输入方向
• $u_1$为最大收益的输出方向
• $Av_1 =\sigma_1 u_1$

Lecture 16 SVD应用

广义伪逆

假设$A\neq 0$，对应的奇异值分解为$A=U \Sigma V^{T}$，那么

$$A^{\dagger}=V \Sigma^{-1} U^{T}$$

为$A$的伪逆或Moore-Penrose逆

如果$A$是瘦，满秩矩阵，那么

$$A^{\dagger}=\left(A^{T} A\right)^{-1} A^{T}$$

给出了最小二乘近似解$x_{\mathrm{ls}}=A^{\dagger} y$

如果$A$是胖，满秩矩阵，那么

$$A^{\dagger}=A^{T}\left(A A^{T}\right)^{-1}$$

给出了最小范数解$x_{\ln }=A^{\dagger} y$

更一般的情形：

$$X_{\mathrm{ls}}=\left\{z |\|A z-y\|=\min _{w}\|A w-y\|\right\}$$

为最小二乘近似解的集合。

特别的，$x_{\text {pinv}}=A^{\dagger} y \in X_{\mathrm{ls}}$为$X_{\mathrm{ls}}$中范数最小的解，即$x_{\mathrm{pinv}}$为最小范数，最小二乘近似解。

通过正则化求解伪逆

对于$\mu >0$，令$x_{\mu }$为最小化下式子的（唯一）解

$$\|A x-y\|^{2}+\mu\|x\|^{2}$$

即，

$$x_{\mu}=\left(A^{T} A+\mu I\right)^{-1} A^{T} y$$

这里，$A^{T} A+\mu I>0$并且也可逆

那么我们有

$$\lim _{\mu \rightarrow 0} x_{\mu}=A^{\dagger} y$$

实际上，我们有

$$\lim _{\mu \rightarrow 0}\left(A^{T} A+\mu I\right)^{-1} A^{T}=A^{\dagger}$$

满SVD

对于$A \in \mathbb{R}^{m \times n}, {\operatorname {Rank}}(A)=r$，其SVD为

$$A=U_{1} \Sigma_{1} V_{1}^{T}= \left[\begin{array}{lll}{u_{1}} & {\cdots} & {u_{r}}\end{array}\right] \left[\begin{array}{lll}{\sigma_{1}} & {} \\ {} & {\ddots} & {} \\ {} & {} & {\sigma_{r}}\end{array}\right] \left[\begin{array}{c}{v_{1}^{T}} \\ {\vdots} \\ {v_{r}^{T}}\end{array}\right]$$

现在做如下操作：

• 找到$U_{2} \in \mathbb{R}^{m \times(m-r)}, V_{2} \in \mathbb{R}^{n \times(n-r)}$使得$U=\left[U_{1} U_{2}\right] \in \mathbb{R}^{m \times m}$以及$V=\left[V_{1} V_{2}\right] \in \mathbb{R}^{n \times n}$为正交矩阵

• 对$\Sigma_1$增加$0$行/列形成$\Sigma \in \mathbb{R}^{m \times n}$：

  $$\Sigma=\left[\begin{array}{c|c}{\Sigma_{1}} & {0_{r \times(n-r)}} \\ \hline 0_{(m-r) \times r } & {0_{(m-r) \times(n-r)}}\end{array}\right]$$

那么我们有

$$A=U_{1} \Sigma_{1} V_{1}^{T}= \left[\begin{matrix}{U_{1}} & | &U_{2}\end{matrix}\right] \left[\begin{array}{c|c}{\Sigma_{1}} & {0_{r \times(n-r)}} \\ \hline 0_{(m-r) \times r } & {0_{(m-r) \times(n-r)}}\end{array}\right] \left[\frac{V_{1}^{T}}{V_{2}^{T}}\right]$$

即

$$A=U \Sigma V^{T}$$

上述分解被称为满SVD

线性变换下的单位球的像

满SVD：

$$A=U \Sigma V^{T}$$

给出了$y=Ax$的解释：

• 旋转（用$V^T$）
• 沿着轴伸缩$\sigma_i $
• 填充$0$（$m>n$）或截断（$m<n$）来得到$m$向量
• 旋转（用$U$）

对应图像为

$\{A x ||x| \leq 1\}$为主轴为$\sigma_i u_i$的椭球。

估计/反转中使用SVD

假设$y=A x+v$，其中

• $y \in \mathbb{R}^{m}$为测量值
• $x \in \mathbb{R}^{n}$为需要估计的向量
• $v$为测量的噪声或误差

噪声的“范数上界”：我们假设$|v| \leq \alpha$，其余不知道任何信息。

• 考虑估计$\hat{x}=B y$，其中$BA=I$

• 估计或反转误差为$\tilde{x}=\hat{x}-x=B v$

• 可能的估计误差为椭球

  $$\tilde{x} \in \mathcal{E}_{\mathrm{unc}}=\{B v |\|v\| \leq \alpha\}$$

• $x=\hat{x}-\tilde{x} \in \hat{x}-\mathcal{E}_{\mathrm{unc}}=\hat{x}+\mathcal{E}_{\mathrm{unc}}$，即：真实的$x$落在不确定的椭球$ \mathcal{E}_{\mathrm{unc}}$，中心在估计值$\hat x$

• “好”估计给出“小”$\mathcal{E}_{\mathrm{unc}}$

$\mathcal{E}_{\mathrm{unc}}$的半轴为$\alpha \sigma_{i} u_{i}$，其中$\sigma_i ,u_i$分别为$B$的奇异值和奇异向量

不难看出最大范数误差为$\alpha|B|$，即

$$\|\hat{x}-x\| \leq \alpha \| B \|$$

最小二乘的最优性：假设$B A=I$是任意估计器，以及$B_{\mathrm{ls}}=A^{\dagger}$为最小二乘估计器

那么：

• $B_{\mathrm{ls}} B_{\mathrm{ls}}^{T} \leq B B^{T}$
• $\mathcal{E}_{\mathrm{ls}} \subseteq \mathcal{E}$
• $\left|B_{\mathrm{ls}}\right| \leq|B|$

即，最小二乘估计器给出最小的不确定椭球

最优性的证明

假设$A \in \mathbb{R}^{m \times n}, m>n$满秩

SVD：$A=U \Sigma V^{T},V$正交

假设$B_{\mathrm{ls}}=A^{\dagger}=V \Sigma^{-1} U^{T}$，以及$BA=I$

定义$Z=B-B_{\mathrm{ls}}$，所以$B=B_{\mathrm{ls}}+Z$

那么

$$Z A=Z U \Sigma V^{T}=B_{\mathrm{ls}} A-BA=0$$

从而

$$ZU=0$$

因此

$$\begin{aligned} B B^{T} &=\left(B_{\mathrm{ls}}+Z\right)\left(B_{\mathrm{ls}}+Z\right)^{T} \\ &=B_{\mathrm{ls}} B_{\mathrm{ls}}^{T}+B_{\mathrm{ls}} Z^{T}+Z B_{\mathrm{ls}}^{T}+Z Z^{T} \\ &=B_{\mathrm{ls}} B_{\mathrm{ls}}^{T}+Z Z^{T} \\ & \geq B_{\mathrm{ls}} B_{\mathrm{ls}}^{T} \end{aligned}$$

这里利用了

$$Z B_{\mathrm{ls}}^{T}=(Z U) \Sigma^{-1} V^{T}=0$$