Schur分解、特征值分解、奇异值分解是三种联系十分紧密的矩阵分解，它们的关系是$Schur\rightarrow{}EVD\rightarrow{}SVD$Schur→EVD→SVD，也就是说由Schur分解可以推导出EVD，再推导出SVD。

本篇博客讨论特征值分解和奇异值分解的相关内容。上篇博客（链接）讨论的是Schur分解以及利用Schur分解能够解决的若干问题，其中包括大名鼎鼎的Hamilton-Cayley定理。

本文内容以线性代数知识为基础（主要是特征值和相似的知识）：
矩阵论（零）：线性代数基础知识整理（1）——逆矩阵、初等变换、满秩分解
矩阵论（零）：线性代数基础知识整理（2）——矩阵的秩与向量组的秩
矩阵论（零）：线性代数基础知识整理（3）——矩阵的秩与向量组的秩
矩阵论（零）：线性代数基础知识整理（4）——线性空间与线性变换
矩阵论（零）：线性代数基础知识整理（5）——特征值与相似

• 特征值分解EVD
  • 正规矩阵与EVD
  • EVD得到矩阵的特征值和特征向量
  • EVD的构造方法
  • EVD用于求矩阵的逼近
  • 实正规矩阵的正交相似拟对角化（拓展内容）
• 奇异值分解SVD
  • SVD的存在性定理
  • SVD的构造方法（简介）
  • SVD的性质
  • SVD用于求矩阵的逼近
  • SVD在推荐系统中的应用

---

特征值分解EVD（正规矩阵）

与Schur分解不同的是，特征值分解（又叫谱分解）要求将方阵酋对角化，这比schur分解的要求更高（Schur分解只是酋相似上三角化）。实际上，只有一类特殊的方阵才能进行特征值分解，这类特殊的方阵是正规矩阵。下面介绍特征值分解EVD。

• 定义（谱分解）：设有n阶方阵A。若存在n阶酋矩阵U和对角矩阵$\Sigma$Σ使得$A=U\Sigma{U^H}$A=UΣUH，则称$A=U\Sigma{U^H}$A=UΣUH是A的一个谱分解

• 定义（正规矩阵）：若n阶方阵A满足$A^HA=AA^H$AHA=AAH，则称A是正规矩阵
  （容易验证Hermite矩阵（共轭对称矩阵）、实对称矩阵、酋矩阵等都是正规矩阵）

• 引理4：任意一个上三角矩阵S，若S是正规矩阵，则S必然是对角矩阵
  证明：（对S的阶数n进行归纳）
  当n=1时，S本身就是对角矩阵。假定结论对n-1成立，现证明结论对n也成立。设$S=\begin{bmatrix}S_1&b\\0^H&a\end{bmatrix}$S=[S1​0H​ba​]，其中a是一个标量，$S_1$S1​是一个n-1阶上三角阵。计算可得$S^HS=\begin{bmatrix}S_1^HS_1&S_1^Hb\\b^HS_1&b^Hb+\bar{a}a\end{bmatrix}$SHS=[S1H​S1​bHS1​​S1H​bbHb+aˉa​]，$SS^H=\begin{bmatrix}S_1S_1^H+bb^H&\bar{a}b\\ab^H&a\bar{a}\end{bmatrix}$SSH=[S1​S1H​+bbHabH​aˉbaaˉ​]，由$S^HS=SS^H$SHS=SSH得$b^Hb+\bar{a}a=a\bar{a}$bHb+aˉa=aaˉ，故$b^Hb=||b||^2=0$bHb=∣∣b∣∣2=0，故$b=0$b=0，故$S_1S_1^H+bb^H=S_1S_1^H=S_1^HS_1$S1​S1H​+bbH=S1​S1H​=S1H​S1​，即$S_1$S1​是正规矩阵，由归纳假设知$S_1$S1​是对角矩阵。则$S=\begin{bmatrix}S_1&0\\0^H&a\end{bmatrix}$S=[S1​0H​0a​]是对角矩阵，得证。

• 定理12：n阶方阵A酋相似于一个对角矩阵的充要条件为A是正规矩阵
  证明：
  必要性：若A酋相似于一个对角矩阵，即存在酋矩阵U和对角矩阵$\Sigma$Σ使得$A=U\Sigma{U^H}$A=UΣUH，则$A^HA=U\overline{\Sigma}U^HU\Sigma{U^H}=U\overline{\Sigma}\Sigma{U^H}$AHA=UΣUHUΣUH=UΣΣUH，$AA^H=U\Sigma{U^H}U\overline{\Sigma}U^H=U\Sigma{}\overline{\Sigma}U^H$AAH=UΣUHUΣUH=UΣΣUH，注意到$\overline{\Sigma}\Sigma=\Sigma\overline{\Sigma}$ΣΣ=ΣΣ，故$A^HA=AA^H$AHA=AAH。
  充分性：设A的Schur分解为$A=PTP^H$A=PTPH，其中P是酋矩阵，T是上三角矩阵。由A是正规矩阵，将A代入$A^HA=AA^H$AHA=AAH得$PT^HTP^H=PTT^HP^H$PTHTPH=PTTHPH，故$T^HT=TT^H$THT=TTH，即上三角矩阵T是正规矩阵。于是由引理4知T是对角矩阵，故A酋相似于对角矩阵T。证毕。

EVD得到矩阵的特征值和特征向量

定理12说明仅正规矩阵可进行谱分解。在探讨谱分解有何用处之前，我们先认识一下谱分解究竟是怎样的，看看分解出来的对角矩阵是什么，以及那个酋矩阵到底是什么：

