奇异值分解（SVD）

· 更新于

前置知识

见另一篇博客：谱定理的证明

奇异值分解（SVD）

奇异值分解（singular value decomposition, SVD），说的是任意矩阵 A∈Cm×n\boldsymbol{A} \in \mathbb{C}^{m\times n} ，都可以分解成以下形式

A=u1σ1v1∗+u2σ2v2∗+⋯+urσrvr∗=(u1…u2um)(diag(σ1,σ2,…,σr)000)(v1∗v2∗⋮vn∗)=UΣV∗\begin{align*} \boldsymbol{A}&=\boldsymbol{u}_1\sigma_1\boldsymbol{v}^* _1 + \boldsymbol{u}_2\sigma_2\boldsymbol{v}^* _2 + \dots + \boldsymbol{u}_r\sigma_r\boldsymbol{v}^*_r \\ &= \left(\begin{array}{cccc} \boldsymbol{u}_1 & \dots & \boldsymbol{u}_2 & \boldsymbol{u}_m \\ \end{array}\right) \left(\begin{array}{cc} \mathrm{diag}(\sigma_1, \sigma_2, \dots, \sigma_r) & 0\\ 0 & 0\\ \end{array}\right) \left(\begin{array}{c} \boldsymbol{v}_1^* \\ \boldsymbol{v}_2^* \\ \vdots \\ \boldsymbol{v}_n^* \end{array}\right)\\ &= \boldsymbol{U} \boldsymbol{\Sigma} \boldsymbol{V}^* \end{align*}

其中 rr 是矩阵 AA 的秩， u1,u2,…,um\boldsymbol{u} _1 , \boldsymbol{u} _2 , \dots , \boldsymbol{u} _m 为 AA∗\boldsymbol{A}\boldsymbol{A}^* 的特征向量， v1,v2,…vn\boldsymbol{v} _1, \boldsymbol{v} _2, \dots \boldsymbol{v} _n 为 A∗A\boldsymbol{A}^*\boldsymbol{A} 的特征向量

U\boldsymbol{U} 和 V\boldsymbol{V} 满足

U∗U=IV∗V=I\begin{align*} \boldsymbol{U}^*\boldsymbol{U}&=\boldsymbol{I}\\ \boldsymbol{V}^*\boldsymbol{V}&=\boldsymbol{I} \end{align*}

即 U\boldsymbol{U} 和 V\boldsymbol{V} 均为酉矩阵。

且 σ1≥σ2≥⋯≥σr>σr+1=σr+2=⋯=σn=0\sigma_1 \geq \sigma_2 \geq \cdots \geq \sigma_r > \sigma_{r+1} = \sigma_{r+2} = \cdots = \sigma_n = 0 。

图来自Github仓库The-Art-of-Linear-Algebra

奇异值分解表明了任意矩阵都可以拆分成rr个秩为11的矩阵之和。酉矩阵表明 u1\boldsymbol{u}_1 和 v1\boldsymbol{v}_1 的长度均为 11。则 σi\sigma_i 的大小描述了拆分成的这个矩阵的重要程度， σi\sigma_i 越大，说明 uiσivi∗\boldsymbol{u}_i\sigma_i\boldsymbol{v}_i^* 这一项越重要。这就揭示了奇异值分解在数据降维、图像压缩、统计分析（如：主成分分析）方面大有用处。

优势

相比于特征值分解，奇异值分解的优势多多。

  1. 对矩阵的要求少

    特征值分解要求 A\boldsymbol{A} 为方阵，且可对角化。而奇异值分解对 A\boldsymbol{A} 没有什么限制。

  2. 稳定性

    当 A\boldsymbol{A} 中一个值微小的改变时，特征值分解的 Λ\boldsymbol{\Lambda} 可能会发生比较大的改变。但是奇异值分解的 Σ\boldsymbol{\Sigma} 只会发生很小的改变。并且这些改变都发生在靠后的、 σi\sigma_i 更小的项里。

