svd

Prerequisites

• norm

设

$$A\in {\mathbb{C}}^{m\times n},p:=\min \{m,n\},r:=\mathrm{rank}(A).$$

记 $A^H$ 为共轭转置，$\mathcal{R}(A)$ 为像空间，$\mathcal{N}(A)$ 为核空间。对实矩阵，$A^H=A^T$，下文的酉矩阵相应退化为正交矩阵。

1. 奇异值分解

1.1. 完整 SVD

任意矩阵 $A\in {\mathbb{C}}^{m\times n}$ 都可以分解为

$$\boxed{A=U\Sigma V^H,}$$

其中

$$U=[u_1\cdots u_m]\in {\mathbb{C}}^{m\times m},V=[v_1\cdots v_n]\in {\mathbb{C}}^{n\times n}$$

都是酉矩阵，而 $\Sigma \in {\mathbb{R}}^{m\times n}$ 是矩形对角矩阵：

$$\Sigma =\left(\begin{array}{cc}{\Sigma }_r& 0\\ 0& 0\end{array}\right),{\Sigma }_r=\mathrm{diag}({\sigma }_1,\dots ,{\sigma }_r).$$

若 $r>0$，正奇异值满足

$${\sigma }_1\ge \cdots \ge {\sigma }_r>0.$$

若 $r<p$，则其余奇异值满足 ${\sigma }_{r+1}=\cdots ={\sigma }_p=0$。

${\sigma }_1,\dots ,{\sigma }_p$ 称为 $A$ 的奇异值；$u_i$ 与 $v_i$ 分别称为左奇异向量与右奇异向量。

对每个 $1\le i\le r$，

$$\boxed{A{v}_i={\sigma }_i{u}_i,}\boxed{A^H{u}_i={\sigma }_i{v}_i.}$$

其余奇异向量满足

$$A{v}_j=0(r<j\le n),A^H{u}_i=0(r<i\le m).$$

1.2. 紧 SVD

只保留非零奇异值及对应的奇异向量，记

$$U_r=[u_1\cdots u_r]\in {\mathbb{C}}^{m\times r},V_r=[v_1\cdots v_r]\in {\mathbb{C}}^{n\times r}.$$

则

$$\boxed{A=U_r{\Sigma }_r{V}_r^H.}$$

这里

$$U_r^H{U}_r=I_r,V_r^H{V}_r=I_r,$$

但当 $r<m$ 或 $r<n$ 时，$U_r$、$V_r$ 本身不是方阵。

紧 SVD 也可以写成秩一矩阵之和：

$$\boxed{A=\sum _{i=1}^r{\sigma }_i{u}_i{v}_i^H.}$$

1.3. 截断 SVD

对 $0\le k\le r$，只保留前 $k$ 个奇异值，得到

$$A_k:=U_k{\Sigma }_k{V}_k^H=\sum _{i=1}^k{\sigma }_i{u}_i{v}_i^H.$$

其中 $\mathrm{rank}(A_k)=k$，并且 $A_r=A$、$A_0=0$。

2. 预备结论

2.1. $A^{H}A$ 与 $A{A}^H$ 半正定

$A^{H}A\in {\mathbb{C}}^{n\times n}$ 与 $A{A}^H\in {\mathbb{C}}^{m\times m}$ 都是 Hermitian 半正定矩阵。

proof

首先，

$$(A^{H}A{)}^H=A^{H}A,(A{A}^H{)}^H=A{A}^H,$$

所以二者都是 Hermitian 矩阵。对任意 $x\in {\mathbb{C}}^n$、$y\in {\mathbb{C}}^m$，

$$x^H{A}^{H}Ax=\Vert Ax{\Vert }_2^2\ge 0,y^{H}A{A}^{H}y=\Vert A^{H}y{\Vert }_2^2\ge 0.$$

因此二者都是半正定矩阵。

所以它们的特征值均为非负实数，并且都可以酉对角化。

2.2. 核空间

有

