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

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

奇异值分解

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

其中

  • $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$

那么

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

注意到我们有

因此:

  • $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}$

类似的,

因此:

  • $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}$的正交基

解释

奇异值分解

对应的框图为

从上图中可以看出,线性映射$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$的伪逆或Moore-Penrose逆

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

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

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

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

更一般的情形:

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

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

通过正则化求解伪逆

对于$\mu >0$,令$x_{\mu }$为最小化下式子的(唯一)解

即,

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

那么我们有

实际上,我们有

满SVD

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

现在做如下操作:

  • 找到$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}$:

那么我们有

上述分解被称为满SVD

线性变换下的单位球的像

满SVD:

给出了$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$

  • 可能的估计误差为椭球

  • $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|$,即

最小二乘的最优性:假设$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$

那么

从而

因此

这里利用了