4. 奇异值分解、广义逆与最小二乘法

接下来我们从奇异值分解开始，进一步推出广义逆，再由广义逆推出最小二乘法，这篇笔记将主要讨论其中的几何意义

$$奇异值分解\to 广义逆\to 最小二乘法$$

奇异值分解(SVD)

奇异值分解(SVD)

设 $A$ 是 $m\times n$ 实矩阵, $\text{rank }A=r$, 则存在 $m$ 阶正交矩阵 $U$ 与 $n$ 阶正交矩阵 $V$, 使得 $A=U\left(\begin{array}{cc}\Sigma & O\\ O& O\end{array}\right)V^T$, 其中 $\Sigma =\text{diag}({\sigma }_1,{\sigma }_2,\dots ,{\sigma }_r)$, 而 ${\sigma }_1\ge {\sigma }_2\ge \cdots \ge {\sigma }_r>0$

证明过程参考矩阵的标准型与分解 > 奇异值分解，方便起见，接下来我们直接记 $A=U\Sigma V^T$ 由于 $U,V$ 为正交矩阵，$\Sigma$ 为对角矩阵，不难看出奇异值分解的几何意义就是:

$$第一次旋转(V^T)\to 沿坐标轴的拉伸(\Sigma )\to 第二次旋转(U)$$

一个简单的例子是，假设 $A$ 是一个 $2\times 2$ 满秩矩阵，那么矩阵 $A$ 作用于一个单位圆，必然会将其映射成一个椭圆。

广义逆(Moore-Penrose 逆)

Moore–Penrose 广义逆

矩阵 $A^{+}$ 是 $A$ 的 Moore–Penrose 逆，当且仅当满足四个条件：

1. $A{A}^{+}A=A$
2. $A^{+}A{A}^{+}=A^{+}$
3. $(A{A}^{+}{)}^T=A{A}^{+}$
4. $(A^{+}A{)}^T=A^{+}A$

现在我们用奇异值分解构造广义逆，首先 $A$ 可分解为

$$A=U\left(\begin{array}{cc}\Sigma & O\\ O& O\end{array}\right)V^T$$

其中 $\Sigma =\text{diag}({\sigma }_1,{\sigma }_2,\dots ,{\sigma }_r)$ 不难看出对角矩阵 $\Sigma$ 的广义逆记为

$${\Sigma }^{+}=\left[\begin{array}{cc}\mathrm{diag}(1/{\sigma }_1,\dots ,1/{\sigma }_r)& 0\\ 0& 0\end{array}\right]\in {\mathbb{R}}^{n\times m}.$$

于是定义：

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

现在来验证上面的4个条件

• $A{A}^{+}A=(U\Sigma V^T)(V{\Sigma }^{+}{U}^T)(U\Sigma V^T)=U\Sigma {\Sigma }^{+}\Sigma V^T=U\Sigma V^T=A$
• $A^{+}A{A}^{+}=V{\Sigma }^{+}{U}^{T}U\Sigma V^{T}V{\Sigma }^{+}{U}^T=V{\Sigma }^{+}\Sigma {\Sigma }^{+}{U}^T=V{\Sigma }^{+}{U}^T=A^{+}$
• $A{A}^{+}$ 与 $A^{+}A$ 都是正交投影矩阵，因此对称。

---

在矩阵的Kronecker积下，有如下结论

逆矩阵情形

若 $A,B$ 都是可逆矩阵，则 $A\otimes B$ 也是可逆矩阵，并且

$$(A\otimes B{)}^{-1}=A^{-1}\otimes B^{-1};$$

而上面的结论对于Moore–Penrose 逆矩阵同样成立

Moore–Penrose 逆矩阵情形

$$(A\otimes B{)}^{+}=A^{+}\otimes B^{+}.$$

证明: 由奇异值分解

$$A=U_A{\Sigma }_A{V}_A^{\ast },B=U_B{\Sigma }_B{V}_B^{\ast },$$

那么由性质 $(A\otimes C)(B\otimes D)=(AB)\otimes (CD)$，我们有

$$A\otimes B=(U_A\otimes U_B)({\Sigma }_A\otimes {\Sigma }_B)(V_A\otimes V_B{)}^{\ast },$$

这就是 Kronecker 积的 SVD。 于是其广义逆为

$$(A\otimes B{)}^{+}=(V_A\otimes V_B)({\Sigma }_A\otimes {\Sigma }_B{)}^{+}(U_A\otimes U_B{)}^{\ast }.$$

容易计算对角奇异值矩阵的广义逆满足

$$({\Sigma }_A\otimes {\Sigma }_B{)}^{+}={\Sigma }_A^{+}\otimes {\Sigma }_B^{+},$$

最终得到结论：

$$(A\otimes B{)}^{+}=A^{+}\otimes B^{+}.$$

实际上由 $ABA=A,BAB=B$，能推出 $AB,BA$ 均为幂等矩阵

