7.1 奇异值分解SVD和对称矩阵谱分解
 
矩阵 $A_{mn},rankA=r<(m,n)$ 是亏秩矩阵时，虽然高斯消元法可以求得方程 $A\mathbf{x}=\mathbf{b}$ 的解，很可惜的是，采用高斯消元法，有两个缺点：第一是，当方程不存在精确解时，高斯消元法无法得到最小二乘解；第二是，当方程存在精确解时，其解的结构是特解加零解。当选择不同的矩阵 $A$ 列空间的极大无关组时，可以求得不同的特解，理论上存在无穷多特解满足方程 $A\mathbf{x}=\mathbf{b}$ ，一般情况下，我们希望获得最特殊的特解－－最小范数解，即所有特解中，内积最小特解 $\min \Vert {\mathbf{x}}_p\Vert$ 。
 
由于矩阵 $A$ 是亏秩矩阵，其列向量不是 $R^m$ 空间的基，故不是任意 $\mathbf{b}$ 都有精确解，只有当 $\mathbf{b}$ 位于矩阵 $A$ 列空间时，才存在精确解，否则只能获得最小二乘解。令向量 $\mathbf{b}$ 向矩阵 $A$ 列空间的投影向量为 ${\mathbf{b}}_p$ ，则方程 $A\mathbf{x}={\mathbf{b}}_p$ 有精确解，称为最小二乘解，由于矩阵 $A$ 不是列满秩矩阵，故不能采用第五章方法获得最小二乘解。同时由于矩阵 $A$ 列向量组是相关组，故方程 $A\mathbf{x}={\mathbf{b}}_p$ 有无穷多解，其解的结构是特解加零解，我们希望获得最小范数特解。综上，对于方程 $A\mathbf{x}=\mathbf{b}$ ，对任意向量 $\mathbf{b}$，我们希望获得最小范数最小二乘解和零解。
 
方程 $A\mathbf{x}=\mathbf{b}$ 的解空间为 $R^n$ 空间，令向量组 ${\mathbf{v}}_i,i=1,\cdots ,n$ 是 $R^n$ 空间中任意 $n$ 个线性无关的单位向量，则向量组 $A{\mathbf{v}}_i,i=1,\cdots ,n$ 是 $R^m$ 空间中向量，对其进行单位化，得 $A{\mathbf{v}}_i={\sigma }_i{\mathbf{u}}_i,{\mathbf{u}}_i是单位向量，{\sigma }_i\ge 0是向量A{\mathbf{v}}_i的长度$ 。向量 $A^T{\mathbf{u}}_i$ 是 $n$ 维，所以位于 $R^n$ 空间，故其能被该空间的基表示，向量组 ${\mathbf{v}}_i,i=1,\cdots ,n$ 是 $R^n$ 空间的基，故 $A^T{\mathbf{u}}_i$ 能被向量组 ${\mathbf{v}}_i,i=1,\cdots ,n$ 线性表示，所以令 $A^T{\mathbf{u}}_i={\sum }_{j=1}^n{k}_{ij}{\mathbf{v}}_j$ 。令矩阵 $V=[{\mathbf{v}}_1,\cdots ,{\mathbf{v}}_n]$ ，则
 $$\begin{gathered} A^{T}A{\mathbf{v}}_i=A^T(A{\mathbf{v}}_i)=A^T{\sigma }_i{\mathbf{u}}_i={\sigma }_i\sum _{j=1}^n{k}_{ij}{\mathbf{v}}_j=V{\Lambda }_i \\ 其中向量{\Lambda }_i=({\sigma }_i{k}_{i1},{\sigma }_i{k}_{i2},\cdots ,{\sigma }_i{k}_{in}) \end{gathered}$$
 
故
 $$\begin{gathered} A^{T}A[{\mathbf{v}}_1,\cdots ,{\mathbf{v}}_n]=V[{\Lambda }_1,\cdots ,{\Lambda }_n] \\ {A}^{T}AV=V\Lambda \\ {A}^{T}A=V\Lambda V^{-1} \end{gathered}$$
 
$V$ 是 $R^n$ 空间中的任意基，如何选择该基，能使 $V\Lambda V^{-1}$ 最简洁？表达式涉及矩阵 $V$ 的逆，故希望求逆简单。能直接获得矩阵逆的矩阵有正交矩阵，对角阵，单位阵，矩阵 $V$ 为对角阵或单位阵，则会造成矩阵 $\Lambda$ 复杂。矩阵 $V$ 为正交矩阵时，能使矩阵 $\Lambda$ 为对角阵！该性质就是对称矩阵谱分解定理。
 
对称矩阵谱分解定理 任意对称矩阵 $S$ 能分解为正交矩阵 $Q$ 和对角阵 $\Lambda$ ，且满足 $S=Q\Lambda Q^T$ 。
 
令 $Q=[{\mathbf{q}}_1,\cdots ,{\mathbf{q}}_n]$ 和 $\Lambda =diag({\lambda }_1,\cdots ,{\lambda }_n)$ 。
 
$$\begin{gathered} S=Q\Lambda Q^T=[{\mathbf{q}}_1,\cdots ,{\mathbf{q}}_n]diag({\lambda }_1,\cdots ,{\lambda }_n)[{\mathbf{q}}_1,\cdots ,{\mathbf{q}}_n{]}^T=[{\mathbf{q}}_1,\cdots ,{\mathbf{q}}_n]\left[\begin{array}{c}{\lambda }_1{\mathbf{q}}_1^T\\ ⋮\\ {\lambda }_n^T{\mathbf{q}}_n^T\end{array}\right] \\ ={\lambda }_1{\mathbf{q}}_1{\mathbf{q}}_1^T+\cdots +{\lambda }_n{\mathbf{q}}_n{\mathbf{q}}_n^T \\ =\sum _{i=1}^n{\lambda }_i{\mathbf{q}}_i{\mathbf{q}}_i^T \end{gathered}$$
 
