矩阵的分解：满秩分解和奇异值分解

本文主要介绍矩阵的两种经典的分解算法：满秩分解和奇异值分解。这两块内容非常基础，同时却又非常重要，在机器学习，模式识别，人工智能等领域有着非常广泛的应用。

满秩分解

定义与性质

定义1 满秩分解：对于$m \times n$的矩阵$A$，假设其秩为$r$，若存在秩同样为$r$两个矩阵：$F_{m \times r}$（列满秩）和$G_{r \times n}$（行满秩），使得$A = FG$，则称其为矩阵$A$的满秩分解。

定理1：满秩分解有两个性质，

• 满秩分解不唯一：假设存在$r$阶可逆方阵$D$，则$A = FG = F(DD^{-1})G = (FD)(D^{-1}G) = F'G'$；
  • 任何非零矩阵一定存在满秩分解。证明如下；

  • 假设存在初等变换矩阵$B_{m \times m}$，使得

    BA=(GO)(1) (1) B A = ( G O )

    $$\begin{equation}BA = \left(\begin{array}{c}G\\O\end{array}\right)\end{equation}$$

    其中$G$是个$m \times r$的行满秩矩阵。由上面的公式，可以推出，

    A=B−1(GO)=(F|S)(GO)=FG(2) (2) A = B − 1 ( G O ) = ( F | S ) ( G O ) = F G

    $$\begin{equation}\begin{aligned}A &= B^{-1}\left(\begin{array}{c}G\\O\end{array}\right)\\&= (F|S) \left(\begin{array}{c}G\\O\end{array}\right)\\&= FG\end{aligned}\end{equation}$$

    公式第二行中，我们将$B^{-1}$分块为$(F|S)$，其中$F$为$m \times r$矩阵（秩为$r$），$G$为$r \times n$矩阵（秩为$r$）。

    满秩分解的计算

    如果能理解上面的证明过程，那么计算满秩分解就很容易了，因为方法与证明思路是一致的。

    举个例子来说明，现在要计算下面矩阵$A$的满秩分解：

    A=⎛⎝⎜−1120221−1−221−1⎞⎠⎟(3) (3) A = ( − 1 0 1 2 1 2 − 1 1 2 2 − 2 − 1 )

    $$\begin{equation} A = \left( \begin{array}{cccc} -1 & 0 & 1 & 2 \\ 1 & 2 & -1 & 1 \\ 2 & 2 & -2 & -1 \\ \end{array}\right) \end{equation}$$

    首先，对$A$进行初等变换，得到行满秩矩阵$G$和初等矩阵$B$.

    
    A=⎛⎝⎜⎜−1120221−1−221−1100010001⎞⎠⎟⎟→⎛⎝⎜⎜−10002010023011101−1001⎞⎠⎟⎟(4)
    
    $$\begin{array}{}\text{(4)}& A=\left(\begin{array}{ccccccc}-1& 0& 1& 2& 1& 0& 0\\ 1& 2& -1& 1& 0& 1& 0\\ 2& 2& -2& -1& 0& 0& 1\end{array}\right)\to \left(\begin{array}{ccccccc}-1& 0& 1& 2& 1& 0& 0\\ 0& 2& 0& 3& 1& 1& 0\\ 0& 0& 0& 0& 1& -1& 1\end{array}\right)\end{array}$$

    $$\begin{equation} A = \left( \begin{array}{cccc|ccc} -1 & 0 & 1 & 2 & 1 & 0 & 0 \\ 1 & 2 & -1 & 1 & 0 & 1 & 0 \\ 2 & 2 & -2 & -1 & 0 & 0 & 1 \\ \end{array}\right)\rightarrow\left( \begin{array}{cccc|ccc} -1 & 0 & 1 & 2 & 1 & 0 & 0 \\ 0 & 2 & 0 & 3 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 & 1 & -1 & 1 \\ \end{array}\right)\end{equation}$$

    可见，

    B=⎛⎝⎜11101−1001⎞⎠⎟,G=(−10021023)(5) (5) B = ( 1 0 0 1 1 0 1 − 1 1 ) , G = ( − 1 0 1 2 0 2 0 3 )

    $$\begin{equation} B = \left( \begin{array}{ccc} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & -1 & 1 \\ \end{array}\right),G = \left( \begin{array}{cccc} -1 & 0 & 1 & 2 \\ 0 & 2 & 0 & 3 \\ \end{array}\right) \end{equation}$$

    接着，可以算出

    B−1=⎛⎝⎜1−1−2011001⎞⎠⎟=(F|S)(6) (6) B − 1 = ( 1 0 0 − 1 1 0 − 2 1 1 ) = ( F | S )

    $$\begin{equation} B^{-1} = \left( \begin{array}{ccc} 1 & 0 & 0 \\ -1 & 1 & 0 \\ -2 & 1 & 1 \\ \end{array}\right) = (F|S) \end{equation}$$

    因为$r = 2$，所以可以得到

    F=⎛⎝⎜1−1−2011⎞⎠⎟(7) (7) F = ( 1 0 − 1 1 − 2 1 )

    $$\begin{equation} F = \left( \begin{array}{ccc} 1 & 0 \\ -1 & 1 \\ -2 & 1 \\ \end{array}\right)\end{equation}$$

    因此

    A=FG=⎛⎝⎜1−1−2011⎞⎠⎟⋅(−10021023)(8) (8) A = F G = ( 1 0 − 1 1 − 2 1 ) ⋅ ( − 1 0 1 2 0 2 0 3 )

    $$\begin{equation} A = FG = \left( \begin{array}{ccc} 1 & 0 \\ -1 & 1 \\ -2 & 1 \\ \end{array}\right) \cdot \left( \begin{array}{cccc} -1 & 0 & 1 & 2 \\ 0 & 2 & 0 & 3 \\ \end{array}\right)\end{equation}$$

    另一种计算满秩分解的方法是用矩阵$A$的Hermite标准型。具体做法如下。

    Hermite标准型

    先给出Hermite标准型的定义。

    定义2 Hermite标准型：对于$m \times n$的矩阵$H$，假设其秩为$r$，若$H$满足以下3个条件，则称之为Hermite标准型。

    • $H$的前$r$行中，每行都至少含一个非零元素，且每行的第一个非零元是1，而后$m - r$行都是零元；

    • 假设第$i$行的第一个非零元（就是1）在第$j_i$列，则$j_1 < j_2 < \dots < j_r$；
    • $H$的$j_1, j_2, \dots, j_r$列是单位矩阵$E_m$的前$r$行（这个条件实际上覆盖了前2个条件）；

    由定义可以看出Hermite标准型就是将秩为$r$的$m \times n$矩阵经初等变换而成的阶梯型矩阵。所以也叫做Hermite最简型。

    算出Hermite标准型后，对于矩阵的满秩分解$A = FG$来说，矩阵$F$就是矩阵$A$中$j_1, j_2, \dots, j_r$列构成的$m \times r$矩阵，而$G$则是$H$的前$r$行构成的矩阵。

    还举上面的例子，先变换得到矩阵$A$的Hermite标准型：

    A=⎛⎝⎜−1120221−1−221−1⎞⎠⎟→⎛⎝⎜100010−10023/20⎞⎠⎟=H(9) (9) A = ( − 1 0 1 2 1 2 − 1 1 2 2 − 2 − 1 ) → ( 1 0 − 1 2 0 1 0 3 / 2 0 0 0 0 ) = H

    $$\begin{equation} A = \left( \begin{array}{cccc} -1 & 0 & 1 & 2 \\ 1 & 2 & -1 & 1 \\ 2 & 2 & -2 & -1\\ \end{array}\right)\rightarrow\left( \begin{array}{cccc} 1 & 0 & -1 & 2 \\ 0 & 1 & 0 & 3/2\\ 0 & 0 & 0 & 0 \\ \end{array}\right) = H\end{equation}$$

    $H$前两行第一个非零元所在的列号是1列和2列，所以

    
    
    F=⎛⎝⎜−112022⎞⎠⎟,G=(1001−1023/2)(10)
    
    $$\begin{array}{}\text{(10)}& F=\left(\begin{array}{cc}-1& 0\\ 1& 2\\ 2& 2\end{array}\right),G=\left(\begin{array}{cccc}1& 0& -1& 2\\ 0& 1& 0& 3/2\end{array}\right)\end{array}$$

    $$\begin{equation} F = \left( \begin{array}{cc} -1 & 0 \\ 1 & 2 \\ 2 & 2 \\ \end{array}\right), G = \left( \begin{array}{cccc} 1 & 0 & -1 & 2 \\ 0 & 1 & 0 & 3/2\\\end{array}\right)\end{equation}$$

    特征值分解（EVD）

    特征值分解是对于对称矩阵的一个经典的分解算法，它也是后面我要说的奇异值分解的基础。所以有必要专门列一个小节，大致介绍一下。

    正交矩阵

    在介绍特征值分解之前，先科普一个概念——正交矩阵。

    定义3 正交矩阵：指满足$AA^T = E$的矩阵$A$，其中$E$为单位矩阵。

    正交矩阵是欧式空间的叫法，在酉空间（即复数域上的欧式空间）叫酉矩阵。从定义也能看出正交矩阵有着很多特殊的性质：

    • $A$的各行（列）是单位向量且两两正交；
    • $A$在任意一组标准正交基下对应的线性变换为正交变换（即只旋转向量，却不改变向量之间的夹角和向量长度）
    • $|A| = \pm 1$
    • $A^T = A^{-1}$

    正交阵的概念先摆在这，后面用到我再提。

    特征值与特征向量

    定义4 特征值与特征向量：设$\mathcal{A}$为数域P上的线性空间V的一个线性变换，如果对于P中一数$\lambda_0$，存在非零向量$\xi$，使得下式成立，那么$\lambda_0$称为$\mathcal{A}$的一个特征值，而$\xi$称为$\mathcal{A}$的属于特征值$\lambda_0$的一个特征向量，即

    Aξ=λ0ξ(11) (11) A ξ = λ 0 ξ

    $$\begin{equation}\mathcal{A}\xi = \lambda_0\xi\end{equation}$$

    计算一个线性变换$\mathcal{A}$的特征值与特征向量的方法可以分为以下三步。

    1. 指定线性空间内的一组基，并写出$\mathcal{A}$在这组基下的矩阵$A$；
    2. 求出$A$的特征多项式$|\lambda E - A|$在数域P的全部根（几重根就算几个），这些根就是$\mathcal{A}$的全部特征值；
    3. 把所得的特征值逐个带入$AX = \lambda_iX$，求出关于每个特征值的一组基础解系，也就是全部的线性无关的特征向量；

    我举例解释一下：假设有线性变换$\mathcal{A}$在基$\varepsilon_1, \varepsilon_2, \varepsilon_3$下的矩阵是$A$，现在求它的特征值和特征向量。

    
    
    A=⎛⎝⎜122212221⎞⎠⎟(12)
    
    $$\begin{array}{}\text{(12)}& A=\left(\begin{array}{ccc}1& 2& 2\\ 2& 1& 2\\ 2& 2& 1\end{array}\right)\end{array}$$

    $$\begin{equation} A = \left( \begin{array}{ccc} 1 & 2 & 2\\ 2 & 1 & 2\\ 2 & 2 & 1\\ \end{array}\right)\end{equation}$$

    其特征多项式$|\lambda E - A| = (\lambda + 1)^2 + (\lambda - 5)$，解得$\lambda_1 = -1$（二重），$\lambda_2 = 5$。将$\lambda_1 = -1$代入方程组$AX = -X$，解得基础解系是：

    ⎛⎝⎜10−1⎞⎠⎟,⎛⎝⎜01−1⎞⎠⎟(13) (13) ( 1 0 − 1 ) , ( 0 1 − 1 )

    $$\begin{equation} \left( \begin{array}{c} 1 \\ 0 \\ -1\\ \end{array}\right), \left( \begin{array}{c} 0 \\ 1 \\ -1\\ \end{array}\right) \end{equation}$$

    因此，可以得到属于特征值-1的两个线性无关的特征向量：$\xi_1 = \varepsilon_1 - \varepsilon_3, \xi_2 = \varepsilon_2 - \varepsilon_3$.
    同理，也可以求出属于特征值5的特征向量$\xi_3 = \varepsilon_1 + \varepsilon_2 + \varepsilon_3$.

    了解了特征值和特征向量，可以给出特征子空间和矩阵迹的概念了，如下。

    定义5 特征子空间：我们把属于特征值$\lambda_0$的所有特征向量加上零向量构成的空间称为$\lambda_0$对应的特征子空间（记为$V_{\lambda_0}$），$V_{\lambda_0}$的维数就是属于$\lambda_0$的所有线性无关的特征向量的个数

    定义6 矩阵的迹：矩阵$A$的全体特征值的和为$A$的迹，记为$Tr(A)$。实际上，通过证明我们还可以知道$Tr(A)$也等于$A$的主对角线上所有元素的和，即$Tr(A) = a_{11} + a_{22} + \dots + a_{nn}$。

    下面我再补充一个重要的概念——相似矩阵。

    相似矩阵

    定义7 相似矩阵：$A, B$为两个$n$阶矩阵，如果存在$n$阶矩阵$X$使得$B = X^{-1}AX$成立，则$A, B$被称为是相似的，记为$A$~$B$。

    上面说到每一个线性变换在不同基下对应着不同的矩阵，那这些矩阵有什么关系呢？有如下定理：

    定理2：线性变换在不同的基下所对应的矩阵是相似的，反之，若两个矩阵相似，则它们可以被看作是同一个线性变换在不同基下的矩阵。

    理解了相似矩阵的概念，我们接着探究相似矩阵与特征多项式的关系，有如下定理：

    定理3：相似的矩阵有相同的特征多项式。证明如下，

    我们知道，若$A$~$B$，则有可逆矩阵$X$，使得$B = X^{-1}AX$，那可以做出如下的推导：

    |λE−B|=|λE−X−1AX|=|X−1(λE−A)X|=|X−1||λE−A||X|=|λE−A|(14) (14) | λ E − B | = | λ E − X − 1 A X | = | X − 1 ( λ E − A ) X | = | X − 1 | | λ E − A | | X | = | λ E − A |

    $$\begin{equation} \begin{aligned}|\lambda E - B| &= |\lambda E - X^{-1}AX|\\& = |X^{-1}(\lambda E - A)X|\\& = |X^{-1}||\lambda E - A||X|\\& = |\lambda E - A|\end{aligned}\end{equation}$$

    根据定理2，我们知道，同一个线性变换在不同的基下所对应的矩阵是相似的，而定理3告诉我们相似的矩阵有相同的特征多项式，那也就说明了一个问题：即线性变换矩阵的特征多项式与选择的基是无关的。

    对角矩阵

    对角矩阵即除了主对角线中的元素外，其他元素都为0的矩阵。对角矩阵和线性变换的结合非常紧密，有如下定理存在：

    定理4：线性变换$\mathcal{A}$在某一组基下式对角矩阵的充要条件是，$\mathcal{A}$有$n$个线性无关的特征向量。

    定理5：属于不同特征值的特征向量是线性无关的。

    特征值分解的计算

    我们知道对于一个$n \times n$的对称矩阵$A$来说（即$A^T = A$），它与对角矩阵是相似的（证明我略了），那他可以被看作是一个对角阵对应的线性变换$\mathcal{A}$在另一组基下的矩阵，因为对角阵有$n$个线性无关的特征向量，而属于不同特征值的特征向量是线性无关的，所以我们说对称阵$A$一定有$n$个特征值（重根算多个）。

    综上，可以得到：

    
    
    AX1AX2AXn=λ1X1=λ1X2…=λ1Xn(31)
    
    $$\begin{array}{}\text{(31)}& \begin{array}{rl}A{X}_1& ={\lambda }_1{X}_1\\ A{X}_2& ={\lambda }_1{X}_2\\ & \dots \\ A{X}_n& ={\lambda }_1{X}_n\end{array}\end{array}$$

    $$\begin{equation} \begin{aligned}AX_1 &= \lambda_1X_1\\AX_2 &= \lambda_1X_2\\&\dots\\AX_n &= \lambda_1X_n\\\end{aligned}\end{equation}$$

    化简一下，上式可以写成：$AU = U\Lambda$，其中$U = (X_1, X_2, \dots, X_n)$，

    Λ=⎛⎝⎜⎜⎜⎜⎜λ10⋮00λ2⋮0……⋱…00⋮λn⎞⎠⎟⎟⎟⎟⎟(16) (16) Λ = ( λ 1 0 … 0 0 λ 2 … 0 ⋮ ⋮ ⋱ ⋮ 0 0 … λ n )

    $$\begin{equation}\Lambda = \left( \begin{array}{cccc} \lambda_1 & 0 & \dots & 0 \\ 0 & \lambda_2 & \dots & 0 \\ \vdots &\vdots & \ddots& \vdots \\ 0 & 0 & \dots & \lambda_n\\ \end{array}\right)\end{equation}$$

    因为对称阵有一个性质：不同特征值对应的特征向量两两正交。所以此处$U$即为正交阵（正交阵的概念上面说了，至于正交阵的每一列是单位向量的问题，你对特征值做处理就完了）。

    综上，一个对称阵的特征值分解可以写成：$A = U\Lambda U^{-1} = U\Lambda U^T$，其中$U$是正交矩阵，每个列向量有$A$对应的归一化的特征向量构成。

    现在对于任意的$n$维向量$Y$来说，可以通过矩阵$A$实现相应的线性变换。

    
    
    AY=UΛUTY(17)
    
    $$\begin{array}{}\text{(17)}& AY=U\mathrm{\Lambda }{U}^{T}Y\end{array}$$

    $$\begin{equation} AY = U\Lambda U^TY\end{equation}$$

    其中$U^TY$相当于是对$Y$做了一个正交变换。根据前面介绍的正交变换相关知识，正交变换相当于是对向量$Y$换了一个坐标系，而新坐标系的基就是$A$的所有特征向量（即$U$的所有列向量），因此，$U^TY = (a_1, \dots, a_n)$，$a_1, \dots, a_n$相当于是$Y$在新坐标系下的坐标.

    继续化简上面的公式，

    
    
    AY=UΛUTY=UΛ(a1,…,an)=U⎛⎝⎜⎜⎜⎜⎜λ10⋮00λ2⋮0……⋱…00⋮λn⎞⎠⎟⎟⎟⎟⎟(a1,…,an)=U⎛⎝⎜⎜⎜⎜λ1a1λ2a2⋮λ1a1⎞⎠⎟⎟⎟⎟(18)
    
    $$\begin{array}{}\text{(18)}& AY=U\mathrm{\Lambda }{U}^{T}Y=U\mathrm{\Lambda }(a_1,\dots ,a_n)=U\left(\begin{array}{cccc}{\lambda }_1& 0& \dots & 0\\ 0& {\lambda }_2& \dots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \dots & {\lambda }_n\end{array}\right)(a_1,\dots ,a_n)=U\left(\begin{array}{c}{\lambda }_1{a}_1\\ {\lambda }_2{a}_2\\ ⋮\\ {\lambda }_1{a}_1\end{array}\right)\end{array}$$

    $$\begin{equation}AY = U\Lambda U^TY = U\Lambda (a_1, \dots, a_n) = U \left( \begin{array}{cccc} \lambda_1 & 0 & \dots & 0 \\ 0 & \lambda_2 & \dots & 0 \\ \vdots &\vdots & \ddots& \vdots \\ 0 & 0 & \dots & \lambda_n\\ \end{array}\right) (a_1, \dots, a_n) = U \left( \begin{array}{c} \lambda_1a_1\\ \lambda_2a_2\\ \vdots\\ \lambda_1a_1\\ \end{array}\right)\end{equation}$$

    $\lambda_ia_i$相当于是对向量$y$在新的坐标系下沿对应的轴方向进行了拉伸或者压缩，并没有改变向量实际的方向，最后再左乘$U$相当于对当前的向量再次进行正交变换，因为$U$是$U^T$的逆矩阵，所以这是一个与$U^T$的变换相反的变换。综上，对阵矩阵$A$所对应的变换实际上可以将一组正交基映射为另一组正交基。

    奇异值分解（SVD）

    奇异值

    上面说了一大推，其实就是介绍了对阵矩阵的一个性质：即把一组正交基映射为另一组正交基。对于任意的$m \times n$的矩阵$A$，$A$可以将$n$维空间中的向量映射到$k$维空间中（$k \leq m$），那么现在来探究能否找到这样一组$n$维正交基，使之经过$A$的变换后，还是正交基。寻找这样正交基的过程，就是SVD的核心思路。

    好了，先假设存在这样的正交基$(V_1, V_2, \dots, V_n)$，$|V_i| = 1$，经过$A$映射后变为$(AV_1, AV_2, \dots, AV_n)$（实际上，这里的$AV_i$都是$m$维向量）。既然他们两两正交，那么就得满足下面的公式。

    
    
    (AVi)(AVj)=(AVi)T⋅AVj=VTi(ATA)Vj=0(19)
    
    $$\begin{array}{}\text{(19)}& (A{V}_i)(A{V}_j)=(A{V}_i{)}^T\cdot A{V}_j=V_i^T(A^{T}A)V_j=0\end{array}$$

    $$\begin{equation} (AV_i)(AV_j) = (AV_i)^T \cdot AV_j = V_i^T (A^TA) V_j = 0\end{equation}$$

    现在来证明这个公式是成立的（成立的话表示正交基找到了）。因为我在假设中，设置的$(V_1, V_2, \dots, V_n)$是一组正交基，所以，$V_i^TV_j = 0$。我把这个结论先放这（下面的公式要用）。接着想，现在$A^TA$是个$n \times n$的对称矩阵。因为对称矩阵一定有$n$个特征值，其特征向量两两正交，那我就假设$(V_1, V_2, \dots, V_n)$是$A^TA$的特征向量，可以得到

    VTi(ATA)Vj=VTiλjVj=λjVTiVj=0(20) (20) V i T ( A T A ) V j = V i T λ j V j = λ j V i T V j = 0

    $$\begin{equation} V_i^T (A^TA) V_j = V_i^T \lambda_jV_j = \lambda_j V_i^T V_j = 0\end{equation}$$

    这样我就证明了$(AV_1, AV_2, \dots, AV_n)$是一组正交向量。再对这组正交向量做归一化处理，构成一组新的正交基。先计算每个$AV_i$的模数：

    |AVi|2=λiVTiVi=λi(21) (21) | A V i | 2 = λ i V i T V i = λ i

    $$\begin{equation} |AV_i|^2 = \lambda_i V_i^TV_i = \lambda_i\end{equation}$$

    取单位向量后，得到$u_i = \frac{1}{\sqrt{\lambda_i}}AV_i$，其中$\sigma_i = \sqrt{\lambda_i}$被称为是矩阵$A$的奇异值，它实际上就是对称阵$A^TA$的特征值的算数平方根。而$(u_1, \dots, u_n)$则是一组经过归一化处理的，两两正交的$m$维向量的集合，在这个集合当中，我们当然可以找到一组$k$维空间的正交基（$k \leq m, k \leq n$）。

    上一段的最后一句话可以这样理解：假设$m = 3, k = 2, n = 3$，$u_1 = (1, 0, 0), u_2 = (0, 1, 0), u_3 = (0, 0, 0)$，$u_1, u_2, u_3$两两正交，我们自然可以找到$k = 2$维空间的正交基：$u_1' = (1, 0), u_2' = (0, 1)$

    分解过程

    上面得到的正交基对我们非常重要，它可以用来做奇异值分解。我们先明确这样一个关系：$\sigma_i u_i' = AV_i, i \in \{1, \dots, k\}$，现在我做如下两组正交基的拓展工作：

    • 生成$(u_1', \dots, u_m')$。它是由$(u_1', \dots, u_k')$拓展生成的$m$维空间的正交基
    • 已知$(V_1, \dots, V_n)$是$n$维空间中一组两两正交的向量，其中，$(V_{k + 1}, \dots, V_n)$使得$AV_i = 0, i \in \{k + 1, \dots, n\}$

    那么，有下面的公式成立：

    A(V1,…,Vk|Vk+1,…,Vn)=(AV1,…,AVk|O,…,O)=(u′1,…,u′k|u′k+1,…,u′m)⎛⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜σ1−⋱−Oσk−−O−O−⎞⎠⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟(22) (22) A ( V 1 , … , V k | V k + 1 , … , V n ) = ( A V 1 , … , A V k | O , … , O ) = ( u 1 ′ , … , u k ′ | u k + 1 ′ , … , u m ′ ) ( σ 1 ⋱ O σ k − − − − − − O O )

    $$\begin{equation} A(V_1, \dots, V_k|V_{k + 1}, \dots, V_n) = (AV_1, \dots, AV_k|O, \dots, O) = (u_1', \dots, u_k'|u_{k + 1}', \dots, u_m') \left(\begin{array}{ccc|ccc} \sigma_1 & & & & & \\ & \ddots & & & O & \\ & & \sigma_k & & & \\ - & - & - & - & - & -\\ & & & & & \\ & O & & & O & \\ & & & & & \\ \end{array}\right)\end{equation}$$

    继而可以得到奇异值分解的公式：
    

    A=UΣVT=(u′1,…,u′m)⋅⎛⎝⎜⎜⎜⎜⎜σ1⋱σkO⎞⎠⎟⎟⎟⎟⎟⋅⎛⎝⎜⎜V1⋮Vn⎞⎠⎟⎟(23) (23) A = U Σ V T = ( u 1 ′ , … , u m ′ ) ⋅ ( σ 1 ⋱ σ k O ) ⋅ ( V 1 ⋮ V n )

    $$\begin{equation}A = U\Sigma V^T = (u_1', \dots, u_m') \cdot \left(\begin{array}{ccc} \sigma_1 & & & \\ & \ddots & & \\ & & \sigma_k &\\ & & & O \end{array}\right) \cdot\left(\begin{array}{c} V_1 \\\vdots \\V_n \\ \end{array}\right)\end{equation}$$

    其中$U$是$m \times m$的正交阵，$\Sigma$是$m \times n$的对角阵，$V$是$n \times n$的正交阵。

    更具体地说，$U$是由$A^TA$的特征向量经过$A$变换而来的标准化的$m \times m$正交阵，$\Sigma$是由矩阵$A^TA$的特征值构成的的算数平方根构成的$m \times n$的对角阵（秩为$k$），$V$是由$A^TA$的特征向量构成的$n \times n$的正交阵。

    计算实例

    我举个例子，看看SVD到底是如何计算的。现在分解矩阵

    A=⎛⎝⎜011110⎞⎠⎟(24) (24) A = ( 0 1 1 1 1 0 )

    $$\begin{equation} A= \left(\begin{array}{cc} 0 & 1\\ 1 & 1\\ 1 & 0 \end{array}\right)\end{equation}$$

    根据$A$，可知参数$m = 3, n = 2, k = 2$.

    先计算$A^TA$的特征值和对应的特征向量：

    λ1=3,V1=⎛⎝12√12√⎞⎠,λ2=1,V2=⎛⎝−12√12√⎞⎠(25) (25) λ 1 = 3 , V 1 = ( 1 2 1 2 ) , λ 2 = 1 , V 2 = ( − 1 2 1 2 )

    $$\begin{equation} \lambda_1 = 3, V_1 = \left(\begin{array}{c} \frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\\ \end{array}\right),\lambda_2 = 1, V_2 = \left(\begin{array}{c} -\frac{1}{\sqrt{2}}\\ \frac{1}{\sqrt{2}}\\ \end{array}\right)\end{equation}$$

    根据上面的分析，这里$V_1, V_2$构成了奇异值分解中的矩阵$V$；

    再计算奇异值，也就是$A^TA$的特征值，解得$\lambda_1 = 3, \lambda_2 = 1, \lambda_3 = 0$。其中$\sqrt{\lambda_1}, \sqrt{\lambda_2}$构成了对角矩阵主对角线上的元素。

    最后计算$V_1, V_2$经过$A$变换后的向量。当然，此时只有$k = 2$个$m$维向量，而我们需要$m$个$m$维向量去构造矩阵$U$，你可以计算$AV_i$，然后再使用正交基的扩充方法，但是有点复杂，一种更简单的思路是，既然$AA^T$是$m \times m$对称阵，而$u_1', \dots, u_m'$是$AA^T$的特征向量，所以直接计算$AA^T$的特征向量，再做归一化处理即可：

    u1=⎛⎝⎜⎜⎜16√26√16√⎞⎠⎟⎟⎟,u2=⎛⎝⎜⎜⎜12√0−12√⎞⎠⎟⎟⎟,u3=⎛⎝⎜⎜⎜13√−13√13√⎞⎠⎟⎟⎟(26) (26) u 1 = ( 1 6 2 6 1 6 ) , u 2 = ( 1 2 0 − 1 2 ) , u 3 = ( 1 3 − 1 3 1 3 )

    $$\begin{equation} u_1 = \left(\begin{array}{c} \frac{1}{\sqrt{6}}\\ \frac{2}{\sqrt{6}}\\ \frac{1}{\sqrt{6}}\\ \end{array}\right),u_2 = \left(\begin{array}{c} \frac{1}{\sqrt{2}}\\ 0\\ -\frac{1}{\sqrt{2}}\\ \end{array}\right),u_3 = \left(\begin{array}{c} \frac{1}{\sqrt{3}}\\ -\frac{1}{\sqrt{3}}\\ \frac{1}{\sqrt{3}}\\ \end{array}\right)\end{equation}$$

    $u_1, u_2, u_3$构成了奇异值分解中的矩阵$U$.

    综上，矩阵$A$被如下分解：

    A=⎛⎝⎜⎜⎜16√26√16√12√0−12√13√−13√13√⎞⎠⎟⎟⎟⎛⎝⎜3–√00010⎞⎠⎟⎛⎝12√−12√12√12√⎞⎠(27) (27) A = ( 1 6 1 2 1 3 2 6 0 − 1 3 1 6 − 1 2 1 3 ) ( 3 0 0 1 0 0 ) ( 1 2 1 2 − 1 2 1 2 )

    $$\begin{equation} A = \left(\begin{array}{ccc} \frac{1}{\sqrt{6}} & \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{3}}\\ \frac{2}{\sqrt{6}} & 0 & -\frac{1}{\sqrt{3}}\\ \frac{1}{\sqrt{6}} & -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{3}}\\ \end{array}\right) \left(\begin{array}{cc} \sqrt{3} & 0\\ 0 & 1\\ 0 & 0\\ \end{array}\right) \left(\begin{array}{cc} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\ -\frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}}\\ \end{array}\right) \end{equation}$$

    结论：最后再把奇异值分解总结一下，任意$m \times n$矩阵$A$，可以被分解为$A = U \Sigma V^T$，其中，

    • $U$：$m \times m$矩阵，每个列向量由对称阵$AA^T$的特征向量构成；
    • $\Sigma$：$m \times n$对角阵，秩为$k$，主对角线上每个元素是对称阵$A^TA$的非零特征值的算数平方根；
    • $V$：$n \times n$矩阵，每个列向量由对称阵$A^TA$的特征向量构成；

    参考文献如下：

    奇异值分解(SVD)原理详解及推导
    矩阵的满秩分解

今天的文章矩阵的分解：满秩分解和奇异值分解分享到此就结束了，感谢您的阅读。