• 定理13：设正规矩阵A的谱分解为$A=U\Sigma U^H$A=UΣUH，则$\lambda$λ是A的特征值的充要条件为$\lambda$λ在$\Sigma$Σ的主对角线上，且A的每个特征值的代数重数等于其在$\Sigma$Σ的主对角线上出现的次数
• 定理14：设n阶正规矩阵A的谱分解为$A=U\Sigma U^H$A=UΣUH，且$\Sigma=diag(\lambda_1,...,\lambda_n)$Σ=diag(λ1​,...,λn​)，$U=\begin{bmatrix}u_1&\cdots&u_n\end{bmatrix}$U=[u1​​⋯​un​​]，则$u_i$ui​是A对应于特征值$\lambda_i$λi​的特征向量，且$u_1,...,u_n$u1​,...,un​是$C^n$Cn的标准正交基
  证明：由$A=U\Sigma U^H$A=UΣUH得$AU=U\Sigma$AU=UΣ，故$Au_i=\lambda_iu_i,i=1,...,n$Aui​=λi​ui​,i=1,...,n，即$u_i$ui​是A对应于特征值$\lambda_i$λi​的特征向量。因为U是酋矩阵，所以$u_1,...,u_n$u1​,...,un​是$C^n$Cn的标准正交基。
  【推论】n阶正规矩阵A有n个相互正交的特征向量
  【推论】n阶正规矩阵A的任意特征值的几何重数与代数重数相等

上面两个定理的结论解释了“特征值分解”这个名称的来源，之所以称之为特征值分解，是因为其既分解出了特征值，还分解出了对应的特征向量。特征值分解还表明，正规矩阵的特征值和特征向量包含了原矩阵的“全部信息”，因此我们可以通过一定的方法利用特征值和特征向量重构出原矩阵。

EVD的构造方法

实际上，我们已经知道U的列向量组是A的单位正交特征向量组，那么怎么求出A的n个单位正交的特征向量呢？我们容易保证属于同一特征值的特征向量间的正交性（只要求出该特征值对应的特征子空间的标准正交基即可），但是，如何保证不同特征值的特征向量间的正交性呢？实际上，正规矩阵本身的性质就保证了这一点。下面我们就来看看正规矩阵的性质：

• 定理15：设A是正规矩阵，则$A$A和$A^H$AH的特征值互为共轭，且$A$A对应于$\lambda$λ的特征子空间$V_\lambda$Vλ​与$A^H$AH对应于$\bar{\lambda}$λˉ的特征子空间$V_{\bar{\lambda}}$Vλˉ​相同，即$V_\lambda=V_{\bar{\lambda}}$Vλ​=Vλˉ​
  证明：
  将A谱分解得$A=U\Sigma U^H$A=UΣUH，则$A^H=U\overline{\Sigma}U^H$AH=UΣUH。因为$\Sigma$Σ和$\overline{\Sigma}$Σ主对角线上对应的元素互为共轭，所以A和$A^H$AH的特征值互为共轭。又$AU=U\Sigma$AU=UΣ，$A^HU=U\overline \Sigma$AHU=UΣ，且U的列向量组是正交向量组，所以$A$A的特征子空间$V_\lambda$Vλ​和$A^H$AH的特征子空间$V_{\bar{\lambda}}$Vλˉ​有同一组正交基，故$V_\lambda=V_{\bar{\lambda}}$Vλ​=Vλˉ​。
• 定理16：设A是正规矩阵，则A对应于不同特征值的特征向量是正交的
  证明：
  设$\lambda$λ和$\mu$μ是A的两个不同特征值，$x$x和$y$y分别是A的对应于$\lambda$λ和$\mu$μ的特征向量，即$\lambda \neq \mu,Ax=\lambda x,Ay=\mu y,x\neq 0,y\neq 0$λ​=μ,Ax=λx,Ay=μy,x​=0,y​=0。由定理15知$\bar \mu$μˉ​是$A^H$AH的特征值，且由$y\in{V_\mu},V_\mu=V_{\bar \mu}$y∈Vμ​,Vμ​=Vμˉ​​知$y\in{V_{\bar \mu}}$y∈Vμˉ​​，故$A^Hy=\bar \mu y$AHy=μˉ​y。$\bar \mu x^Hy=x^H(\bar \mu y )=x^HA^Hy=(Ax)^Hy=\bar \lambda x^Hy$μˉ​xHy=xH(μˉ​y)=xHAHy=(Ax)Hy=λˉxHy故$(\bar \mu-\bar \lambda)x^Hy=0$(μˉ​−λˉ)xHy=0，由$\lambda \neq \mu$λ​=μ知$x^Hy=0$xHy=0，即$x$x和$y$y是正交的，得证。

上面的定理说明只要求出A的每个特征值的特征子空间的标准正交基，那么所有的这些基向量一定两两正交。于是，我们有如下方法来求正规矩阵的特征值分解：


注意，之所以我们构造出的矩阵U是酋矩阵，是因为U的列向量组是单位正交的（其中对应于同一特征值的特征向量两两正交，对应于不同特征值的特征向量也两两正交）。而这样的$U$U一定可以保证构造出了$A$A的一个谱分解：
因为$U^HAU=\begin{bmatrix}u^H_{11}\\...\\u^H_{s_{r_s}}\end{bmatrix}\begin{bmatrix}Au_{11}&...&Au_{s_{r_s}}\end{bmatrix}\\=\begin{bmatrix}u^H_{11}\\...\\u^H_{s_{r_s}}\end{bmatrix}\begin{bmatrix}\lambda_1u_{11}&...&\lambda_su_{s_{r_s}}\end{bmatrix}=\begin{bmatrix}\lambda_1I_{r_1}&&\\&\ddots&\\&&\lambda_sI_{r_s}\end{bmatrix}$UHAU=⎣⎡​u11H​...usrs​​H​​⎦⎤​[Au11​​...​Ausrs​​​​]=⎣⎡​u11H​...usrs​​H​​⎦⎤​[λ1​u11​​...​λs​usrs​​​​]=⎣⎡​λ1​Ir1​​​⋱​λs​Irs​​​⎦⎤​所以$A=U\Lambda U^H$A=UΛUH是A的谱分解。

EVD的其他结论

谱分解还能得到其他一些有用的结论，如：

• 定理17：设n阶正规矩阵A的谱分解为$A=U\Sigma U^H$A=UΣUH，则$r(A)=r(\Sigma)$r(A)=r(Σ)，即A的秩等于A的非零特征值的个数（如果重特征值按重数算的话），零特征值的代数重数为$n-r(A)$n−r(A)
• 定理18：共轭对称矩阵A的特征值都是实数
  证：
  因A是共轭对称矩阵，故A是正规矩阵。考虑A的谱分解$A=U\Sigma U^H$A=UΣUH，因为$A^H=A$AH=A，即$U\overline{\Sigma}U^H=U\Sigma U^H$UΣUH=UΣUH，所以$\overline{\Sigma}=\Sigma$Σ=Σ，则对角矩阵$\Sigma$Σ的对角元都是实数，即A的特征值都是实数。