$$\boxed{\mathcal{N}(A^{H}A)=\mathcal{N}(A),}\boxed{\mathcal{N}(A{A}^H)=\mathcal{N}(A^H).}$$

proof

以第一个等式为例，若 $Ax=0$，则显然 $A^{H}Ax=0$；反过来，若 $A^{H}Ax=0$，则

$$0=x^H{A}^{H}Ax=\Vert Ax{\Vert }_2^2,$$

所以 $Ax=0$。第二个等式同理。

由秩–零度定理可得

$$\mathrm{rank}(A^{H}A)=\mathrm{rank}(A)=\mathrm{rank}(A{A}^H)=r.$$

此外，

$$\boxed{\mathcal{R}(A{)}^{\perp }=\mathcal{N}(A^H),}\boxed{\mathcal{R}(A^H{)}^{\perp }=\mathcal{N}(A).}$$

proof

例如，$y\in \mathcal{R}(A{)}^{\perp }$ 当且仅当 $y^{H}Ax=0$ 对所有 $x\in {\mathbb{C}}^n$ 成立，也就是 $A^{H}y=0$。另一个等式同理。

2.3. 非零特征值

$A^{H}A$ 与 $A{A}^H$ 具有相同的非零特征值，并且重数相同。

proof

设 $\lambda >0$，分别记相应的特征空间为

$$E_{\lambda }(A^{H}A)\text{和}{E}_{\lambda }(A{A}^H).$$

映射

$$T:E_{\lambda }(A^{H}A)\to E_{\lambda }(A{A}^H),T(v)=Av$$

是同构，其逆映射为

$$T^{-1}(u)=\frac{1}{\lambda }{A}^{H}u.$$

事实上，若 $A^{H}Av=\lambda v$，则

$$A{A}^H(Av)=A(A^{H}Av)=\lambda Av,$$

并且 $Av\ne 0$，否则 $\lambda v=A^{H}Av=0$ 将推出 $v=0$。类似地，若 $A{A}^{H}u=\lambda u$，则

$$A^{H}A(A^{H}u)=A^H(A{A}^{H}u)=\lambda A^{H}u.$$

最后，

$$\frac{1}{\lambda }{A}^H(Av)=v,A\left(\frac{1}{\lambda }{A}^{H}u\right)=u.$$

因此两个特征空间同构。由于 $A^{H}A$ 与 $A{A}^H$ 都可对角化，非零特征值的几何重数等于代数重数，结论成立。

3. SVD 的存在性证明

proof

由谱定理，存在 ${\mathbb{C}}^n$ 的一组标准正交基 $v_1,\dots ,v_n$，使得