截取k项

由于 σi\sigma_i 的大小是从大到小排列，因此我们可以只取前面 kk 项，得到

u1σ1v1∗+u2σ2v2∗+⋯+ukσkvk∗=UkΣkVk∗\begin{align*} &\boldsymbol{u}_1\sigma_1\boldsymbol{v}^* _1 + \boldsymbol{u}_2\sigma_2\boldsymbol{v}^* _2 + \dots + \boldsymbol{u}_k\sigma_k\boldsymbol{v}^*_k \\ &=\boldsymbol{U}_k \boldsymbol{\Sigma}_k \boldsymbol{V}_k^* \end{align*}

其中 Uk\boldsymbol{U}_k 为 m ⁣× ⁣km\!\times\!k 矩阵，Σk\boldsymbol{\Sigma}_k 为 k ⁣× ⁣kk\!\times\!k 对角阵， V\boldsymbol{V} 为 n ⁣× ⁣kn\!\times\!k 矩阵。

当 k=rk=r 时，则

A=UkΣkVk∗\boldsymbol{A}=\boldsymbol{U}_k\boldsymbol{\Sigma}_k \boldsymbol{V}_k^*

仍然成立，此时相当于对A\boldsymbol{A}进行了无损压缩。

当 k<rk\lt r 时，σ1\sigma_1 最小的 r−kr-k 项被舍弃了，但是得到的新矩阵和原来的矩阵仍然是相近的，相当于一个有损压缩。

A≈UkΣkVk∗\boldsymbol{A}\approx\boldsymbol{U}_k\boldsymbol{\Sigma}_k \boldsymbol{V}_k^*

显然，新矩阵的秩为kk，此时相当于做了一个数据降维。

数据降维：从二维到一维

存在性证明

引理1：对称矩阵均为半正定矩阵（半正定矩阵：特征值均非负的矩阵）

先证明λ\lambda为实数

S∗=SSx=λx⇒x∗S=λ‾x∗x∗(Sx)=λ‾x∗x=λ‾∣x∣2(x∗S)x=λx∗x=λ∣x∣2(λ−λ‾)∣x∣2=0\begin{align*} \boldsymbol{S}^* &= \boldsymbol{S} \\ \boldsymbol{Sx} &= \lambda \boldsymbol{x}\\ \Rightarrow\\ \boldsymbol{x}^*\boldsymbol{S} &= \overline{\lambda}\boldsymbol{x}^* \\ \boldsymbol{x}^*(\boldsymbol{S}\boldsymbol{x}) &= \overline{\lambda}\boldsymbol{x}^*\boldsymbol{x}=\overline{\lambda}|\boldsymbol{x}|^2\\ (\boldsymbol{x}^*\boldsymbol{S})\boldsymbol{x}&=\lambda \boldsymbol{x}^* \boldsymbol{x} = \lambda|\boldsymbol{x}|^2\\ (\lambda - \overline{\lambda})|\boldsymbol{x}|^2 &= 0\\ \end{align*}

又因为特征向量 x\boldsymbol{x} 非零，得 λ=λ‾\lambda = \overline{\lambda}，即 λ\lambda 为实数

再证明 λ\lambda 非负

x∗A∗Ax=(λ‾x∗)(λx)∣Ax∣2=∣λ∣2∣x2∣∣λ∣2=∣Ax∣2∣x∣2≥0\begin{align*} \boldsymbol{x}^*\boldsymbol{A}^*\boldsymbol{Ax}&=(\overline{\lambda}\boldsymbol{x}^*)(\lambda \boldsymbol{x})\\|\boldsymbol{Ax}|^2&=|\lambda|^2|\boldsymbol{x}^2|\\|\lambda|^2&=\frac{|\boldsymbol{Ax}|^2}{|\boldsymbol{x}|^2}\geq 0 \end{align*}

引理2：rank(A∗A)=rank(AA∗)=r\mathrm{rank}(\boldsymbol{A}^*\boldsymbol{A})=\mathrm{rank}(\boldsymbol{AA}^*)=r