此外，类似于schur分解，谱分解也可以加快矩阵的幂运算，且效果要更好。谱分解（酋相似对角化）是相似对角化的一个特殊情形，在相似对角化中有一个计算幂的经典例子：求斐波那契数列的通项，谱分解也能用在与之类似的情形。感兴趣的读者请参考矩阵论（零）：线性代数基础知识整理（5）——特征值与相似。

机器学习应用中，常常遇到实矩阵而非复矩阵的问题。为避免复数运算，提高效率，需尽可能熟悉实矩阵中的相关结论：

• 定理19：设$A\in R^{n\times n}$A∈Rn×n，则$A$A存在谱分解$A=U\Sigma U^T$A=UΣUT（其中$U$U是实正交矩阵，$\Sigma$Σ是实对角矩阵）的充要条件为$A$A是实对称矩阵
  证明：
  充分性：实对称矩阵都是共轭对称矩阵，故A的特征值都是实数。考虑特征方程$(\lambda I-A)x=0$(λI−A)x=0，由于$\lambda$λ是实数，$A$A是实矩阵，故$\lambda I-A$λI−A是实矩阵。取$N(\lambda I-A)$N(λI−A)的一组实向量基，根据前述谱分解的构造方法，可以构造出$A$A的一个谱分解$A=U\Sigma U^T$A=UΣUT，其中$U$U是实正交矩阵，$\Sigma$Σ是实对角矩阵。
  必要性：设$A$A存在谱分解$A=U\Sigma U^T$A=UΣUT，其中$U$U是实正交矩阵，$\Sigma$Σ是实对角矩阵，则有$A^T=(U\Sigma U^T)^T=U\Sigma U^T=A$AT=(UΣUT)T=UΣUT=A。
  【注】该定理的一个等价表述为：任意实对称矩阵必可正交相似对角化。

EVD用于求矩阵的逼近

谱分解在机器学习中有重要的应用，一个典型的例子就是主成分分析（PCA）。主成分分析能够将高维数据“压缩”成低维数据，在去噪的同时还能保留原数据的大部分主要特征。PCA算法会在后面的博客中详细说，这里我们大致了解一下如何求得正规矩阵的近似矩阵，以达到去噪的效果：
设n阶正规矩阵A的特征值分解为$A=U\Sigma U^H$A=UΣUH，且$\Sigma=diag(\lambda_1,...,\lambda_n)$Σ=diag(λ1​,...,λn​)，$U=\begin{bmatrix}u_1&\cdots&u_n\end{bmatrix}$U=[u1​​⋯​un​​]。则$\begin{aligned}A&=\begin{bmatrix}u_1&\cdots&u_n\end{bmatrix}diag(\lambda_1,...,\lambda_n)\begin{bmatrix}u_1^H\\\cdots\\u_n^H\end{bmatrix}\\&=\begin{bmatrix}\lambda_1u_1&\cdots&\lambda_nu_n\end{bmatrix}\begin{bmatrix}u_1^H\\\cdots\\u_n^H\end{bmatrix}\\&=\Sigma_{i=1}^n\lambda_iu_iu_i^H\end{aligned}$A​=[u1​​⋯​un​​]diag(λ1​,...,λn​)⎣⎡​u1H​⋯unH​​⎦⎤​=[λ1​u1​​⋯​λn​un​​]⎣⎡​u1H​⋯unH​​⎦⎤​=Σi=1n​λi​ui​uiH​​于是我们可以将原矩阵A看成是它的不同特征的加权和。这样我们就可以对A的特征值按照模的大小排序，去掉模较小（注意特征值是复数，在PCA中我们会对一个实对称矩阵进行谱分解，此时特征值都是实数，直接比较大小就行）的特征值$\lambda$λ对应的项$\lambda uu^H$λuuH，也就是去掉权重较小的项，就得到了A的一个近似矩阵。（显然，去掉模越接近0的特征值的对应项，得到的矩阵与原矩阵的近似程度越高）
不过，由于特征值分解的适用性有限，我们无法对任何矩阵都使用特征值分解的方法来求近似矩阵。但是，后面要说的奇异值分解是适用于任意矩阵的，而奇异值分解出的奇异值和奇异向量就类似于特征值和特征向量的作用，故奇异值分解可以用来“分解任意矩阵的特征”。在求任意矩阵的近似矩阵时，可以使用SVD的方法。

实正规矩阵的正交相似拟对角化（拓展内容）

我们在复数域下证明了正规矩阵必可酋对角化的结论，并且讨论了实矩阵可正交相似对角化的充要条件（即必须是实对称矩阵）。根据正规矩阵的定义可得，实正规矩阵就是满足$A^TA=AA^T$ATA=AAT的矩阵$A$A。显然，实对称矩阵一定是实正规矩阵，但实正规矩阵不一定是实对称阵（例如$A=\begin{bmatrix}1&1\\-1&1\end{bmatrix}$A=[1−1​11​]），所以并非所有实正规矩阵都可以正交相似对角化。但是，我们可以将它们“近似”对角化，即正交相似拟对角化。
拟对角阵具有如下形式：$\begin{bmatrix}R_{11}&&\\&\ddots&\\&&R_{nn}\end{bmatrix}$⎣⎡​R11​​⋱​Rnn​​⎦⎤​其中对角子块$R_{ii}$Rii​是$1\times1$1×1矩阵或具有一对共轭特征值的$2\times 2$2×2正规矩阵。（注意，为表述方便，这里的拟对角阵是狭义的）