注意 $\mathbf{u}{\mathbf{v}}^T$ 是矩阵，称为向量外积，需要与向量内积区分。因为 $rank({\mathbf{q}}_i{\mathbf{q}}_i^T)=1$ ，$S=Q\Lambda Q^T={\lambda }_1{\mathbf{q}}_1{\mathbf{q}}_1^T+\cdots +{\lambda }_n{\mathbf{q}}_n{\mathbf{q}}_n^T$ ，这表明对称矩阵可分解为 $n$ 个简单矩阵（秩为$1$）${\mathbf{q}}_i{\mathbf{q}}_i^T$ 之和，其系数为 ${\lambda }_i$ 。因为 ${\mathbf{q}}_i$ 都是单位向量，故 ${\lambda }_i$ 绝对值大的分量更重要，是主成分。
 
因为 $Q$ 是正交矩阵，故 ${\mathbf{q}}_i{\mathbf{q}}_i^T=1,{\mathbf{q}}_i{\mathbf{q}}_j^T=0fori\ne j$，所以 $S{\mathbf{q}}_i=({\lambda }_1{\mathbf{q}}_1{\mathbf{q}}_1^T+\cdots +{\lambda }_n{\mathbf{q}}_n{\mathbf{q}}_n^T){\mathbf{q}}_i={\lambda }_1{\mathbf{q}}_1({\mathbf{q}}_1^T{\mathbf{q}}_i)+\cdots +{\lambda }_n{\mathbf{q}}_n({\mathbf{q}}_n^T{\mathbf{q}}_i)＝{\lambda }_i{\mathbf{q}}_i$ 即 $S{\mathbf{q}}_i={\lambda }_i{\mathbf{q}}_i$ ，我们称 ${\lambda }_i$ 为矩阵 $S$ 的特征值，${\mathbf{q}}_i$ 为对应的特征向量。
 
$$rankS=rank(Q\Lambda Q^T)=rank(\Lambda Q^T)=rank\Lambda$$
 所以对角元素 ${\lambda }_i$ 非零数目等于矩阵 $S$ 的秩。
 
后面证明该定理。
 
因为矩阵 $A^{T}A$ 是对称矩阵，故能分解为 $A^{T}A=V\Lambda V^T$ ，得到正交矩阵 $V=[{\mathbf{v}}_1,\cdots ,{\mathbf{v}}_n]$ 和 对角阵 $\Lambda$ 的对角元素 ${\lambda }_i$ 值，且对角阵 $\Lambda$ 的对角元素 ${\lambda }_i$ 非负。因为对任意向量 $\mathbf{x}$ ，有 ${\mathbf{x}}^T{A}^{T}A\mathbf{x}=(A\mathbf{x}{)}^T(A\mathbf{x})\ge 0$ ，故 ${\mathbf{x}}^{T}V\Lambda V^T\mathbf{x}=(V^T\mathbf{x}{)}^T\Lambda (V^T\mathbf{x})={\mathbf{y}}^T\Lambda \mathbf{y}={\lambda }_1{y}_1^2+{\lambda }_2{y}_2^2+\cdots +{\lambda }_n{y}_n^2\ge 0$ 成立，所以 ${\lambda }_i\ge 0$ 。
 
根据对称矩阵性质 $S{\mathbf{q}}_i={\lambda }_i{\mathbf{q}}_i$ ，故 $A^{T}A{\mathbf{v}}_i={\lambda }_i{\mathbf{v}}_i$ 成立，矩阵 $A^{T}A$ 特征值为 ${\lambda }_i$ 且非负，我们习惯把特征值按降序排列，即 ${\lambda }_1\ge {\lambda }_2\ge \cdots {\lambda }_n\ge 0$ 。
 
根据对称矩阵性质 $S={\lambda }_1{\mathbf{q}}_1{\mathbf{q}}_1^T+\cdots +{\lambda }_n{\mathbf{q}}_n{\mathbf{q}}_n^T$ ，故 $A^{T}A={\lambda }_1{\mathbf{v}}_1{\mathbf{v}}_1^T+\cdots +{\lambda }_n{\mathbf{v}}_n{\mathbf{v}}_n^T$ ，由于 ${\lambda }_i$ 非负且按降序排列，故靠前的 ${\lambda }_i{\mathbf{v}}_i{\mathbf{v}}_i^T$ 占矩阵 $A^{T}A$ 比例更大，是主成分。
 
$r=rankA=rank(A^{T}A)=rank\Lambda$ ，所以对角元素 ${\lambda }_i$ 非零数目等于矩阵 $A$ 的秩！
 
现在证明向量组 $U=[{\mathbf{u}}_1,\cdots ,{\mathbf{u}}_n]$ 两两正交。
 $$({\mathbf{u}}_i^T{\mathbf{u}}_j)({\sigma }_i{\sigma }_j)=(A{\mathbf{v}}_i{)}^T(A{\mathbf{v}}_j)={\mathbf{v}}_i^T{A}^{T}A{\mathbf{v}}_j={\mathbf{v}}_i^T(A^{T}A{\mathbf{v}}_j)={\mathbf{v}}_i^T{\lambda }_j{\mathbf{v}}_j={\lambda }_j{\mathbf{v}}_i^T{\mathbf{v}}_j$$
 因为向量组 $V=[{\mathbf{v}}_1,\cdots ,{\mathbf{v}}_n]$ 两两正交，故得证。
 
当 $i=j$ 时 $({\mathbf{u}}_i^T{\mathbf{u}}_i)({\sigma }_i{\sigma }_i)={\lambda }_i({\mathbf{v}}_i^T{\mathbf{v}}_i)$，因为 ${\mathbf{u}}_i,{\mathbf{v}}_i$ 是单位向量，故 ${\lambda }_i={\sigma }_i^2$ 。
 
又根据 $A^{T}A{\mathbf{v}}_i={\sigma }_i{\sum }_{j=1}^n{k}_{ij}{\mathbf{v}}_j={\lambda }_i{\mathbf{v}}_i$ 得 $k_{ij}=0forj\ne i$ 和 ${\lambda }_i={\sigma }_i{k}_{ii}$ ，得 $k_{ii}={\sigma }_i$，所以 $A^T{\mathbf{u}}_i={\sum }_{j=1}^n{k}_{ij}{\mathbf{v}}_j=k_{ii}{\mathbf{v}}_i={\sigma }_i{\mathbf{v}}_i$ 。
 