由 Ax=0⇒A∗Ax=0\boldsymbol{Ax}=0 \Rightarrow \boldsymbol{A}^*\boldsymbol{Ax}=0 得

N(A∗A)⊂N(A)\mathrm{N}(\boldsymbol{A} ^*\boldsymbol{A}) \subset \mathrm{N}(\boldsymbol{A})

若 A∗Ax=0\boldsymbol{A}^*\boldsymbol{Ax}=0，则

x∗A∗AX=(Ax)∗Ax=∣Ax∣2=0\boldsymbol{x}^*\boldsymbol{A}^*\boldsymbol{AX}=(\boldsymbol{Ax})^*\boldsymbol{Ax}=|\boldsymbol{Ax}|^2=0 Ax=0\boldsymbol{Ax}=0

所以

N(A)⊂N(A∗A)\mathrm{N}(\boldsymbol{A}) \subset \mathrm{N}(\boldsymbol{A}^*\boldsymbol{A})

有

N(A)=N(A∗A)dim⁡N(A)=dim⁡N(A∗A)n−rank(A)=n−rank(A∗A)rank(A)=rank(A∗A)\begin{align*}\mathrm{N}(\boldsymbol{A})&=\mathrm{N}(\boldsymbol{A}^*\boldsymbol{A})\\\dim\mathrm{N}(\boldsymbol{A})&=\dim\mathrm{N}(\boldsymbol{A}^*\boldsymbol{A})\\n-\mathrm{rank}(\boldsymbol{A})&=n-\mathrm{rank}(\boldsymbol{A}^*\boldsymbol{A})\\\mathrm{rank}(\boldsymbol{A})&=\mathrm{rank}(\boldsymbol{A}^*\boldsymbol{A}) \end{align*}

同理可证明rank(A∗)=rank(AA∗)\mathrm{rank}(\boldsymbol{A}^*)=\mathrm{rank}(\boldsymbol{AA}^*)，故原式成立

引理3：A∗A\boldsymbol{A}^*\boldsymbol{A} 和 AA∗\boldsymbol{AA}^* 均有 rr 个相同的正特征值。

首先证明均有 rr 个特征值：

由于 A∗A\boldsymbol{A}^*\boldsymbol{A} 为对称矩阵，由于对称矩阵一定是正规矩阵，由谱定理有

A∗A=UΛU∗\boldsymbol{A}^*\boldsymbol{A}=\boldsymbol{U\Lambda}\boldsymbol{U}^*

由引理1，特征值不可能为负。且 Λ\boldsymbol{\Lambda} 中非零元素个数其实就是 rank(Λ)\mathrm{rank}(\boldsymbol{\Lambda})

则正特征值个数 rank(Λ)=rank(A∗A)\mathrm{rank}(\boldsymbol{\Lambda})=\mathrm{rank}(\boldsymbol{A}^*\boldsymbol{A})

对 AA∗\boldsymbol{AA}^* 同理

再证明 A∗A\boldsymbol{A}^*\boldsymbol{A} 的正特征值也是 AA∗\boldsymbol{AA}^* 的正特征值：

A∗Ax=λxAA∗Ax=λAxAA∗(Ax)=λ(Ax)\begin{align*} \boldsymbol{A}^*\boldsymbol{Ax}&=\lambda\boldsymbol{x}\\ \boldsymbol{A}\boldsymbol{A}^*\boldsymbol{Ax}&=\lambda\boldsymbol{Ax}\\ \boldsymbol{A}\boldsymbol{A}^*(\boldsymbol{Ax})&=\lambda(\boldsymbol{Ax})\\ \end{align*}

由 λ≠0\lambda \neq 0 得 Ax≠0\boldsymbol{Ax}\neq 0，故 Ax\boldsymbol{Ax} 是 A∗A\boldsymbol{A}^*\boldsymbol{A} 的一个特征向量，对应的特征值为 λ\lambda。