例

$A$ 为 $n$ 阶矩阵，证明存在矩阵 $B$，使得 $AB,BA$ 均为幂等矩阵

有了上面的结论后，这里的 $B$ 就是 $A$ 的广义逆矩阵 $A^{+}$，而且我们能通过奇异值分解直接计算出来 $B$

---

现在来看一下Moore–Penrose广义逆的几何意义

Moore–Penrose广义逆的几何意义

将 $A,B$ 看作线性映射，$A:{\mathbb{R}}^n\to {\mathbb{R}}^m，B$ 为 $A$ 的广义逆。那么 $BA$ 是 ${\mathbb{R}}^n$ 到 $(\mathrm{Ker}A{)}^{\perp }$ 上的正交投影算子，$AB$ 是 ${\mathbb{R}}^m$ 到 $\mathrm{Im}A$ 上的正交投影算子

证明: 由奇异值分解

$$AB=(U\Sigma V^T)(V{\Sigma }^{+}{U}^T)=U(\Sigma {\Sigma }^{+})U^T$$

其中，$\Sigma {\Sigma }^{+}$ 是一个对角线上前 $r$ 个元素为 $1$、其余全为 $0$ 的对角矩阵，设 $U=(u_1,...,u_m)$，于是

$$U\left(\begin{array}{cc}{I}_r& 0\\ 0& 0\end{array}\right)U^T=\sum _{i=1}^r{u}_i{u}_i^T$$

现在 $\forall x\in {\mathbb{R}}^m$，${\sum }_{i=1}^r{u}_i{u}_i^{T}x={\sum }_{i=1}^r⟨x,u_i⟩u_i\in \mathrm{Im}A$

同理，有

$$BA=(V{\Sigma }^{+}{U}^T)(U\Sigma V^T)=V({\Sigma }^{+}\Sigma )V^T$$

其中，${\Sigma }^{+}\Sigma =\left(\begin{array}{cc}{I}_r& 0\\ 0& 0\end{array}\right)$ ，现在 $\forall y\in {\mathbb{R}}^m$ ，$V\left(\begin{array}{cc}{I}_r& 0\\ 0& 0\end{array}\right)V^{T}y={\sum }_{i=1}^r⟨y,v_i⟩v_i$ ，也就是 $BA$ 将 $y$ 变为了在由 $\{v_1,v_2,\dots ,v_r\}$ 张成的子空间上的正交投影，我们记这个子空间为 $W=\mathrm{span}(v_1,v_2,\dots ,v_r)$ 另一方面，设 $x\in \mathrm{Ker}A$，于是 $U\Sigma V^{T}x=0\to \Sigma V^{T}x=0$，我们将 $V^{T}x$ 写成内积的形式，即 $V^{T}x=\left(\begin{array}{c}⟨v_1,x⟩\\ ⟨v_2,x⟩\\ ⋮\\ ⟨v_n,x⟩\end{array}\right)$。代入上式并展开矩阵乘法：

$$\left(\begin{array}{ccccc}{\sigma }_1& & & & \\ & \ddots & & & \\ & & {\sigma }_r& & \\ & & & 0& \\ & & & & \ddots \end{array}\right)\left(\begin{array}{c}⟨v_1,x⟩\\ ⋮\\ ⟨v_r,x⟩\\ ⟨v_{r+1},x⟩\\ ⋮\\ ⟨v_n,x⟩\end{array}\right)=\left(\begin{array}{c}0\\ ⋮\\ 0\\ 0\\ ⋮\\ 0\end{array}\right)$$

要使得这个等式成立，必须满足：

$${\sigma }_i⟨v_i,x⟩=0⟹⟨v_i,x⟩=0(\text{对于 }i=1,2,\dots ,r)$$

这意味着 $\mathrm{Ker}A$ 只能由后面 $n-r$ 个基向量张成，即 $\mathrm{Ker}A=\mathrm{span}(v_{r+1},\dots ,v_n)$，那么根据正交补的定义，$\mathrm{Ker}A$ 的正交补 $(\mathrm{Ker}A{)}^{\perp }$ 自然就是由前面 $r$ 个基向量张成的空间，从而

$$(\mathrm{Ker}A{)}^{\perp }=\mathrm{span}(v_1,v_2,\dots ,v_r)=W$$

因此 $BA$ 是 ${\mathbb{R}}^m$ 到 $(\mathrm{Ker}A{)}^{\perp }$ 上的正交投影算子

---

最小二乘法

最小二乘法

$$\underset{x\in {\mathbb{R}}^n}{\min }\Vert Ax-b{\Vert }^2$$

其中 $A$ 为 $m\times n$ 阶矩阵，$b\in {\mathbb{R}}^m$