• 引理5：任意实的拟上三角阵$T$T，若$T$T是正规矩阵，则$T$T一定是拟对角阵
  证：（对$T$T对角线上的子块个数n进行归纳）
  当$n=1$n=1时，$T$T本身就是拟对角阵。假设命题对$n-1$n−1成立，现证明命题对$n$n也成立。设$T=\begin{bmatrix}T_1&S\\O&R\end{bmatrix}$T=[T1​O​SR​]，其中$R$R是$1\times1$1×1矩阵或$2\times 2$2×2矩阵。$T^TT=\begin{bmatrix}T_1^T&O\\S^T&R^T\end{bmatrix}\begin{bmatrix}T_1&S\\O&R\end{bmatrix}=\begin{bmatrix}T_1^TT_1&T_1^TS\\S^TT_1&S^TS+R^TR\end{bmatrix}$TTT=[T1T​ST​ORT​][T1​O​SR​]=[T1T​T1​STT1​​T1T​SSTS+RTR​]$TT^T=\begin{bmatrix}T_1&S\\O&R\end{bmatrix}\begin{bmatrix}T_1^T&O\\S^T&R^T\end{bmatrix}=\begin{bmatrix}T_1T_1^T+SS^T&SR^T\\RS^T&RR^T\end{bmatrix}$TTT=[T1​O​SR​][T1T​ST​ORT​]=[T1​T1T​+SSTRST​SRTRRT​]由$T^TT=TT^T$TTT=TTT得$S^TS+R^TR=RR^T$STS+RTR=RRT，进而$tr(RR^T)=tr(S^TS)+tr(R^TR)=tr(S^TS)+tr(RR^T)$tr(RRT)=tr(STS)+tr(RTR)=tr(STS)+tr(RRT)，故$tr(S^TS)=0$tr(STS)=0，$S=O$S=O，$T_1^TT_1=T_1T_1^T$T1T​T1​=T1​T1T​。于是$T=\begin{bmatrix}T_1&O\\O&R\end{bmatrix}$T=[T1​O​OR​]，注意到$T_1$T1​是有$n-1$n−1个对角子块的拟上三角阵，故由归纳假设知$T_1$T1​是拟对角阵，进而$T$T也是拟对角阵。证毕。
• 定理20：$A\in R^{n\times n}$A∈Rn×n正交相似于一个拟对角矩阵的充要条件为A是正规矩阵
  证明：
  必要性：若A正交相似于一个拟对角矩阵，即存在正交矩阵U和拟对角矩阵$T$T使得$A=UTU^T$A=UTUT，则$A^TA=UT^TU^TUTU^T=UT^TTU^T$ATA=UTTUTUTUT=UTTTUT，$AA^T=UTU^TUT^TU^T=UTT^TU^T$AAT=UTUTUTTUT=UTTTUT，注意到$T$T的对角子块都是正规矩阵，故$T^TT=TT^T$TTT=TTT，故$A^TA=AA^T$ATA=AAT。
  充分性：设A的Schur分解为$A=PTP^T$A=PTPT，其中P是正交矩阵，T是拟上三角矩阵。由A是正规矩阵，将A代入$A^TA=AA^T$ATA=AAT得$PT^TTP^T=PTT^TP^T$PTTTPT=PTTTPT，故$T^TT=TT^T$TTT=TTT，即拟上三角矩阵T是正规矩阵。于是由引理5知T是拟对角矩阵，故A正交相似于拟对角矩阵T。证毕。

---

奇异值分解SVD（任意矩阵）

奇异值分解在机器学习领域的应用实在是太广泛了：数据压缩、推荐系统、自然语言处理等等到处都有它的身影。这里介绍奇异值分解的数学推导，建议数学推导之外多了解一些应用和直观的几何解释。推荐学习奇异值的几何意义以及奇异值分解与特征值分解的区别与联系，以上知乎链接中的回答多是从线性变换的角度来讲解奇异值分解（实际上矩阵的几何意义就是线性变换），这样能够较为直观得理解EVD和SVD。照片压缩直观地给出了奇异值分解在照片压缩上呈现的效果。

• 定义：设$A\in{C^{m\times{n}}_r}$A∈Crm×n​，$A^HA$AHA的特征值为$\lambda_1\geqslant \lambda_2\geqslant ...\geqslant\lambda_r\gt\lambda_{r+1}= ...=\lambda_n=0$λ1​⩾λ2​⩾...⩾λr​>λr+1​=...=λn​=0称$\sigma_i=\sqrt \lambda_i(i=1,2,...,n)为A的奇异值$σi​=λ​i​(i=1,2,...,n)为A的奇异值
  【注1】关于$A^HA$AHA的特征值为什么都是非负实数的问题请参考矩阵论（零）：线性代数基础知识整理（5）——特征值与相似），注意奇异值都是非负的
  【注2】因为$r(A^HA)=r(A)=r$r(AHA)=r(A)=r，且$A^HA$AHA是一个n阶正规矩阵，故$A^HA$AHA的零特征值的代数重数是$n-r$n−r，这就是为什么$\lambda_{r+1}=...=\lambda_n=0$λr+1​=...=λn​=0
  【注3】网上看到有的人把$A^HA$AHA和$AA^H$AAH的特征值完全等同起来，这是不对的（它们差就差在零特征值上）。对奇异值的定义就是采用$A^HA$AHA的特征值来定义，用$AA^H$AAH来定义是不准确的。（不过这不会影响奇异值分解的结果）

奇异值的相关性质：

1. 奇异值的酋不变性（旋转不变性）：

• 定理21：设U是酋矩阵，则$UA$UA的奇异值与$A$A的奇异值相同
  证明：$(UA)^H(UA)=A^HU^HUA=A^HA$(UA)H(UA)=AHUHUA=AHA，故由奇异值的定义得$UA$UA的奇异值与$A$A的奇异值相同。
• 定理22：设U是酋矩阵，则$AU$AU的奇异值与$A$A的奇异值相同
  证明：$(AU)^H(AU)=U^H(A^HA)U$(AU)H(AU)=UH(AHA)U，即$(AU)^H(AU)$(AU)H(AU)酋相似于$A^HA$AHA，故它们的特征值相同，由奇异值的定义得$AU$AU的奇异值与$A$A的奇异值相同。

2. 逆矩阵的奇异值：