反之可证 AA\boldsymbol{A}\boldsymbol{A} 的正特征值也是 A∗A\boldsymbol{A}^*\boldsymbol{A} 的特征值，则两矩阵拥有相同的一组正特征值。

由引理3，我们设这一组相同的特征值为 λi(i≤r)\lambda_i\quad(i \leq r) 并从大到小排列，λ1≥λ2≥⋯≥λr>λr+1=λr+2=⋯=λm=0\lambda_1 \geq \lambda_2 \geq \dots \geq \lambda_r > \lambda_{r+1} = \lambda_{r+2} = \dots = \lambda_m = 0。

证明是构造性的

对 A∗A\boldsymbol{A}^*\boldsymbol{A} 谱分解可以求出 V\boldsymbol{V} 和 λi\lambda_i，设 V\boldsymbol{V} 的第 ii 列为 vi\boldsymbol{v}_i，对应特征值 λi\lambda_i。

设 V=(VrV0)\boldsymbol{V}=\left(\begin{array}{cc}\boldsymbol{V}_r & \boldsymbol{V}_0\end{array}\right) ，前 rr 列为 Vr\boldsymbol{V}_r，剩下 m−rm-r 列为 V0\boldsymbol{V}_0。

U=(UrU0) \boldsymbol{U}=\left(\begin{array}{cc} \boldsymbol{U}_r & \boldsymbol{U}_0 \\ \end{array}\right)，前 rr 列为 Ur\boldsymbol{U}_r，剩下 n−rn-r 列为 U0\boldsymbol{U}_0。

当 i>ri>r 时，由 A∗Avi=0\boldsymbol{A}^*\boldsymbol{Av}_i=0 两边左乘以 vi∗\boldsymbol{v}_i^*，易得 Avi=0\boldsymbol{Av}_i=0，故有 AV0=0\boldsymbol{AV}_0 = 0。

等价变换原式

A=UΣV∗AV=UΣA(VrV0)=(UrU0)(Σr000)AVr=UrΣr\begin{align*} \boldsymbol{A} &= \boldsymbol{U\Sigma V}^*\\ \boldsymbol{AV} &= \boldsymbol{U \Sigma}\\ \boldsymbol{A}\left(\begin{array}{cc} \boldsymbol{V}_r\\ \boldsymbol{V}_0\\ \end{array}\right)&=\left(\begin{array}{cc} \boldsymbol{U}_r & \boldsymbol{U}_0\\ \end{array}\right) \left(\begin{array}{cc} \boldsymbol{\Sigma}_r & 0 \\ 0 & 0 \\ \end{array}\right) \tag{1}\\ \boldsymbol{AV}_r &= \boldsymbol{U}_r \boldsymbol{\Sigma}_r \tag{2}\\ \end{align*}

再令

σi=λiΣr=diag(σ1,σ2,…,σr)\begin{align*} \sigma_i &= \sqrt{\lambda_i}\\ \boldsymbol{\Sigma}_r &= \mathrm{diag}(\sigma_1, \sigma _2, \dots, \sigma_r)\\ \end{align*}

Vr\boldsymbol{V}_r、Σr\boldsymbol{\Sigma}_r 均已构造出来，则只需构造符合 (1)(1) 的 Ur\boldsymbol{U}_r，且 ui\boldsymbol{u}_i（i≤ri\leq r）满足以下条件：

  1. ui\boldsymbol{u}_i 为单位向量。
  2. ui⊥uj\boldsymbol{u}_i \perp \boldsymbol{u}_j（i≠ji \neq j）。
  3. ui\boldsymbol{u}_i 是 AA∗\boldsymbol{AA}^* 的特征向量。

令 ui=1σiAvi\boldsymbol{u}_i=\frac{1}{\sigma_i}\boldsymbol{Av}_i，下面证明其满足三个条件

1