$$A^{H}A{v}_i=\{\begin{array}{ll}{\lambda }_i{v}_i,& 1\le i\le r,\\ 0,& r<i\le n,\end{array}$$

其中

$${\lambda }_1\ge \cdots \ge {\lambda }_r>0.$$

定义

$${\sigma }_i:=\sqrt{{\lambda }_i},u_i:=\frac{1}{{\sigma }_i}A{v}_i,1\le i\le r.$$

3.1. $u_1,\dots ,u_r$ 标准正交

对 $1\le i,j\le r$，

$$\begin{array}{rl}{u}_i^H{u}_j& =\frac{1}{{\sigma }_i{\sigma }_j}{v}_i^H{A}^{H}A{v}_j\\ & =\frac{{\sigma }_j^2}{{\sigma }_i{\sigma }_j}{v}_i^H{v}_j\\ & ={\delta }_{ij}.\end{array}$$

因此 $u_1,\dots ,u_r$ 标准正交。它们都属于 $\mathcal{R}(A)$，且数量恰好等于 $\dim \mathcal{R}(A)=r$，所以

$$\mathcal{R}(A)=\mathrm{span}\{u_1,\dots ,u_r\}.$$

3.2. 左右奇异向量的关系

根据定义，

$$A{v}_i={\sigma }_i{u}_i.$$

同时，

$$A^H{u}_i=\frac{1}{{\sigma }_i}{A}^{H}A{v}_i=\frac{{\lambda }_i}{{\sigma }_i}{v}_i={\sigma }_i{v}_i.$$

因而 $u_i$ 也是 $A{A}^H$ 对应于特征值 ${\sigma }_i^2$ 的特征向量：

$$A{A}^H{u}_i={\sigma }_i^2{u}_i.$$

3.3. 补全标准正交基

由

$$\mathcal{R}(A{)}^{\perp }=\mathcal{N}(A^H)$$

可选取 $\mathcal{N}(A^H)$ 的一组标准正交基 $u_{r+1},\dots ,u_m$。于是

$$U=[u_1\cdots u_m]$$

是酉矩阵。另一方面，第 2.2 节给出

$$\mathcal{N}(A)=\mathcal{N}(A^{H}A)=\mathrm{span}\{v_{r+1},\dots ,v_n\},$$

所以 $V=[v_1\cdots v_n]$ 也是酉矩阵。

对任意 $x\in {\mathbb{C}}^n$，

$$x=\sum _{i=1}^n(v_i^{H}x)v_i,$$

并且 $A{v}_i=0$ 对 $i>r$ 成立。因此

$$Ax=\sum _{i=1}^r{\sigma }_i(v_i^{H}x)u_i=U\Sigma V^{H}x.$$

这对一切 $x$ 都成立，故

$$\boxed{A=U\Sigma V^H.}$$

当 $A=0$ 时，取 $\Sigma =0$，并任取两个相应尺寸的酉矩阵 $U,V$ 即可。

Q.E.D.

4. 四个基本子空间

SVD 给出了四个基本子空间的标准正交基：

$$\boxed{\begin{array}{rl}\mathcal{R}(A)& =\mathrm{span}\{u_1,\dots ,u_r\},\\ \mathcal{N}(A^H)& =\mathrm{span}\{u_{r+1},\dots ,u_m\},\\ \mathcal{R}(A^H)& =\mathrm{span}\{v_1,\dots ,v_r\},\\ \mathcal{N}(A)& =\mathrm{span}\{v_{r+1},\dots ,v_n\}.\end{array}}$$

因此

$${\mathbb{C}}^m=\mathcal{R}(A){\oplus }^{\perp }\mathcal{N}(A^H),{\mathbb{C}}^n=\mathcal{R}(A^H){\oplus }^{\perp }\mathcal{N}(A).$$

对应的正交投影分别为

$$U_r{U}_r^H=P_{\mathcal{R}(A)},V_r{V}_r^H=P_{\mathcal{R}(A^H)}.$$

若

$$x=\sum _{i=1}^n{\alpha }_i{v}_i,$$

则

$$Ax=\sum _{i=1}^r{\sigma }_i{\alpha }_i{u}_i.$$

也就是说，$\mathcal{N}(A)$ 中的分量被映为零，而 $\mathcal{R}(A^H)$ 中沿 $v_i$ 的分量被缩放 ${\sigma }_i$ 倍并映到 $u_i$ 方向。

5. 谱分解与基本性质

由 $A=U\Sigma V^H$ 可得

$$\boxed{A^{H}A=V{\Sigma }^H\Sigma V^H,}\boxed{A{A}^H=U\Sigma {\Sigma }^H{U}^H.}$$

其中

$${\Sigma }^H\Sigma =\mathrm{diag}({\sigma }_1^2,\dots ,{\sigma }_r^2,0,\dots ,0)\in {\mathbb{R}}^{n\times n},$$ $$\Sigma {\Sigma }^H=\mathrm{diag}({\sigma }_1^2,\dots ,{\sigma }_r^2,0,\dots ,0)\in {\mathbb{R}}^{m\times m}.$$

因此：

• ${\sigma }_i^2$ 是 $A^{H}A$ 与 $A{A}^H$ 的非零特征值；
• $\mathrm{rank}(A)$ 等于正奇异值的个数；
• 若 $A$ 是方阵，则

$$|\det A|=\prod _{i=1}^n{\sigma }_i.$$

6. 范数与条件数

6.1. 谱范数

$$\boxed{\Vert A{\Vert }_2={\sigma }_1}$$

proof

对任意 $x\in {\mathbb{C}}^n$，写成

$$x=\sum _{i=1}^n{\alpha }_i{v}_i.$$

则

$$\Vert Ax{\Vert }_2^2=\sum _{i=1}^r{\sigma }_i^2|{\alpha }_i{|}^2\le {\sigma }_1^2\sum _{i=1}^n|{\alpha }_i{|}^2={\sigma }_1^2\Vert x{\Vert }_2^2.$$

当 $x=v_1$ 时取等号；当 $A=0$ 时两边均为零。

6.2. Frobenius 范数

$$\boxed{\Vert A{\Vert }_F={\left(\sum _{i=1}^r{\sigma }_i^2\right)}^{1/2}.}$$

proof

$$\begin{array}{rl}\Vert A{\Vert }_F^2& =\mathrm{tr}(A^{H}A)\\ & =\mathrm{tr}({\Sigma }^H\Sigma )\\ & =\sum _{i=1}^r{\sigma }_i^2.\end{array}$$

6.3. 酉不变性

若 $Q\in {\mathbb{C}}^{m\times m}$、$W\in {\mathbb{C}}^{n\times n}$ 都是酉矩阵，则

$$\boxed{\Vert QAW{\Vert }_2=\Vert A{\Vert }_2,\Vert QAW{\Vert }_F=\Vert A{\Vert }_F.}$$

proof

由

$$QAW=(QU)\Sigma (W^{H}V{)}^H$$

可知右侧也是一个 SVD，所以 $QAW$ 与 $A$ 具有相同的奇异值。再由前两节的结论即得所证。

6.4. 2-范数条件数

当 $r=p$ 时，定义

$$\boxed{{\kappa }_2(A)=\frac{{\sigma }_1}{{\sigma }_p}.}$$

若 $r<p$，则存在零奇异值，约定

$${\kappa }_2(A)=+\infty .$$

特别地，对可逆方阵 $A\in {\mathbb{C}}^{n\times n}$，

$${\kappa }_2(A)=\Vert A{\Vert }_2\Vert A^{-1}{\Vert }_2=\frac{{\sigma }_1}{{\sigma }_n}.$$

7. 唯一性与非唯一性

设 $A^{H}A$ 的特征值按降序排列。对 $1\le i\le p$，奇异值由下式唯一确定：

$${\sigma }_i=\sqrt{{\lambda }_i(A^{H}A)},$$

所以按降序排列后的奇异值及其重数是唯一的，但奇异向量一般不唯一。

• 若正奇异值 ${\sigma }_i$ 是单重的，则对应的 $u_i,v_i$ 在共同乘以一个模为 $1$ 的标量后仍表示同一项；实数情形下，这就是同时改变二者的符号。
• 若某个正奇异值重复出现，可以在对应的左右奇异子空间内同时施加任意酉基变换。
• 与零奇异值对应的向量只需分别构成 $\mathcal{N}(A^H)$ 与 $\mathcal{N}(A)$ 的标准正交基，因此通常也不唯一。

所以，唯一的是奇异值和相应的奇异子空间，而不是某一组具体的 $U$ 与 $V$。

8. 总结

• 任意复矩阵都存在完整 SVD $A=U\Sigma V^H$；
• 正奇异值是 $A^{H}A$（或 $A{A}^H$）正特征值的平方根；
• 紧 SVD 为 $A=U_r{\Sigma }_r{V}_r^H={\sum }_{i=1}^r{\sigma }_i{u}_i{v}_i^H$；
• 左右奇异向量分别给出四个基本子空间的标准正交基；
• $\Vert A{\Vert }_2={\sigma }_1$，$\Vert A{\Vert }_F^2={\sum }_i{\sigma }_i^2$；
• 奇异值唯一，奇异向量在相位、重根子空间及零空间中不唯一。