• 定理23：设$A\in C^{n\times n}_n$A∈Cnn×n​，则$A$A的奇异值均非零。设$A$A的奇异值为$\sigma_1\geqslant \sigma_2\geqslant\cdots\geqslant\sigma_n\gt 0$σ1​⩾σ2​⩾⋯⩾σn​>0，则$A^{-1}$A−1的奇异值为$1/\sigma_n\geqslant1/\sigma_{n-1}\geqslant\cdots\geqslant1/\sigma_1$1/σn​⩾1/σn−1​⩾⋯⩾1/σ1​
  证明：
  由奇异值定义的注释2知$A$A的奇异值均为正。设$AA^H$AAH的一个谱分解为$AA^H=U\Sigma U^H$AAH=UΣUH，其中$\Sigma=diag(\lambda_1,\lambda_2,\cdots,\lambda_n),\lambda_1\geqslant\lambda_2\geqslant\cdots\geqslant\lambda_n\gt 0$Σ=diag(λ1​,λ2​,⋯,λn​),λ1​⩾λ2​⩾⋯⩾λn​>0。由于$A^HA$AHA和$AA^H$AAH的非零特征值相同，且同一非零特征值的代数重数相等，于是由奇异值的定义得$\sigma_i=\sqrt{\lambda_i},i=1,2,...,n$σi​=λi​​,i=1,2,...,n。因为$(A^{-1})^HA^{-1}=(AA^H)^{-1}=U\Sigma^{-1}U^H$(A−1)HA−1=(AAH)−1=UΣ−1UH，于是由奇异值的定义得$A^{-1}$A−1的奇异值为$1/\sqrt{\lambda_n}\geqslant1/\sqrt{\lambda_{n-1}}\geqslant\cdots\geqslant1/\sqrt{\lambda_1}$1/λn​​⩾1/λn−1​​⩾⋯⩾1/λ1​​，即$1/\sigma_n\geqslant1/\sigma_{n-1}\geqslant\cdots\geqslant1/\sigma_1$1/σn​⩾1/σn−1​⩾⋯⩾1/σ1​。

3. 正规矩阵的奇异值与特征值的关系：

• 定理24：设正规矩阵$A\in C^{n\times n}$A∈Cn×n的奇异值为$\sigma_1 \geqslant \sigma_2\geqslant...\geqslant\sigma_n$σ1​⩾σ2​⩾...⩾σn​，特征值为$\lambda_1,\lambda_2,...,\lambda_n$λ1​,λ2​,...,λn​满足$|\lambda_1|\geqslant\ |\lambda_2|\geqslant ...\geqslant|\lambda_n|$∣λ1​∣⩾ ∣λ2​∣⩾...⩾∣λn​∣，则$\sigma_i=|\lambda_i|,i=1,2,...,n$σi​=∣λi​∣,i=1,2,...,n
  证明：
  设A的一个谱分解为$A=U\Sigma U^H$A=UΣUH，其中$\Sigma = diag(\lambda_1,\lambda_2,...,\lambda_n)$Σ=diag(λ1​,λ2​,...,λn​)，则$A^HA=U\overline{\Sigma}U^HU\Sigma U^H=U\overline{\Sigma}\Sigma U^H$AHA=UΣUHUΣUH=UΣΣUH。注意到该式是$A^HA$AHA的一个谱分解，且$\overline{\Sigma}\Sigma$ΣΣ的对角元为$|\lambda_1|^2\geqslant\ |\lambda_2|^2\geqslant ...\geqslant|\lambda_n|^2$∣λ1​∣2⩾ ∣λ2​∣2⩾...⩾∣λn​∣2，故根据奇异值的定义得$\sigma_i=|\lambda_i|,i=1,2,...,n$σi​=∣λi​∣,i=1,2,...,n。

下面我们进入奇异值分解。

SVD的存在性定理

• 定义1：设$A\in{C^{m\times{n}}_r}$A∈Crm×n​，若存在m阶酋矩阵U和n阶酋矩阵V，以及$m\times{n}$m×n广义对角矩阵$\Lambda=\begin{bmatrix}\Sigma&O\\O&O\end{bmatrix}$Λ=[ΣO​OO​]，其中$\Sigma=diag(\sigma_1,...,\sigma_r)$Σ=diag(σ1​,...,σr​)，$\sigma_1\geqslant ..\geqslant \sigma_r>0$σ1​⩾..⩾σr​>0为A的非零奇异值，使得$A=U\Lambda V^H$A=UΛVH，则称$A=U\Lambda V^H$A=UΛVH是A的一个奇异值分解
  【注1】由于在$\Sigma$Σ的对角线上$A$A的非零奇异值是从大到小排列的，故若$A$A的奇异值分解存在，则$\Lambda$Λ唯一。在有些资料的定义中，广义对角矩阵$\Lambda$Λ的对角线元素的大小顺序可以是任意的，但一般来说为便于分析更常约束$\Lambda$Λ的对角线元素从大到小排列。
  【注2】由于$A^HA$AHA和$AA^H$AAH的非零特征值相同，且同一非零特征值的代数重数相等，故A的非零奇异值既是$A^HA$AHA的非零特征值的算数平方根，又是$AA^H$AAH的非零特征值的算数平方根。
  【注3】由奇异值分解的定义及注2知，若$A=U\Lambda V^H$A=UΛVH是A的一个奇异值分解，则$A^H=V\Lambda U^H$AH=VΛUH是$A^H$AH的一个奇异值分解（但需注意的是，$A$A的奇异值与$A^H$AH的奇异值不完全等同，且只差在零奇异值上）

上述定义的条件可以减弱：

• 定义2：设$A\in C^{m\times n}$A∈Cm×n，若存在m阶酋矩阵$U$U和n阶酋矩阵$V$V，以及$m\times{n}$m×n广义对角矩阵$\Lambda=\begin{bmatrix}\Sigma&O\\O&O\end{bmatrix}$Λ=[ΣO​OO​]，其中$\Sigma=diag(\sigma_1,\sigma_2,...,\sigma_r)$Σ=diag(σ1​,σ2​,...,σr​)，$\sigma_1\geqslant\sigma_2\geqslant...\sigma_r\gt 0$σ1​⩾σ2​⩾...σr​>0，使得$A=U\Lambda V^H$A=UΛVH，则称$A=U\Lambda V^H$A=UΛVH是$A$A的一个奇异值分解
  【注】注意定义1和定义2的区别：定义1中设$A\in{C^{m\times{n}}_r}$A∈Crm×n​，而定义2中设$A\in C^{m\times n}$A∈Cm×n，即$r$r在定义1中指明为$A$A的秩，而在定义2中并未指明；定义1中直接指明$\sigma_1\geqslant\sigma_2\geqslant...\sigma_r\gt 0$σ1​⩾σ2​⩾...σr​>0为$A$A的非零奇异值，而在定义2中并未指明