ui∗ui=1σi2vi∗A∗Avi=1λivi∗λivi=1\begin{align*} \boldsymbol{u}_i^*\boldsymbol{u}_i &= \frac{1}{\sigma_i^2}\boldsymbol{v}_i^*\boldsymbol{A}^*\boldsymbol{Av}_i\\ &=\frac{1}{\lambda_i}\boldsymbol{v}_i^*\lambda_i \boldsymbol{v}_i\\ &=1\\ \end{align*}
2
ui∗uj=1σiσjvi∗A∗Avj=1σiσjvi∗vj\begin{align*} \boldsymbol{u}_i^*\boldsymbol{u}_j &= \frac{1}{\sigma_i\sigma_j}\boldsymbol{v}_i^*\boldsymbol{A}^*\boldsymbol{Av}_j\\ &=\frac{1}{\sigma_i\sigma_j}\boldsymbol{v}_i^*\boldsymbol{v}_j\\ \end{align*}

由 vi\boldsymbol{v}_i 和 vj\boldsymbol{v}_j 正交知上式等于 00，即 ui\boldsymbol{u}_i 和 uj\boldsymbol{u}_j 也正交。

3

AA∗ui=1σiAA∗Avi=σiAvi=λiui\begin{align*} \boldsymbol{AA}^*\boldsymbol{u}_i &= \frac{1}{\sigma_i}\boldsymbol{AA}^*\boldsymbol{A}\boldsymbol{v}_i\\ &= \sigma_i\boldsymbol{Av}_i\\ &=\lambda_i \boldsymbol{u}_i\\ \end{align*}

证毕。

与四个基本子空间的关系

  • Vr=(v1,v2,…,vn)\boldsymbol{V}_r=(\boldsymbol{v} _1, \boldsymbol{v} _2, \dots, \boldsymbol{v} _n)是A\boldsymbol{A}的行空间C(A∗)\mathrm{C}(\boldsymbol{A}^*)的一组标准正交基；
  • V0=(vr,vr+1,…,vn)\boldsymbol{V}_0=(\boldsymbol{v} _r, \boldsymbol{v} _{r+1}, \dots, \boldsymbol{v} _n)是A\boldsymbol{A}的零空间N(A)\mathrm{N}(\boldsymbol{A})的一组标准正交基；
  • Ur=(u1,u2,…,uu)\boldsymbol{U}_r=(\boldsymbol{u} _1, \boldsymbol{u} _2, \dots, \boldsymbol{u} _u)是A\boldsymbol{A}的列空间C(A)\mathrm{C}(\boldsymbol{A})的一组标准正交基；
  • U0=(ur,ur+1,…,un)\boldsymbol{U}_0=(\boldsymbol{u} _r, \boldsymbol{u} _{r+1}, \dots, \boldsymbol{u} _n)是A\boldsymbol{A}的左零空间N(A∗)\mathrm{N}(\boldsymbol{A}^*)的一组标准正交基。

线性代数中非常重要的子空间，和SVD就这样巧妙地联系在一起了，由 V∗V=I\boldsymbol{V}^*\boldsymbol{V} = \boldsymbol{I} 和 U∗U=I\boldsymbol{U}^*\boldsymbol{U} = \boldsymbol{I}，又能再次验证四个基本子空间的两组垂直关系：

C(A)⊥N(A∗)C(A∗)⊥N(A)\begin{align*} \mathrm{C}(\boldsymbol{A}) \perp \mathrm{N}(\boldsymbol{A}^*)\\ \mathrm{C}(\boldsymbol{A}^*) \perp \mathrm{N}(\boldsymbol{A})\\ \end{align*}

补充

为了结论的泛用性，上面的证明是在复数域 C\mathbb{C} 下进行的，当然换成实数域也是同理的，只要将 A∗\boldsymbol{A}^* 换成 AT\boldsymbol{A}^\mathrm{T} 即可。

参考

Introduction to Linear Algebra, 5th edition, by Gilbert Strang

https://inst.eecs.berkeley.edu/~ee127/sp21/livebook/thm_sed.html