$A{A}^T{\mathbf{u}}_i=A{\sigma }_i{\mathbf{v}}_i={\sigma }_{i}A{\mathbf{v}}_i={\sigma }_i{\sigma }_i{\mathbf{u}}_i={\lambda }_i{\mathbf{u}}_i$ ，所以对称矩阵 $A{A}^T$ 特征值为 ${\lambda }_i$ ，对应特征向量为 ${\mathbf{u}}_i$ 。
 
综合上面结论可得矩阵的奇异值分解定理
 1、首先根据对称矩阵谱分解定理，可得 $A^{T}A=V\Lambda V^T={\lambda }_1{\mathbf{v}}_1{\mathbf{v}}_1^T+\cdots +{\lambda }_n{\mathbf{v}}_n{\mathbf{v}}_n^T$，矩阵 $V=[{\mathbf{v}}_1,\cdots ,{\mathbf{v}}_n]$ 是正交矩阵，矩阵 $\Lambda$ 是对角阵，对角元素 ${\lambda }_i\ge 0$ 按降序排列，非零数目等于 $rankA$ 。
 2、满足如下性质
 $$\begin{gathered} A{\mathbf{v}}_i={\sigma }_i{\mathbf{u}}_i \\ {A}^T{\mathbf{u}}_i={\sigma }_i{\mathbf{v}}_i \\ {A}^{T}A{\mathbf{v}}_i={\lambda }_i{\mathbf{v}}_i \\ A{A}^T{\mathbf{u}}_i={\lambda }_i{\mathbf{u}}_i \\ {\sigma }_i=\sqrt{{\lambda }_i}称为奇异值，{\mathbf{v}}_i称为右奇异向量，{\mathbf{u}}_i称为左奇异向量. \end{gathered}$$
 
几点说明：
 1、正交矩阵 $V=[{\mathbf{v}}_1,\cdots ,{\mathbf{v}}_n]$ 和对角阵 $\Lambda$ 如何获得呢？理论上可通过解方程 $A^{T}A{\mathbf{v}}_i={\lambda }_i{\mathbf{v}}_i$ 获得，具体如何解后面介绍，非零奇异值 ${\sigma }_i=\sqrt{{\lambda }_i},i=1,\cdots ,r=rankA$ ，${\sigma }_i$ 是向量 $A{\mathbf{v}}_i$ 的长度和向量 $A^T{\mathbf{u}}_i$ 的长度；
 2、根据非零奇异值计算得到 ${\mathbf{u}}_i=A{\mathbf{v}}_i/{\sigma }_i,i=1,\cdots ,r=rankA$ ；
 3、由于向量组 ${\mathbf{u}}_i，i=1,\cdots ,r=rankA$ 两两正交，根据基的扩充定理，可扩充 $m-r$ 个单位向量 ${\mathbf{u}}_i，i=r+1,\cdots ,m$ ，使矩阵 $U=[{\mathbf{u}}_1，\cdots ,{\mathbf{u}}_m]$ 为正交矩阵，并满足对称矩阵谱分解定理即 $A{A}^T=U\Lambda U^T={\lambda }_1{\mathbf{u}}_1{\mathbf{u}}_1^T+\cdots +{\lambda }_m{\mathbf{u}}_m{\mathbf{u}}_m^T$
 
根据 $A{\mathbf{v}}_i={\sigma }_i{\mathbf{u}}_i$ 得 $A{\mathbf{v}}_1={\sigma }_1{\mathbf{u}}_1$；$A{\mathbf{v}}_2={\sigma }_2{\mathbf{u}}_2$；$\cdots$；$A{\mathbf{v}}_r={\sigma }_r{\mathbf{u}}_r$ ，故 $A[{\mathbf{v}}_1,\cdots ,{\mathbf{v}}_r]=[{\mathbf{u}}_1,\cdots ,{\mathbf{u}}_r]diag({\sigma }_1,\cdots ,{\sigma }_r)$ ，写成矩阵形式 $A{V}_r=U_r{\Sigma }_r$ ，其中矩阵 $V_r=[{\mathbf{v}}_1,\cdots ,{\mathbf{v}}_r],U_r=[{\mathbf{u}}_1,\cdots ,{\mathbf{u}}_r],{\Sigma }_r=diag({\sigma }_1,\cdots ,{\sigma }_r)$ 满足 $V_r^T{V}_r=E_r,U_r^T{U}_r=E_r$ ，注意 $V_r{V}_r^T\ne E_r,U_r{U}_r^T\ne E_r$ 。
 