这两个定义是等价的：
显然若定义1的条件被满足，则定义2的条件也被满足（定义2的条件相较于定义1弱化了）。
若定义2的条件被满足，则由$r(A)=r(U\Lambda V^H)=r(\Lambda)=r(\Sigma)=r$r(A)=r(UΛVH)=r(Λ)=r(Σ)=r知$A\in C^{m\times n}_r$A∈Crm×n​（即$r$r恰为$A$A的秩），注意到$A^HA=(U\Lambda V^H)^H(U\Lambda V^H)=V\Lambda^TU^HU\Lambda V^H=V\Lambda^T\Lambda V^H$AHA=(UΛVH)H(UΛVH)=VΛTUHUΛVH=VΛTΛVH是$A^HA$AHA的一个谱分解，于是$\Lambda^T\Lambda$ΛTΛ的非零对角线元素$\sigma_1^2\geqslant\sigma_2^2\geqslant...\sigma_r^2\gt 0$σ12​⩾σ22​⩾...σr2​>0恰为$A^HA$AHA的非零特征值，于是根据奇异值的定义得$\sigma_1\geqslant\sigma_2\geqslant...\sigma_r\gt 0$σ1​⩾σ2​⩾...σr​>0是$A$A的非零奇异值，即定义1的条件也被满足。

下面我们证明任意矩阵的奇异值分解的存在性：

• 定理25：任意矩阵$A\in{C^{m\times{n}}_r}$A∈Crm×n​都存在奇异值分解$A=U\Lambda V^H$A=UΛVH，其中U、V分别为m、n阶酋矩阵，$\Lambda=\begin{bmatrix}\Sigma&O\\O&O\end{bmatrix}$Λ=[ΣO​OO​]，$\Sigma=diag(\sigma_1,...,\sigma_r)$Σ=diag(σ1​,...,σr​)，$\sigma_1\geqslant ..\geqslant \sigma_r$σ1​⩾..⩾σr​为A的非零奇异值
  证明：
  由于$A^HA$AHA是n阶正规矩阵，故存在n阶酋矩阵V使得$V^HA^HAV=\begin{bmatrix}\Sigma^2&O\\O&O\end{bmatrix}$VHAHAV=[Σ2O​OO​]。将V分块$V=\begin{bmatrix}V_1&V_2\end{bmatrix}$V=[V1​​V2​​]，其中$V_1$V1​是$n\times{r}$n×r矩阵，$V_2$V2​是$r\times{n}$r×n矩阵。则$V_1^HA^HAV_1=\Sigma^2$V1H​AHAV1​=Σ2，$V_2^HA^HAV_2=O$V2H​AHAV2​=O，即$\Sigma^{-1}V_1^HA^HAV_1\Sigma^{-1}=I_r$Σ−1V1H​AHAV1​Σ−1=Ir​，$(AV_2)^H(AV_2)=O$(AV2​)H(AV2​)=O。设$U_1=AV_1\Sigma^{-1}$U1​=AV1​Σ−1，则有$U_1^HU_1=I_r$U1H​U1​=Ir​，$AV_2=O$AV2​=O。由于$U_1$U1​的列向量组为单位正交向量组（注意是r个m维向量），故由扩充定理以及Schmidt正交化方法可将$U_1$U1​的列向量组扩充为$C^m$Cm的一组标准正交基，于是构造出m阶酋矩阵$U=\begin{bmatrix}U_1&U_2\end{bmatrix}$U=[U1​​U2​​]。由$\begin{aligned}U^HAV&=\begin{bmatrix}U^H_1\\U^H_2\end{bmatrix}A\begin{bmatrix}V_1&V_2\end{bmatrix}\\&=\begin{bmatrix}U_1^HAV_1&U_1^HAV_2\\U_2^HAV_1&U_2^HAV_2\end{bmatrix}\\&=\begin{bmatrix}\Sigma&O\\O&O\end{bmatrix}=\Lambda\end{aligned}$UHAV​=[U1H​U2H​​]A[V1​​V2​​]=[U1H​AV1​U2H​AV1​​U1H​AV2​U2H​AV2​​]=[ΣO​OO​]=Λ​知$A=U\Lambda V^H$A=UΛVH就是A的一个奇异值分解。
  【注】该定理的证明实际上就是通过将$A^HA$AHA进行谱分解构造出A的一个奇异值分解。若A是一实矩阵，使用类似的构造方法（不同之处在于$A^HA=A^TA$AHA=ATA的谱分解应选择“实的”谱分解，且应将$U_1$U1​的列向量组扩充为$R^m$Rm的标准正交基）可知，A存在“实的”奇异值分解，即$A=U\Lambda V^T$A=UΛVT，其中$U$U、$V$V是实正交矩阵，$\Lambda$Λ是实广义对角矩阵。

SVD的构造方法（参考资料）

由定理25的证明过程可以看出，奇异值分解的构造是比较复杂的（先构造$A^HA$AHA的特征值分解，再构造$A$A的奇异值分解的话时间复杂度太高，且数值稳定性不好）。一般，奇异值分解采用如下算法：第一步用Householder变换将A化为双对角阵，第二步用QR分解或单边Jacobi旋转求双对角阵的SVD，复杂度可以到$O(mn^2)$O(mn2)，且有很好的数值稳定性。（详见英文维基百科）

SVD的性质

现在我们来认识一下奇异值分解的数学性质：
（以下均设$A\in{C^{m\times{n}}_r}$A∈Crm×n​且$A=U\Lambda V^H$A=UΛVH是A的一个奇异值分解）