方法1: 投影的视角 要最小化 $\Vert Ax-b{\Vert }^2$，也就是 $b$ 到 $\mathrm{Im}A$ 的距离要尽可能小，换言之就是计算 $b$ 到 $\mathrm{Im}A$ 的正交投影，这意味着 $b-Ax$ 必然与 $\mathrm{Im}A$ 中的所有向量垂直，也就是与 $A$ 的所有列向量垂直，于是我们得到

$$A^T(b-Ax)=0$$

即

$$A^{T}Ax=A^{T}b$$

case1: 此时若 $A^{T}A$ 可逆，那么 $x=(A^{T}A{)}^{-1}{A}^{T}b$

case2: 若 $A^{T}A$ 不可逆，此时我们可以借助广义逆矩阵来表示。设 $A^{T}A$的广义逆为 $(A^{T}A{)}^{+}$，因为 $A^{T}b\in \mathrm{Im}{A}^T=\mathrm{Im}(A^{T}A)$，因此 $A^{T}Ax=A^{T}b$ 有解，方便起见，记 $A^{T}A=M$，$c=A^{T}b$，原方程变为

$$Mx=c$$

现在令 $x=M^{+}c$，代入等式左边为 $M{M}^{+}c$，由上一题的结论，$M{M}^{+}$ 是到 $\mathrm{Im}M$ 的正交投影算子，而 $c$ 本来就在 $\mathrm{Im}M$ 里面，因此 $M{M}^{+}c=c$，这就说明 $x=M^{+}c$ 是原方程的一个特解，现在我们继续求原方程的通解，考虑

$$Mx=0$$

也就是求 $x\in \mathrm{Ker}M$，继续由上一题的结论，$M^{+}M$ 是到 $(\mathrm{Ker}M{)}^{\perp }$ 的正交投影算子，那么 $I-M^{+}M$ 就是到 $\mathrm{Ker}M$ 的正交投影算子，事实上，$\forall x\in V$，可以分解为

$$x=x_r+x_n$$

其中 $x_r\in (\mathrm{Ker}M{)}^{\perp }$，$x_n\in \mathrm{Ker}M$。因为 $M^{+}M$ 是到 $(\mathrm{Ker}M{)}^{\perp }$ 的正交投影算子，从而

$$M^{+}Mx=x_r$$

另一方面，考虑

$$(I-M^{+}M)x=x-M^{+}Mx=x_n$$

这就证明了 $I-M^{+}M$ 就是到 $\mathrm{Ker}M$ 的正交投影算子。因此原方程的所有解为

$$x=M^{+}c+(I-M^{+}M)z,z\in {\mathbb{R}}^n$$

现在代回 $M=A^{T}A,c=A^{T}b$，就有

$$\begin{array}{rl}x& =(A^{T}A{)}^{+}{A}^{T}b+(I-(A^{T}A{)}^{+}(A^{T}A))z\\ & \\ & =A^{+}b+(I-A^{+}A)z\end{array}$$

要推出最后一个等式需要重新将 $A$ 进行奇异值分解，然后代入计算

于是 $Ax=A{A}^{+}b+A(I-A^{+}A)z=A{A}^{+}b$，此时代入元函数就得到

$$\underset{x\in {\mathbb{R}}^n}{\min }\Vert Ax-b{\Vert }^2=\Vert b-A{A}^{+}b{\Vert }^2=b^T(I-A{A}^{+}{)}^T(I-A{A}^{+})b$$

如果不计算 $x$ 的具体表达式，只是计算最小值的话，也可以这样做: 由上一题结论，此时 $A{A}^{+}b$ 就是 $b$ 在 $\mathrm{Im}A$ 上的正交投影，所以

$$\underset{x\in {\mathbb{R}}^n}{\min }\Vert Ax-b{\Vert }^2=\Vert b-A{A}^{+}b{\Vert }^2=b^T(I-A{A}^{+}{)}^T(I-A{A}^{+})b$$

利用奇异值分解不难证明

$$(I-A{A}^{+}{)}^T(I-A{A}^{+})=I-A{A}^{+}$$

因此最终我们得到

$$\underset{x\in {\mathbb{R}}^n}{\min }\Vert Ax-b{\Vert }^2=b^T(I-A{A}^{+})b$$

方法2: 直接计算梯度 将范数展开，记作 $f(x)$， 得到

$$\begin{array}{rl}f(x)& =(Ax-b{)}^T(Ax-b)\\ & \\ & =x^T{A}^{T}Ax-x^T{A}^{T}b-b^{T}Ax+b^{T}b\\ & \\ & =x^T{A}^{T}Ax-2b^{T}Ax+b^{T}b\end{array}$$

计算 $f(x)$ 的梯度，使其为 $0$

$$\nabla f(x)=2A^{T}Ax-2A^{T}b=0$$

此时也能得到

$$A^{T}Ax=A^{T}b$$

因为 ${\nabla }^{2}f(x)=2A^{T}A$ 为半正定矩阵，于是此时的 $x$ 就是全局最小值点 剩下的流程就与方法1一样了