对 $A{V}_r=U_r{\Sigma }_r$ 可进行扩充即 $A[{\mathbf{v}}_1,\cdots ,{\mathbf{v}}_r,\cdots ,{\mathbf{v}}_n]=[{\mathbf{u}}_1,\cdots ,{\mathbf{u}}_r\cdots ,{\mathbf{u}}_m]diag({\sigma }_1,\cdots ,{\sigma }_r,0,\cdots ,0)$ 写成矩阵形式 $AV=U\Sigma$，此时矩阵 $V,U$ 均是正交矩阵，故 $A=U\Sigma V^T={\sigma }_1{\mathbf{u}}_1{\mathbf{v}}_1^T+\cdots +{\sigma }_r{\mathbf{u}}_r{\mathbf{v}}_r^T$，这表明秩为 $r$ 的任意矩阵 $A$ 可分解为 $r$ 个简单矩阵（秩为 $1$）的矩阵 ${\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^T$ 之和，且 ${\sigma }_1\ge {\sigma }_2\ge \cdots {\sigma }_r>0$，按重要性排序。这就是奇异值分解的核心。注意矩阵 $\Sigma$ 尺寸为 $(m,n)$，并不是对角阵，但其前 $(r,r)$ 子矩阵 ${\Sigma }_r$ 是对角阵，对角元素为 ${\sigma }_i>0$ ，矩阵其它元素均为 $0$ 。
 
根据 $A=U\Sigma V^T={\sigma }_1{\mathbf{u}}_1{\mathbf{v}}_1^T+\cdots +{\sigma }_r{\mathbf{u}}_r{\mathbf{v}}_r^T$ 可得 $A^T=V\Sigma U^T={\sigma }_1{\mathbf{v}}_1{\mathbf{u}}_1^T+\cdots +{\sigma }_r{\mathbf{v}}_r{\mathbf{u}}_r^T$ 。
 
$A^{T}A=V\Lambda V^T={\lambda }_1{\mathbf{v}}_1{\mathbf{v}}_1^T+\cdots +{\lambda }_r{\mathbf{v}}_r{\mathbf{v}}_r^T$ 和 $A{A}^T=U\Lambda U^T={\lambda }_1{\mathbf{u}}_1{\mathbf{u}}_1^T+\cdots +{\lambda }_r{\mathbf{u}}_r{\mathbf{u}}_r^T$ 。
 
举几个特殊例子说明奇异值分解。
 1、对单位矩阵 $A=E$ 进行奇异值分解。根据 $A^{T}A{\mathbf{v}}_i={\lambda }_i{\mathbf{v}}_i$ 得 $E^{T}E{\mathbf{v}}_i={\lambda }_i{\mathbf{v}}_i$ 即 ${\mathbf{v}}_i={\lambda }_i{\mathbf{v}}_i$ ，所以所有特征值 ${\lambda }_i=1$ 即 $\Sigma =E$。任意单位向量 ${\mathbf{v}}_i$ 均满足方程 $A^{T}A{\mathbf{v}}_i={\lambda }_i{\mathbf{v}}_i$，故可取任意正交矩阵 $V$ ，它们均是特征值 $1$ 对应的特征向量。根据 $A{\mathbf{v}}_i={\sigma }_i{\mathbf{u}}_i$ 得 ${\mathbf{u}}_i={\mathbf{v}}_i$， 故单位矩阵的奇异值分解为 $E=VE{V}^T$ ，$V$ 是任意正交矩阵。通过这个例子可以得出，矩阵的奇异值分解不唯一，只有当矩阵 $A$ 是方阵且奇异值均不相等时，分解才唯一。同一个奇异值可以对应多个奇异向量，甚至全部，奇异值对应奇异向量的数目称为几何重数。
 
2、对正交矩阵 $A=Q$ 进行奇异值分解。根据 $A^{T}A{\mathbf{v}}_i={\lambda }_i{\mathbf{v}}_i$ 得 $Q^{T}Q{\mathbf{v}}_i={\lambda }_i{\mathbf{v}}_i$ 即 ${\mathbf{v}}_i={\lambda }_i{\mathbf{v}}_i$ ，所以所有特征值 ${\lambda }_i=1$即 $\Sigma =E$。任意单位向量 ${\mathbf{v}}_i$ 均满足方程 $A^{T}A{\mathbf{v}}_i={\lambda }_i{\mathbf{v}}_i$，故可取任意正交矩阵 $V$ ，它们均是特征值 $1$ 对应的特征向量。根据 $A{\mathbf{v}}_i={\sigma }_i{\mathbf{u}}_i$ 得 ${\mathbf{u}}_i=Q{\mathbf{v}}_i$ 即 $U=QV$ ，故正交矩阵的奇异值分解为 $Q=(QV)E{V}^T$ ，$V$ 是任意正交矩阵。
 
3、对秩为 $1$ 矩阵 $A=\mathbf{x}{\mathbf{y}}^T$ 进行奇异值分解，其中 $\mathbf{x},\mathbf{y}$ 是单位向量。根据 $A^{T}A{\mathbf{v}}_i={\lambda }_i{\mathbf{v}}_i$ 得 $\mathbf{y}{\mathbf{y}}^T{\mathbf{v}}_i={\lambda }_i{\mathbf{v}}_i$ ，当取 ${\mathbf{v}}_i=\mathbf{y}$ 时有 ${\lambda }_i=1$ 。由于秩为 $1$ ，故只有${\lambda }_1=1$ ，其它奇异值均为 $0$ 。${\mathbf{u}}_1=A{\mathbf{v}}_1=\mathbf{x}$ 。故矩阵 $A=\mathbf{x}{\mathbf{y}}^T$ 的奇异值分解就是 $A=\mathbf{x}{\mathbf{y}}^T$ 。在 $R^n$ 空间扩充基向量得到正交矩阵 $V$ ，在 $R^m$ 空间扩充基向量得到正交矩阵 $U$ ，则 $A=U\Sigma V^T$ ，其中伪对角阵 ${\Sigma }_{11}=1，其它元素均为0$ 。
 
4、对角阵 $A=D=diag(d_1,\cdots ,d_n)$ 进行奇异值分解。根据 $A^{T}A{\mathbf{v}}_i={\lambda }_i{\mathbf{v}}_i$ 得 $diag(d_1^2,\cdots ,d_n^2){\mathbf{v}}_i={\lambda }_i{\mathbf{v}}_i$ 即 $(diag(d_1^2,\cdots ,d_n^2)-{\lambda }_{i}E){\mathbf{v}}_i=diag(d_1^2-{\lambda }_i,\cdots ,d_n^2-{\lambda }_i){\mathbf{v}}_i=((d_1^2-{\lambda }_i)v_{i1},\cdots ,(d_n^2-{\lambda }_i)v_{in})=0$ ，所以 ${\lambda }_1=d_1^2$ 时 ${\mathbf{v}}_1={\mathbf{e}}_1$，${\lambda }_i=d_i^2$ 时 ${\mathbf{v}}_i={\mathbf{e}}_i$。故正交矩阵 $V=E$ ，奇异值为 ${\sigma }_i=|d_i|$ ， $\Sigma =|D|$，根据 $A{\mathbf{v}}_i={\sigma }_i{\mathbf{u}}_i$ 得 ${\mathbf{u}}_i=D{\mathbf{e}}_i/|d_i|=sign(d_i){\mathbf{e}}_i$ 即 $U=sign(D)E$ ，故对角阵的奇异值分解为 $D=U\Sigma V^T=(sign(D)E)|D|E^T$。

上次听AK讲到谱分解的时候，若有所思，下面将对思考稍作记录。
 
矩阵谱分解
 
关于谱分解有很多定义，主要区别在于条件的强弱，有的要求一个$n$阶矩阵不仅要求可对角化，而且加强条件至其$n$个特征值${\lambda }_1,{\lambda }_2,...,{\lambda }_n$互异，我们这里由于不深入讨论谱分解，所以就采用最简单的定义来说。
 
 
 
定义：若$n$阶矩阵$A$可对角化，那么存在$n$个$n$阶方阵$G_i$使得$A={\sum }_{i=1}^n{\lambda }_i{G}_i$.
 
 
证明:设矩阵$A$的$n$个特征值为${\lambda }_1,{\lambda }_2,...,{\lambda }_n$，其对应的特征向量进行Gram-Schmidt 正交化后为${\alpha }_1,{\alpha }_2,...,{\alpha }_n$，那么有$A{\alpha }_i={\lambda }_i{\alpha }_i$。令$P=[{\alpha }_1,{\alpha }_2,...,{\alpha }_n]$，可以写成矩阵形式有$AP=P\cdot diag({\lambda }_1,{\lambda }_2,...,{\lambda }_n)$。
 此时，令：$P^{-1}=({\beta }_1^T,{\beta }_2^T,...{\beta }_n^T,{)}^T$，注意到这里的可逆性是由Gram-Schmidt 正交化保证的，当然，如果条件加强至特征值均互异，那么特征向量是相互独立的，这样不需要进行正交化，也可以保证可逆性。${\beta }_i$和${\alpha }_i$的size相同。
 KaTeX parse error: Unknown column alignment: * at position 112: …{\begin{array}{*̲{20}{c}} {\beta…
 
于是谱分解的命题得证，上述证明同时给出了谱分解的一个构造。
 
问题引入
 
在讲座中AK猜测谱分解可以像SVD那样对图像进行压缩，但是有个不好的地方在于和SVD不同，谱分解要求矩阵(图像)为方阵。
 
当时有若干想法（假设谱分解可以用于图像压缩）：
 
既然谱分解只能作用于方阵，而对于一个$m\cdot n$的图像矩阵$A$，那我们是否能对一个矩形方阵先进行正方形剖分，后处理呢？
正方形剖分后，分别进行压缩后重组的图像和直接进行压缩（假设是图像本来就是方阵的情况下）是否有区别？如果有，那么从肉眼角度，区别大不大？
既然要正方形剖分，那么这样的剖分是否存在？如果存在是否有最小正方形个数的剖分（这样的剖分可以使得处理和重组次数都最小）？如果有最小的剖分，那么这样的剖分数的方法是否唯一？
矩形的正方形剖分种类是否有限？
 
后来觉得不太对劲，虽然由谱分解$A={\sum }_{i=1}^n{\lambda }_i{G}_i$，可以舍弃掉特征值较小的部分。但是，较小？实际上，矩阵的特征值完全有可能是复数，甚至几乎都是复数(当然这里的复数是特指虚部不为0的意思)。而SVD所求的特征值是$A^{T}A$的，作为实对称矩阵的所有特征值必为实数。先用SVD来验证一下，“剖分-重组”的思路如何:
 
 
(a)和(b)两图都用SVD处理(仅保留一个特征值)，从(a)中可以发现“剖分-重组”从肉眼上差别不大，但是从(b)中可以发现差别还是有点明显的，实际上这种思路本身就不抱太大的希望2333。
 
矩形的最少正方形剖分
 
和完美正方形剖分不同的是，我们这里关注的是分成的正方形数量最小，而不需要和完美正方形剖分那样要求每个正方形大小互异。
 
正方形剖分是否存在？
 存在性是显然的，我们以一个5x3的矩形为例，我们显然可以如下图(a)所示
 
 
将其分成15个小正方形显然是一种剖分，存在性即可证明。此时实际上不仅给出了一种剖分的构造同时也给出了"de数"(剖分后正方形的数量，de是decomposition的缩写)的一个上界，由最小数原理（自然数集的任一非空子集必有最小数）知道，"de数"必有最小值，即对于任意矩形，存在最少的正方形剖分。
 
关于"de数"的界还可以参考这篇文章Tiling a Rectangle with the Fewest Squares ，这篇文章指出，对于一个$m\cdot n$的矩形，其中$m\ge n$，那么$log_2 n \leq $ de数 $\le \frac{m}{n}+C\cdot lo{g}_{2}n$,其中$C$是一个常数，虽然这个结论没什么太大的用处，但是上下界都出现的$lo{g}_{2}n$引起了我的注意，它恰是辗转相除法的时间复杂度，为何突然扯到辗转相除法呢？且听我慢慢分析。
 
贪心策略下的剖分
 
狗蔡在ak那场讨论班中给出了一种贪心的办法，即上图(b)中的办法。
 对于这个5x3的矩形，先取一个以短边的正方形，即3x3的正方形，然后一直下去，可以观察发现似乎可以作为一种剖分的办法。
 
做了两三次手动计算后发现，实际上这就是一个辗转相除法，可以说明最后剩下的正方形的边长大小恰好就是$gcd(m,n)$。对于相邻Fibonacci数型的矩形，这样的方法也是很优美的说，如下图所示：
 
 
对于这个8x13的矩形，我们甚至可以从繁分数的角度来一目了然：
 $$\frac{13}{8}=1+\frac{1}{1+\frac{1}{1+\frac{1}{1+\frac{1}{2}}}}$$
 用
    
     
      
       
        F
       
       
        {
       
       
        1
       
       
        ,
       
       
        1
       
       
        ,
       
       
        1
       
       
        ,
       
       
        1
       
       
        ,
       
       
        2
       
       
        }
       
      
      
       F\{1,1,1,1,2\}
      
     
    F{1,1,1,1,2}表示，4个1恰好就是黄、绿、蓝、红四个正方形，最后一个2就是紫色的两个正方形。遗憾的是，这种辗转相除法并不是最优解，因为很快就构造出了反例：
 
 
上面是9x10的矩形，可以发现右边这种辗转大法并不是最优的。但似乎可以证明，斐波那契型的矩形是最优解（具体是否有看到这样的文献不是太记得了ww）
 
"de数"剖分的方法是否唯一？
 
从目前来看，这个问题并不确定，一般情况下，除了对称解外，至今没有找到通用反例。但是对于斐波那契型矩形而言，却很容易构造多解。（利用辗转相除法）
 
好吧还是给出构造吧（如下图所示），注意到由于每次划分的时候，两部分之间都可以对调（如图），而由辗转相除法的复杂度可以估计数量大约有$O(logn)$个，由乘法原理知道，这种情况下。同一个de数有$O(2^{[logn]})=O(n)$种划分。
 
 
矩形的正方形剖分种类是否有限？
 
考虑一个这样的额外问题，一个矩形的正方形剖分的方法的种类是否是有限的呢？辗转相除法是一种通用剖分，直接分为$m\cdot n$个矩形也是一种通用剖分，所以对于一个矩形，它至少有两种方法，那么方法数是否有上界呢？
 
这个问题是和AK在吃饭的时候解决的，当时西园一楼的天花板恰好就是一个一个的小格子，有灯的部分恰好是有小格子的大矩形，恰好可以用来观察。下面这一步思考虽然有冗余，但是恰是思考的过程，我们可以得到：
 $$D_{Square}\le D_{Rectangle}\le D_{Tetris},$$
 其中$D_{Square}，D_{Rectangle}，D_{Tetris}$分别表示正方形剖分种数，矩形剖分种数和俄罗斯方块剖分种数，用$S_{name}$表示他们的剖分方法的集合。其如下图所示：
 
 
上述不等式成立的原因是，显然有$S_{Square}\subseteq S_{Rectangle}\subseteq S_{Tetris}$，所以我们只需要给出$D_{Tetris}$的一个有限上界就可以说明正方形剖分种类是有限的了，实际上这个有限上界并不难给出。
 
考虑一个$m\cdot n$的矩形，可以容易知道它一共有$m(n+1)+n(m+1)$条单位边，其中横向的有$m(n+1)$条，纵向的有$n(m+1)$条。对这些边进行二染色，即要么染色，要么不染色，设这样的处理种数的集合为$S_{bin}$，显然有$S_{Tetris}\subseteq S_{bin}$，于是立马有：
 $$D_{Square}\le D_{Tetris}<D_{bin}=2^{m(n+1)+n(m+1)},$$
 综上所述，正方形剖分种数的有限性得证。
 
数值求解
 
我们不妨回顾一下完全背包问题：
 
 
 
（完全背包问题）有$N$种物品和一个容量为$V$的背包，每种物品都有无限件可用。第$i$种物品的体积是$c_i$，价值是$w_i$。将哪些物品装入背包可使这些物品的体积总和不超过背包容量，且价值总和最大。
 
 
而对于我们的剖分问题而言，我们可以将$m\cdot n$的矩形看成是一个容量为$mn$的背包，有$n$种物品（注意到，不妨设$m\ge n$，那么最大最大的正方形边长为$n$）,那我们可以改写一下完全背包问题：
 
 
 
（矩形最少正方形剖分）有$n$种物品和一个容量为$mn$的背包，每种物品都有无限件可用。第$i$种物品的体积是$c_i^2$，价值是1。将哪些物品装入背包可使这些物品的体积总和等于背包容量，且价值总和最小。
 
 
可以看出，矩形最少正方形剖分问题应该是比完全背包问题要强的，而完全背包问题是NP-complete问题，所以说可以大致估计矩形最少正方形剖分问题也应该是NP-complete问题。所以，本问题不妨从最优化的角度入手。
 
先约定一些符号，下面的模型也可以直接参考论文Minimum Tiling of a Rectangle by Squares：。对矩形建立一个平面直角坐标系，不过不是连续的，而是格点状的，左下角的格子看做为$(0,0)$，
 
 
我们称边长为$k$的正方形占据着坐标$(i,j)$是指，坐标$(i,j)$恰好为正方形$k$的左下角，用$k\in (i,j)$表示。由此定义，我们等会讨论的关注点都在上左下角！（注意辣）。更进一步定义：
 KaTeX parse error: Unknown column alignment: * at position 36: …{\begin{array}{*̲{20}{c}} {1,t \…
 其中，对于一个$MN$的矩形，
    
     
      
       
        t
       
       
        ∈
       
       
        {
       
       
        1
       
       
        ,
       
       
        2
       
       
        ,
       
       
        .
       
       
        .
       
       
        .
       
       
        ,
       
       
        N
       
       
        }
       
      
      
       t \in \{1,2,...,N\}
      
     
    t∈{1,2,...,N},
    
     
      
       
        i
       
       
        ∈
       
       
        
         N
        
        
         t
        
       
       
        =
       
       
        {
       
       
        0
       
       
        ,
       
       
        1
       
       
        ,
       
       
        .
       
       
        .
       
       
        .
       
       
        ,
       
       
        N
       
       
        −
       
       
        t
       
       
        }
       
      
      
       i\in N_t=\{0,1,...,N-t\}
      
     
    i∈Nt​={0,1,...,N−t}以及
    
     
      
       
        j
       
       
        ∈
       
       
        
         M
        
        
         t
        
       
       
        =
       
       
        {
       
       
        0
       
       
        ,
       
       
        1
       
       
        ,
       
       
        .
       
       
        .
       
       
        .
       
       
        ,
       
       
        M
       
       
        −
       
       
        t
       
       
        }
       
      
      
       j\in M_t=\{0,1,...,M-t\}
      
     
    j∈Mt​={0,1,...,M−t}。由此，我们可以建立一个0-1规划的模型：
 KaTeX parse error: Unknown column alignment: * at position 32: … \begin{array}{*̲{20}{c}} {}&{}&…
 优化目标容易理解，而限制条件的目的是使得任意一个坐标$(i,j)$最多只有一个正方形占据（占据是指$k\in (i,j)$），上图(a),(b)给出两种案例给大家理解限制条件中和号的范围取定。（重申一次，我们考察的是正方形的左下角，上图黑框给出左下角的范围）另一方面，限制条件还有一个功能：使得矩形每个位置均在一个正方形内，没有缺漏。（想一想为什么，假设有缺漏，直接以这点为$(i,j)$考虑一下限制条件即可）
 
这个0-1规划问题问题如何求解，额，只能上启发式算法了，特别注意到的是，模型中优化目标有$M{N}^2$个0-1变量，限制条件有大约$O(MN)$个。规模可以说是相当地巨大。
 
这灰常考验计算能力，截止至2016年6月14日，已经在这里公布了380x380以内的矩形的计算结果。同时这里给出了一个在线的可视化结果。
 
下面给出40x40以内的直观结果，$z$轴表示de数，纵横代表$m,n$，其中$m\ge n$所以有一半是没有的，下面给大家欣赏一下：
 
 
一些补充
 
最少正方形剖分的应用
 
最少正方形剖分是有直接的应用的，如有关量子霍尔阵列电阻的文章。
 
猜想1：$de(m,n)=de(km,kn)$
 
其实从上图（右）可以看出很多斜率相同的格点的值是相同的，这个猜想如果成立可以迅速扩大矩形的规模（现在是380x380），另外这个猜想至今没有找到反例。
 
猜想2：若$m\ge n$，那么有$de(m+n,n)=de(m,n)+1$
 
这个稍微画个图大致就会觉得还是蛮有道理的，但是很遗憾的是，在近几年里，这个猜想被推翻，反例是：$de(112,53)=de(59,53)=11$。
 
猜想3：$de(m,n)\sim g(m)=lo{g}_{\varphi }(m\cdot \sqrt{5})$，其中$\varphi =\frac{1+\sqrt{5}}{2}$。
 
上面提到了繁分数，对于Fibonacci型的矩形，如$F_k\cdot F_{k+1}$的矩形，其繁分数对应的数码之和，或者说$de(F_k,F_{k+1})$是满足（应该是成立的，暂时没证明），$de(F_k,F_{k+1})\sim lo{g}_{\varphi }(F_{k+1}\cdot \sqrt{5})$，而对于一般情况我们用程序验证一下$de(m,n)$和$g(m)$的关系，如下图所示：
 
 
可以看出效果还是可以的，“阶”大致吻合。

 
文章目录
 
先修知识: 幂等矩阵
谱分解定理
谱分解的流程
  
谱分解的推论
谱分解的应用

 
先修知识: 幂等矩阵
 
 
谱分解定理
 
 

 
 
 
谱分解的流程
 
 
谱分解的推论
 

 
 
 
谱分解的应用
 

 
 

前言
 
本文主要针对线性代数中的正定矩阵、实对称矩阵、矩阵特征值分解以及矩阵 SVD 分解进行总结。
 
如果你对这篇文章可感兴趣，可以点击「【访客必读 - 指引页】一文囊括主页内所有高质量博客」，查看完整博客分类与对应链接。
 
 
正定矩阵
 
1. 概念
 
首先正定矩阵是定义在对称矩阵的基础上，其次对于任意非零向量 $\text{x}$，若 ${\text{x}}^T\text{A}\text{x}>0$ 恒成立，则矩阵 $\text{A}$ 为正定矩阵；若${\text{x}}^T\text{A}\text{x}\ge 0$ 恒成立，则矩阵 $\text{A}$ 为半正定矩阵。
 
2. 物理意义
 
任意非零向量 $\text{x}$ 经过矩阵 $A$ 线性变换后，与原先向量的夹角 $\le 90$ 度。
 
3. 其他充要条件
 
充要条件1： 矩阵 $\text{A}$ 的全部特征值都是正数 
  
推论： 若 $\text{A}$ 正定，则 $|\text{A}|>0$，即 $\text{A}$ 可逆（有时会根据矩阵正定来判断是否可逆）
推论： 若 $\text{A}$ 正定，则 $\text{A}$ 与单位阵合同，即存在可逆阵 $\text{C}$，使得 ${\text{C}}^T\text{A}\text{C}=\text{E}$ 成立
 
充要条件2： 矩阵 $\text{A}$ 的各阶顺序主子式都是正数，即 ${\Delta }_i>0$ 
  
其中 ${\Delta }_i$ 表示矩阵 $\text{A}$ 前 $i$ 行与前 $i$ 列组成的子矩阵的行列式的值
推论：$|A|>0$ 则 $A$ 一定可逆
 
 
 
实对称矩阵
 
1. 概念
 
矩阵为方阵，其中元素均为实数，且 $\text{A}={\text{A}}^T$。
 
2. 性质
 
性质1： 实对称矩阵的特征值都是实数。 
  
假设 $\lambda$、$\text{x}$ 分别为矩阵 $\text{A}$ 的特征值、特征向量，即 $\text{A}\text{x}=\lambda \text{x}$
等式两边取共轭，即 $\overline{a+bi}=a-bi$，$\overline{\text{A}}\overline{\text{x}}=\overline{\lambda }\overline{\text{x}}$，$\text{A}$ 是实对称矩阵，因此 $\text{A}={\text{A}}^T=\overline{\text{A}}$，即 $\text{A}\overline{\text{x}}=\overline{\lambda }\overline{\text{x}}$
等式两边取转置，则 ${\text{x}}^T\text{A}=\lambda {\text{x}}^T$
${\text{x}}^T\text{A}\overline{x}=\overline{\lambda }{\text{x}}^T\overline{\text{x}}=\lambda {\text{x}}^T\overline{\text{x}}$
$(\lambda -\overline{\lambda }){\Vert \text{x}\Vert }_2^2=0$，由于 ${\Vert \text{x}\Vert }_2^2>0$，因此 $\lambda =\overline{\lambda }$，$\lambda$ 为实数
 
性质2： 实对称矩阵不同特征值所对应的特征向量必定正交。 
  
假设 $\text{A}{\text{x}}_1={\lambda }_1{\text{x}}_1$ 与 $\text{A}{\text{x}}_2={\lambda }_2{\text{x}}_2$ 成立
${\text{x}}_1^T\text{A}={\lambda }_1{\text{x}}_1^T$
${\text{x}}_1^T\text{A}{\text{x}}_2={\lambda }_1{\text{x}}_1^T{\text{x}}_2={\lambda }_2{\text{x}}_1^T{\text{x}}_2$
$({\lambda }_1-{\lambda }_2){\text{x}}_1^T{\text{x}}_2=0$，因此 ${\text{x}}_1$ 与 ${\text{x}}_2$ 正交
 
性质3： 实对称矩阵相同特征值所对应的特征向量必定线性无关。 
  
证明较繁琐，不详细展开
线性无关的向量可以通过施密特正交化转为正交向量 
    
对于线性无关向量组 ${\text{x}}_1,{\text{x}}_2,...,{\text{x}}_n$，转为正交向量组 ${\text{y}}_1,{\text{y}}_2,...,{\text{y}}_n$
${\text{y}}_1={\text{x}}_1$
${\text{y}}_i={\text{x}}_i-\sum _{j=1}^{i-1}\frac{{\text{x}}_i^T{\text{y}}_j}{{\text{y}}_j^T{\text{y}}_j}{\text{y}}_j$
 
由于新的正交向量都是原来线性无关向量的线性组合，而原先的线性无关向量对应的特征值均相同，因此新的正交向量也均为该相同特征值对应的特征向量
 
性质4： 任何一个实对称矩阵，都可以正交对角化。 
  
正交对角化，即存在一个正交矩阵 $\text{Q}({\text{Q}}^T={\text{Q}}^{-1})$ 使得 ${\text{Q}}^T\text{A}\text{Q}=\text{D}$，其中 $\text{D}$ 是一个对角矩阵
实对称矩阵，一定有 $n$ 个解，因为实对称矩阵特征值都是实数，因此一共有 $n$ 个实特征值（包括重特征值）—— 性质 $1$
不同特征值对应的特征向量正交，相同特征值也一定存在对应的正交向量 —— 性质 $2,3$
实对称矩阵，一定有 $n$ 个正交特征向量，因此可以特征值分解，即该性质成立
 
性质5： 实对称矩阵的非零特征值个数等于矩阵的秩 
  
矩阵 $\text{A}$ 相似于对角矩阵，${\text{P}}^{-1}\text{A}\text{P}=\text{D}$
对角矩阵 $\text{D}$ 的秩 = 矩阵 $\text{A}$ 的秩 = $\text{D}$ 非零特征值个数
矩阵 $\text{A}$ 与 矩阵 $\text{D}$ 相似，则特征值相同
 
性质6：实对称矩阵不一定可逆，但若可逆，则一定是实对称矩阵 
  
0 矩阵对称不可逆
$(A^{-1}{)}^T=(A^T{)}^{-1}=A^{-1}$
 
 
 
矩阵特征值分解
 
1. 概念
 
$n\ast n$ 的方阵 $\text{A}$，由 $\text{A}\text{x}=\lambda \text{x}$ 可以得到 $\text{A}\text{V}=\text{V}\Lambda$。
 
如果方阵 $\text{A}$ 有 $n$ 个线性无关的特征向量，则 $\text{V}$ 可逆
$\text{A}=\text{V}\Lambda {\text{V}}^{-1}$
其中矩阵 $\text{V}$ 的列为方阵 $\text{A}$ 的特征向量，$\Lambda =diag({\lambda }_1,{\lambda }_2,...,{\lambda }_n),{\lambda }_i\ge {\lambda }_{i+1}$
 
 
矩阵 SVD 分解
 
1. 概念
 
任意一个矩阵 $\text{A}$ 都可以分解为 $\text{A}=\text{U}\Sigma {\text{V}}^T$，其中 $\text{U},\text{V}$ 均为正交单位矩阵，$\Sigma$ 为对角矩阵。
 
2. 证明
 
${\text{A}}^T\text{A}=(\text{U}\Sigma {\text{V}}^T{)}^T\text{U}\Sigma {\text{V}}^T=\text{V}{\Sigma }^2{\text{V}}^T$，由于 ${\text{A}}^T\text{A}$ 为实对称矩阵，因此 $\text{V}$ 为矩阵 ${\text{A}}^T\text{A}$ 对应特征向量组成的正交单位阵。
$\text{A}{\text{A}}^T=\text{U}\Sigma {\text{V}}^T(\text{U}\Sigma {\text{V}}^T{)}^T=\text{U}{\Sigma }^2{\text{U}}^T$，由于 $\text{A}{\text{A}}^T$ 为实对称矩阵，因此 $\text{U}$ 矩阵 $\text{A}{\text{A}}^T$ 对应特征向量组成的正交单位阵。
$\text{A}\text{V}=\text{U}\Sigma$，其中 $\Sigma$ 为对角阵，因此 $\text{A}{\text{v}}_i={\sigma }_i{\text{u}}_i$，由此可以得到对角矩阵 $\Sigma$，其中 ${\sigma }_i$ 就是奇异值。
${\text{A}}_{m\ast n}={\text{U}}_{m\ast m}{\Sigma }_{m\ast n}{\text{V}}_{n\ast n}^T$
 
3. 几何角度
 
矩阵 $U,V$ 仅负责旋转，$\Sigma$ 负责放缩，具体示意图如下：
 
 
4. SVD 压缩
 
如下所示，仅选取前 $r$ 个不为零的奇异值，可以实现无损压缩。注意非零奇异值的个数等于矩阵 $A$ 的秩。
 
 
5. 计算伪逆
 
 
6. Eckart-Young Theorem
 
如果矩阵 $\mathbf{B}$ 的秩为 $k$，则 $||A-B||\ge ||A-A_k||$ 对如下三个矩阵范数成立：
 
$||A|{|}_2={\sigma }_1$，即最大的奇异值
$||A|{|}_{Nuclear}=\sum _{i=1}^r{\sigma }_i$
Frobenius norm $=||A|{|}_{2,1}=||A|{|}_F=(tr(A^{T}A){)}^{1/2}=(\sum _{i=1}^m\sum _{j=1}^n{a}_{ij}^2{)}^{1/2}$
 
其中 $\mathbf{A}$ 与 ${\mathbf{A}}_{\mathbf{k}}$ 定义如下：
 $$\begin{array}{rl}& \mathbf{A}=\mathbf{U}\Sigma {\mathbf{V}}^T=\sum _{i=1}^r{\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^T\\ & {\mathbf{A}}_k={\mathbf{U}}_k{\Sigma }_k{\mathbf{V}}_k^T=\sum _{i=1}^k{\sigma }_i{\mathbf{u}}_i{\mathbf{v}}_i^T\end{array}$$
 
需要注意，矩阵乘上一个正交矩阵，其奇异值不会发生变化，即上述涉及的矩阵范数不会改变。
 
7. LSI
 
计算不同 $query$ 之间的相似程度，常用于推荐系统。
 
 更多 SVD 的应用：
 
为数据集推荐算法模型
推荐系统、图像去噪等