• 奇异值与奇异性的关系：若A是n阶方阵，则$|det(A)|=|det(U)|det(\Lambda)|det(V^H)|=\sigma_1\sigma_2...\sigma_n$∣det(A)∣=∣det(U)∣det(Λ)∣det(VH)∣=σ1​σ2​...σn​，可见A是非奇异的等价于A的奇异值都不为零
• 全奇异值分解与截尾奇异值分解：
  • 全奇异值分解：就是前面我们所说的奇异值分解$A=U\Lambda V^H$A=UΛVH。
  • 截尾奇异值分解：设$U=\begin{bmatrix}U_1&U_2\end{bmatrix}$U=[U1​​U2​​]，$V=\begin{bmatrix}V_1&V_2\end{bmatrix}$V=[V1​​V2​​]，其中$U_1$U1​是U的前r列（注意r是A的秩），$V_1$V1​是V的前r列。则$A=U\Lambda V^H=\begin{bmatrix}U_1&U_2\end{bmatrix}\begin{bmatrix}\Sigma_r&O\\O&O\end{bmatrix}\begin{bmatrix}V_1^H\\V_2^H\end{bmatrix}=U_1\Sigma_rV_1^H$A=UΛVH=[U1​​U2​​][Σr​O​OO​][V1H​V2H​​]=U1​Σr​V1H​。称$A=U_1\Sigma_rV_1^H$A=U1​Σr​V1H​为A的截尾奇异值分解。
    （注意：截尾奇异值分解表明，实际上酋矩阵U和V各自的子矩阵$U_1$U1​和$V_1$V1​和A的全部非零奇异值就已携带了原矩阵A的全部信息）
  • 当A是满秩方阵时，A的截尾奇异值分解和全奇异值分解是等同的
  • 如果仔细观察截尾奇异值分解式，会发现它是A的一个满秩分解：$A =U_1(\Sigma_rV_1^H)$A=U1​(Σr​V1H​)，$U_1$U1​是一列满秩矩阵，$\Sigma_rV^H_1$Σr​V1H​是一行满秩矩阵；或者$A=(U_1\Sigma_r)V_1^H$A=(U1​Σr​)V1H​，$U_1\Sigma_r$U1​Σr​是一列满秩矩阵，$V_1^H$V1H​是一行满秩矩阵；再或者$A=(U_1\sqrt{\Sigma_r})(\sqrt{\Sigma_r}V_1^H)$A=(U1​Σr​​)(Σr​​V1H​)，其中$\sqrt{\Sigma_r}=diag(\sqrt{\sigma_1},...,{\sigma_r})$Σr​​=diag(σ1​​,...,σr​)，$U_1\sqrt{\Sigma_r}$U1​Σr​​是一列满秩矩阵，$\sqrt{\Sigma_r}V_1^H$Σr​​V1H​是一行满秩矩阵……等等。
• 认识酋矩阵U和V：
  • 左奇异向量与右奇异向量：
    U的列向量称为A的左奇异向量，V的列向量称为A的右奇异向量。
    $A$A的左奇异向量都是$AA^H$AAH的特征向量，$A$A的右奇异向量都是$A^HA$AHA的特征向量。（原因：根据$A=U\Lambda V^H$A=UΛVH，有$AA^H=U\Lambda V^HV\Lambda ^TU^H=U(\Lambda\Lambda^T)U^H$AAH=UΛVHVΛTUH=U(ΛΛT)UH，注意这是$AA^H$AAH的一个谱分解，于是$U$U的列向量都是$A^HA$AHA的特征向量。同理，根据$A^HA=V(\Lambda^T\Lambda)V^H$AHA=V(ΛTΛ)VH是$A^HA$AHA的一个谱分解就知道$V$V的列向量都是$AA^H$AAH的特征向量）
  • 设$U=\begin{bmatrix}U_1&U_2\end{bmatrix}$U=[U1​​U2​​]，其中$U_1$U1​是U的前$r$r列（注意r是A的秩）构成的子矩阵。则$U_1$U1​的列向量组是A的列空间$R(A)$R(A)的标准正交基，$U_2$U2​的列向量组是$A^H$AH的零空间$N(A^H)$N(AH)的标准正交基
    （原因：观察截尾奇异值分解式$A=U_1(\Sigma_rV_1^H)$A=U1​(Σr​V1H​)，可见A的列向量组可由$U_1$U1​的列向量组线性表示，又$dim\ R(A)=r=r(U_1)$dim R(A)=r=r(U1​)，所以$U_1$U1​的列向量组是$R(A)$R(A)的标准正交基；计算可得$A^HU_2=V_1\Sigma_r^TU_1^HU_2=V_1\Sigma_r^TO=O$AHU2​=V1​ΣrT​U1H​U2​=V1​ΣrT​O=O，又$dim\ N(A^H)=m-r=r(U_2)$dim N(AH)=m−r=r(U2​)，所以$U_2$U2​的列向量组是$N(A^H)$N(AH)的标准正交基）
    【注】这说明奇异值分解可以用来求矩阵的列空间及其正交补的标准正交基。
  • 设$V=\begin{bmatrix}V_1&V_2\end{bmatrix}$V=[V1​​V2​​]，其中$V_1$V1​是V的前r列构成的子矩阵。则$V_1$V1​的列向量组是$A^H$AH的列空间$R(A^H)$R(AH)的一组标准正交基，$V_2$V2​的列向量组是A的零空间$N(A)$N(A)的一组标准正交基
    （原因和上面同理）
    【注】这说明奇异值分解可以用来求矩阵的零空间及其正交补的标准正交基。
• 奇异值与特征值的关系
  • 定理26：若A是对称半正定矩阵，则A的奇异值与A的特征值完全等同，A的一个特征值分解也是A的一个奇异值分解
    证明：
    若A是对称半正定矩阵，则A的特征值（为实数）均非负。设n阶方阵$A$A的一个谱分解为$A=U\Lambda U^H$A=UΛUH，其中$\Lambda=diag(\lambda_1,...,\lambda_n)$Λ=diag(λ1​,...,λn​)，则$A^HA=A^2=U\Lambda U^HU\Lambda U^H=U\Lambda^2 U^H$AHA=A2=UΛUHUΛUH=UΛ2UH。这说明$A^HA$AHA的特征值为$\lambda_1^2,...,\lambda_n^2$λ12​,...,λn2​，故由奇异值的定义知A的奇异值$\sigma_i=\sqrt{\lambda_i^2}=\lambda_i,i=1,2,...,n$σi​=λi2​​=λi​,i=1,2,...,n，即A的奇异值与其特征值等同。进而由奇异值分解的定义知$A=U\Lambda U^H$A=UΛUH是A的一个奇异值分解。

SVD用于求矩阵的逼近

奇异值分解可以视作方阵（正规矩阵）的特征值分解在一般的长方矩阵上的推广，奇异值和奇异向量是描述长方矩阵的特征的量，这一点可以通过照片压缩的例子直观地理解。和特征值分解一样，奇异值分解可以改写成矩阵的特征的加权和：由$A\in{C^{m\times{n}}_r}$A∈Crm×n​的截尾奇异值分解式$A=U_1\Sigma_rV_1^H$A=U1​Σr​V1H​，若设$U_1=\begin{bmatrix}u_1&...u_r\end{bmatrix}$U1​=[u1​​...ur​​]，$V_1=\begin{bmatrix}v_1&...v_r\end{bmatrix}$V1​=[v1​​...vr​​]，则有$A=\Sigma_{i=1}^r\sigma_iu_iv_i^H$A=Σi=1r​σi​ui​viH​在求A的近似矩阵时，只要去掉奇异值较小的项即可（等价于在奇异值分解式中令对角矩阵上相应的奇异值为零）。另外，注意到$r(A)=r(U_1\Sigma_rV_1^H)=r(\Sigma_r)$r(A)=r(U1​Σr​V1H​)=r(Σr​)，故每去掉$A=\Sigma_{i=1}^r\sigma_iu_iv_i^H$A=Σi=1r​σi​ui​viH​中的一项，$A$A的秩就减少1，所以这样求得的近似矩阵实际上是对原矩阵的低秩逼近。这种方法可以实现对数据的去噪、压缩等。还有一点比较有趣，$\sigma_iu_iv_i^H$σi​ui​viH​是一个秩为1的矩阵（因为$r(\sigma_iu_iv_i^H)\leqslant r(u_i)=1$r(σi​ui​viH​)⩽r(ui​)=1且$r(\sigma_iu_iv_i^H)\geqslant r(u_i)+r(v_i^H)-1=1$r(σi​ui​viH​)⩾r(ui​)+r(viH​)−1=1），所以$A=\Sigma_{i=1}^r\sigma_iu_iv_i^H$A=Σi=1r​σi​ui​viH​实际上是把A拆分成了若干独立的低秩矩阵（秩为1）的加权和，每个低秩项都可视作A的一个特征项。
总的来说，每去掉$A=\Sigma_{i=1}^r\sigma_iu_iv_i^H$A=Σi=1r​σi​ui​viH​中的一项，不仅去掉的是一个秩为1的项，还恰好使$A$A的秩减少了1。

SVD在推荐系统中的应用

奇异值分解的应用有很多，这里简单介绍一下SVD在推荐系统中的应用：
推荐算法可以分为传统的SVD方法和凸优化的方法，这里介绍传统的SVD算法。传统算法中SVD的作用是提取每个user和每个item的主要特征（实际上是对原评分矩阵做低秩逼近），用于计算每个item间的相似度或每个user间的相似度，如果利用user间的相似度来预测评分，就是User_based的算法；如果利用item间的相似度来预测评分，就是Item_based的算法。

设有$n\times m$n×m评分矩阵A（如上图），A的$(i,j)$(i,j)元素是$User(j)$User(j)对$Item(i)$Item(i)的评分。通常A是一个稀疏矩阵，即A中大多数元素是未定义的，可以使用均值归一化的方法填充（注意这里的填充是为了后续可计算，而不是作为预测值）：先算出每个item已有评分的均分，然后给该item的每个已有评分减去该item的均分，并用0填充该item下未定义的评分。
设填充好的评分矩阵是B。求出B的“实的”奇异值分解式$B=U\Lambda V^T$B=UΛVT（$U$U、$\Lambda$Λ、$V$V都是实矩阵），其中B的奇异值在$\Lambda$Λ的对角线上从大到小排列，令$\Lambda$Λ中B的最小的k个非零奇异值为零（具体k取多少取决于你想保留原矩阵B的多少信息），就得到了B的一个低秩逼近矩阵C，C的截尾奇异值分解式是$C=U_1\Sigma V_1^T$C=U1​ΣV1T​（如果保留了B的前$l$l大奇异值，则$U_1$U1​就是$U$U的前$l$l列，$V_1$V1​就是$V$V的前$l$l列）。以User_based为例，注意到$U_1$U1​的列向量组是C的列空间的标准正交基，于是可将C的每一列在该基下的坐标向量求出（实际中不会求出矩阵C，所以实际计算时常是拿B的每一列求），得到了降维后User的特征，于是可以计算任意两个User间的相似度（余弦相似度、欧式距离、皮尔逊相关系数等相似度函数均可）。
现在，若要预测$User(j)$User(j)对$item(i)$item(i)的评分（前提是$User(j)$User(j)未对$item(i)$item(i)打分），可以看看其他user对$item(i)$item(i)的评分是多少，将其他user与$User(j)$User(j)的相似度作为权重系数，求出其他user对$item(i)$item(i)的评分的加权平均值，作为$User(j)$User(j)对$item(i)$item(i)的评分的预测值。最后，推荐过程则是基于预测的评分，将预测评分较高的item推荐给用户即可。
【补充】如何求C的列向量在已知C的列空间的标准正交基（即$U_1$U1​的列向量组）下的坐标：设$C$C的第$i$i个列向量的坐标向量是$z_i$zi​，$Z=\begin{bmatrix}z_1&...&z_n\end{bmatrix}$Z=[z1​​...​zn​​]。那么就是要求得矩阵Z使得$C=U_1Z$C=U1​Z，两端左乘$U_1^T$U1T​，得到$U_1^TC=U_1^TU_1Z=Z$U1T​C=U1T​U1​Z=Z。故求Z的公式是$Z=U_1^TC$Z=U1T​C。