【李航】统计学习方法--15. 奇异值分解(详细推导)

【李航】统计学习方法--15. 奇异值分解(详细推导)

文章目录

  • 奇异值分解(singular value decomposition, SVD)是一种矩阵因子分解方法,是线性代数的概念
  • 任意一个mxn矩阵,都可以表示为三个矩阵的乘积(因子分解)形式,分别是n阶正交矩阵、由降序排列的非负的对角线元素组成的mxn矩形对角矩阵n阶正交矩阵,称为该矩阵的奇异值分解。
  • 矩阵的奇异值分解一定存在,但不唯一。
  • 奇异值分解可以看作是矩阵数据压缩的一种方法,即用因子分解的方式近似地表示原始矩阵,这种近似是在平方损失意义下的最优近似。

15.1 奇异值分解的定义与性质


15.1.1 定义与定理


定义 15.1 15.1 15.1 (奇异值分解) 矩阵的奇异值分解是指, 将一个非零的 m × n m \times n m×n 实矩阵 A A A, A ∈ R m × n A \in \mathbf{R}^{m \times n} A∈Rm×n, 表示为以下三个实矩阵乘积形式的运算 , 即进行矩阵的因子分解:

A = U Σ V T A=U \Sigma V^{\mathrm{T}} A=UΣVT

其中 U U U 是 m m m 阶正交矩阵 ( orthogonal matrix ), V V V 是 n n n 阶正交矩阵, Σ \Sigma Σ 是由降序排列的非负的对角线元素组成的 m × n m \times n m×n 矩形对角矩阵 ( rectangular diagonal matrix ), 满足

U U T = I V V T = I Σ = diag ⁡ ( σ 1 , σ 2 , ⋯   , σ p ) σ 1 ⩾ σ 2 ⩾ ⋯ ⩾ σ p ⩾ 0 p = min ⁡ ( m , n ) \begin{array}{l} U U^{\mathrm{T}}=I \\ V V^{\mathrm{T}}=I \\ \Sigma=\operatorname{diag}\left(\sigma_{1}, \sigma_{2}, \cdots, \sigma_{p}\right) \\ \sigma_{1} \geqslant \sigma_{2} \geqslant \cdots \geqslant \sigma_{p} \geqslant 0 \\ p=\min (m, n) \end{array} UUT=IVVT=IΣ=diag(σ1​,σ2​,⋯,σp​)σ1​⩾σ2​⩾⋯⩾σp​⩾0p=min(m,n)​

U Σ V T U \Sigma V^{\mathrm{T}} UΣVT 称为矩阵 A A A 的奇异值分解( singular value decomposition, S V D ) , σ i \left.\mathrm{SVD}\right), \sigma_{i} SVD),σi​ 称为矩阵 A A A 的奇异值 ( singular value ), U U U 的列向量称为左奇异向量 ( left singular vector ), V V V
的列向量称为右奇异向量 ( right singular vector)。

注意:奇异值分解不要求矩阵 A A A 是方阵

定理 15.1 15.1 15.1 (奇异值分解基本定理) 若 A A A 为一 m × n m \times n m×n 实矩阵, A ∈ R m × n A \in \mathbf{R}^{m \times n} A∈Rm×n, 则 A A A
的奇异值分解存在

A = U Σ V T A=U \Sigma V^{\mathrm{T}} A=UΣVT

其中 U U U 是 m m m 阶正交矩阵, V V V 是 n n n 阶正交矩阵, Σ \Sigma Σ 是 m × n m \times n m×n 矩形对角矩阵, 其对角线 元素非负,且按降序排列。

证明 证明是构造性的, 对给定的矩阵 A A A, 构造出其奇异值分解的各个矩阵。为 了方便, 不妨假设 m ⩾ n m \geqslant n m⩾n, 如果 m < n m<n m<n 证明仍然成立。证明由三步完成。

  1. 确定 V V V 和 Σ \Sigma Σ
    首先构造 n n n 阶正交实矩阵 V V V 和 m × n m \times n m×n 矩形对角实矩阵 Σ \Sigma Σ 。
    矩阵 A A A 是 m × n m \times n m×n 实矩阵, 则矩阵 A T A A^{\mathrm{T}} A ATA 是 n n n 阶实对称矩阵。因而 A T A A^{\mathrm{T}} A ATA 的特征值都是实数, 并且存在一个 n n n 阶正交实矩阵 V V V 实现 A T A A^{\mathrm{T}} A ATA 的对角化, 使得 V T ( A T A ) V = Λ V^{\mathrm{T}}\left(A^{\mathrm{T}} A\right) V=\Lambda VT(ATA)V=Λ 成立, 其中 Λ \Lambda Λ 是 n n n 阶对角矩阵, 其对角线元素由 A T A A^{\mathrm{T}} A ATA 的特征值组成。

    证明: A T A A^TA ATA是实对称矩阵
    ​ ( A T A ) T = A T ( A T ) T = A T A (A^TA)^T=A^T(A^T)^T=A^{\mathrm{T}} A (ATA)T=AT(AT)T=ATA

    一个n*n矩阵A可正交对角化的充要条件是A是对称矩阵

    A T A = V Λ V − 1 = = > V − 1 A T A V = V − 1 V Λ V − 1 V = = > V − 1 A T A V = Λ = = > V T A T A V = Λ A^TA=V\Lambda V^{-1}==>V^{-1}A^TAV=V^{-1}V\Lambda V^{-1}V==>V^{-1}A^TAV=\Lambda==>V^{T}A^TAV=\Lambda ATA=VΛV−1==>V−1ATAV=V−1VΛV−1V==>V−1ATAV=Λ==>VTATAV=Λ

    而且, A T A A^{\mathrm{T}} A ATA 的特征值都是非负的。事实上, 令 λ \lambda λ 是 A T A A^{\mathrm{T}} A ATA 的一个特征值, x x x 是对 应的特征向量, 则
    ∥ A x ∥ 2 = ( A x ) T A x = x T A T A x = λ x T x = λ ∥ x ∥ 2 \|A x\|^{2}=(Ax)^TAx=x^{\mathrm{T}} A^{\mathrm{T}} A x=\lambda x^{\mathrm{T}} x=\lambda\|x\|^{2} ∥Ax∥2=(Ax)TAx=xTATAx=λxTx=λ∥x∥2

    向量的长度(范数)是非负数 ∥ v ∥ \|\boldsymbol{v}\| ∥v∥,定义为

    ∥ v ∥ = v ⋅ v = v 1 2 + v 2 2 + ⋯ + v n 2  且  ∥ v ∥ 2 = v ⋅ v \|\boldsymbol{v}\|=\sqrt{\boldsymbol{v} \cdot \boldsymbol{v}}=\sqrt{v_{1}^{2}+v_{2}^{2}+\cdots+v_{n}^{2}} \quad \text { 且 }\|\boldsymbol{v}\|^{2}=\boldsymbol{v} \cdot \boldsymbol{v} ∥v∥=v⋅v ​=v12​+v22​+⋯+vn2​ ​ 且 ∥v∥2=v⋅v

    而 ∥ v ∥ 2 = v ⋅ v = v T v \|\boldsymbol{v}\|^{2}=\boldsymbol{v} \cdot \boldsymbol{v}=\boldsymbol{v}^T \boldsymbol{v} ∥v∥2=v⋅v=vTv

    A T A x = λ x A^TAx=\lambda x ATAx=λx

    于是
    λ = ∥ A x ∥ 2 ∥ x ∥ 2 ⩾ 0 \lambda=\frac{\|A x\|^{2}}{\|x\|^{2}} \geqslant 0 λ=∥x∥2∥Ax∥2​⩾0

    可以假设正交矩阵 V V V 的列的排列使得对应的特征值形成降序排列
    λ 1 ⩾ λ 2 ⩾ ⋯ ⩾ λ n ⩾ 0 \lambda_{1} \geqslant \lambda_{2} \geqslant \cdots \geqslant \lambda_{n} \geqslant 0 λ1​⩾λ2​⩾⋯⩾λn​⩾0

    计算特征值的平方根 (实际就是矩阵 A A A 的奇异值)
    σ j = λ j , j = 1 , 2 , ⋯   , n \sigma_{j}=\sqrt{\lambda_{j}}, \quad j=1,2, \cdots, n σj​=λj​ ​,j=1,2,⋯,n

    设矩阵 A A A 的秩是 r , rank ⁡ ( A ) = r r, \operatorname{rank}(A)=r r,rank(A)=r, 则矩阵 A T A A^{\mathrm{T}} A ATA 的秩也是 r r r 。由于 A T A A^{\mathrm{T}} A ATA 是对称矩阵, 它的秩等于正的特征值的个数, 所以
    λ 1 ⩾ λ 2 ⩾ ⋯ ⩾ λ r > 0 , λ r + 1 = λ r + 2 = ⋯ = λ n = 0 \lambda_{1} \geqslant \lambda_{2} \geqslant \cdots \geqslant \lambda_{r}>0, \quad \lambda_{r+1}=\lambda_{r+2}=\cdots=\lambda_{n}=0 λ1​⩾λ2​⩾⋯⩾λr​>0,λr+1​=λr+2​=⋯=λn​=0

    对应地有
    σ 1 ⩾ σ 2 ⩾ ⋯ ⩾ σ r > 0 , σ r + 1 = σ r + 2 = ⋯ = σ n = 0 \sigma_{1} \geqslant \sigma_{2} \geqslant \cdots \geqslant \sigma_{r}>0, \quad \sigma_{r+1}=\sigma_{r+2}=\cdots=\sigma_{n}=0 σ1​⩾σ2​⩾⋯⩾σr​>0,σr+1​=σr+2​=⋯=σn​=0


    V 1 = [ ν 1 ν 2 ⋯ ν r ] , V 2 = [ ν r + 1 ν r + 2 ⋯ ν n ] . V_{1}=\left[\begin{array}{llll} \nu_{1} & \nu_{2} & \cdots & \left.\nu_{r}\right], \quad V_{2}=\left[\nu_{r+1}\right. & \nu_{r+2} & \cdots & \nu_{n} \end{array}\right]. V1​=[ν1​​ν2​​⋯​νr​],V2​=[νr+1​​νr+2​​⋯​νn​​].

    其中 ν 1 , ⋯   , ν r \nu_{1}, \cdots, \nu_{r} ν1​,⋯,νr​ 为 A T A A^{\mathrm{T}} A ATA 的正特征值对应的特征向量, ν r + 1 , ⋯   , ν n \nu_{r+1}, \cdots, \nu_{n} νr+1​,⋯,νn​ 为 0 特征值对应的 特征向量, 则
    V = [ V 1 V 2 ] V=\left[\begin{array}{ll} V_{1} & V_{2} \end{array}\right] V=[V1​​V2​​]

    这就是矩阵 A A A 的奇异值分解中的 n n n 阶正交矩阵 V 。  V_{\text {。 }} V。 ​

    Σ 1 = [ σ 1 σ 2 ⋱ σ r ] \Sigma_{1}=\left[\begin{array}{cccc} \sigma_{1} & & & \\ & \sigma_{2} & & \\ & & \ddots & \\ & & & \sigma_{r} \end{array}\right] Σ1​=⎣⎢⎢⎡​σ1​​σ2​​⋱​σr​​⎦⎥⎥⎤​

    则 Σ 1 \Sigma_{1} Σ1​ 是一个 r r r 阶对角矩阵, 其对角线元素为按降序排列的正的 σ 1 , ⋯   , σ r \sigma_{1}, \cdots, \sigma_{r} σ1​,⋯,σr​, 于是 m × n m \times n m×n 矩形对角矩阵 Σ \Sigma Σ 可以表为
    Σ = [ Σ 1 0 0 0 ] \Sigma=\left[\begin{array}{cc} \Sigma_{1} & 0 \\ 0 & 0 \end{array}\right] Σ=[Σ1​0​00​]

    这就是矩阵 A A A 的奇异值分解中的 m × n m \times n m×n 矩形对角矩阵 Σ 。  \Sigma_{\text {。 }} Σ。 ​

    下面推出后面要用到的一个公式。在式 V = [ V 1 a m p ; V 2 ] V=\left[\begin{array}{ll}V_{1} &amp; V_{2}\end{array}\right] V=[V1​​amp;V2​​]中, V 2 V_{2} V2​ 的列向量是 A T A A^{\mathrm{T}} A ATA 对应于特征值为 0 的特征向量。因此

    A T A v j = 0 , j = r + 1 , ⋯   , n A^{\mathrm{T}} A v_{j}=0, \quad j=r+1, \cdots, n ATAvj​=0,j=r+1,⋯,n

    于是, V 2 V_{2} V2​ 的列向量构成了 A T A A^{\mathrm{T}} A ATA 的零空间 N ( A T A ) N\left(A^{\mathrm{T}} A\right) N(ATA), 而 N ( A T A ) = N ( A ) N\left(A^{\mathrm{T}} A\right)=N(A) N(ATA)=N(A) 。所以 V 2 V_{2} V2​ 的 列向量构成 A A A 的零空间的一组标准正交基。因此,

    A V 2 = 0 A V_{2}=0 AV2​=0

    由于 V V V 是正交矩阵, 由式 V = [ V 1 a m p ; V 2 ] V=\left[\begin{array}{ll}V_{1} &amp; V_{2}\end{array}\right] V=[V1​​amp;V2​​]可得

    I = V V T = V 1 V 1 T + V 2 V 2 T A = A I = A V 1 V 1 T + A V 2 V 2 T = A V 1 V 1 T \begin{gathered} I=V V^{\mathrm{T}}=V_{1} V_{1}^{\mathrm{T}}+V_{2} V_{2}^{\mathrm{T}} \\ A=A I=A V_{1} V_{1}^{\mathrm{T}}+A V_{2} V_{2}^{\mathrm{T}}=A V_{1} V_{1}^{\mathrm{T}} \end{gathered} I=VVT=V1​V1T​+V2​V2T​A=AI=AV1​V1T​+AV2​V2T​=AV1​V1T​​

  2. 确定 U U U
    接着构造 m m m 阶正交实矩阵 U U U 。

    u j = 1 σ j A v j , j = 1 , 2 , ⋯   , r ① U 1 = [ u 1 u 2 ⋯ u r ] \begin{gathered} u_{j}=\frac{1}{\sigma_{j}} A v_{j}, \quad j=1,2, \cdots, r① \\ U_{1}=\left[\begin{array}{llll} u_{1} & u_{2} & \cdots & u_{r} \end{array}\right] \end{gathered} uj​=σj​1​Avj​,j=1,2,⋯,r①U1​=[u1​​u2​​⋯​ur​​]​

    则有
    A V 1 = U 1 Σ 1 A V_{1}=U_{1} \Sigma_{1} AV1​=U1​Σ1​

    A V 1 = A [ ν 1 ν 2 ⋯ ν r ] = [ u 1 u 2 ⋯ u r ] [ σ 1 σ 2 ⋱ σ r ] = U 1 Σ 1 A V_{1}=A\left[\begin{array}{llll} \nu_{1} & \nu_{2} & \cdots & \left.\nu_{r}\right] \end{array}\right.=\left[\begin{array}{llll} u_{1} & u_{2} & \cdots & u_{r} \end{array}\right]\left[\begin{array}{cccc} \sigma_{1} & & & \\ & \sigma_{2} & & \\ & & \ddots & \\ & & & \sigma_{r} \end{array}\right]= U_{1} \Sigma_{1} AV1​=A[ν1​​ν2​​⋯​νr​]​=[u1​​u2​​⋯​ur​​]⎣⎢⎢⎡​σ1​​σ2​​⋱​σr​​⎦⎥⎥⎤​=U1​Σ1​

    U 1 U_{1} U1​ 的列向量构成了一组标准正交集, 因为
    u i T u j = ( 1 σ i v i T A T ) ( 1 σ j A v j ) = 1 σ i σ j v i T ( A T A v j ) = 1 σ i σ j v i T ( σ j 2 v j ) = σ j σ i v i T v j = δ i j , i = 1 , 2 , ⋯   , r ; j = 1 , 2 , ⋯   , r ② \begin{aligned} u_{i}^{\mathrm{T}} u_{j} &=\left(\frac{1}{\sigma_{i}} v_{i}^{\mathrm{T}} A^{\mathrm{T}}\right)\left(\frac{1}{\sigma_{j}} A v_{j}\right) \\ &=\frac{1}{\sigma_{i} \sigma_{j}} v_{i}^{\mathrm{T}}\left(A^{\mathrm{T}} A v_{j}\right) \\ &=\frac{1}{\sigma_{i} \sigma_{j}} v_{i}^{\mathrm{T}}\left(\sigma_{j}^2 v_{j}\right)\\ &=\frac{\sigma_{j}}{\sigma_{i}} v_{i}^{\mathrm{T}} v_{j} \\ &=\delta_{i j}, \quad i=1,2, \cdots, r ; \quad j=1,2, \cdots, r \end{aligned}② uiT​uj​​=(σi​1​viT​AT)(σj​1​Avj​)=σi​σj​1​viT​(ATAvj​)=σi​σj​1​viT​(σj2​vj​)=σi​σj​​viT​vj​=δij​,i=1,2,⋯,r;j=1,2,⋯,r​②

    由式 ①和式② 可知, u 1 , u 2 , ⋯   , u r u_{1}, u_{2}, \cdots, u_{r} u1​,u2​,⋯,ur​ 构成 A A A 的列空间的一组标准正交基, 列空间的维数为 r ∘ r_{\circ} r∘​ 如果将 A A A 看成是从 R n \mathbf{R}^{n} Rn 到 R m \mathbf{R}^{m} Rm 的线性变换, 则 A A A 的列空间和 A A A 的值域 R ( A ) R(A) R(A) 是相同的。因此 u 1 , u 2 , ⋯   , u r u_{1}, u_{2}, \cdots, u_{r} u1​,u2​,⋯,ur​ 也是 R ( A ) R(A) R(A) 的一组标准正交基。
    若 R ( A ) ⊥ R(A)^{\perp} R(A)⊥ 表示 R ( A ) R(A) R(A) 的正交补, 则有 R ( A ) R(A) R(A) 的维数为 r , R ( A ) ⊥ r, R(A)^{\perp} r,R(A)⊥ 的维数为 m − r m-r m−r, 两者的维数之和等于 m m m 。而且有 R ( A ) ⊥ = N ( A T ) R(A)^{\perp}=N\left(A^{\mathrm{T}}\right) R(A)⊥=N(AT) 成立。 令 { u r + 1 , u r + 2 , ⋯   , u m } \left\{u_{r+1}, u_{r+2}, \cdots, u_{m}\right\} {ur+1​,ur+2​,⋯,um​} 为 N ( A T ) N\left(A^{\mathrm{T}}\right) N(AT) 的一组标准正交基, 并令
    U 2 = [ u r + 1 u r + 2 ⋯ u m ] U = [ U 1 U 2 ] \begin{aligned} &U_{2}=\left[\begin{array}{llll} u_{r+1} & u_{r+2} & \cdots & u_{m} \end{array}\right] \\ &U=\left[\begin{array}{ll} U_{1} & U_{2} \end{array}\right] \end{aligned} ​U2​=[ur+1​​ur+2​​⋯​um​​]U=[U1​​U2​​]​

    则 u 1 , u 2 , ⋯   , u m u_{1}, u_{2}, \cdots, u_{m} u1​,u2​,⋯,um​ 构成了 R m \mathbf{R}^{m} Rm 的一组标准正交基。因此, U U U 是 m m m 阶正交矩阵, 这就是 矩阵 A A A 的奇异值分解中的 m m m 阶正交矩阵。
    (3) 证明 U Σ V T = A U \Sigma V^{\mathrm{T}}=A UΣVT=A

    U Σ V T = [ U 1 U 2 ] [ Σ 1 0 0 0 ] [ V 1 T V 2 T ] = U 1 Σ 1 V 1 T = A V 1 V 1 T = A \begin{aligned} U \Sigma V^{\mathrm{T}} &=\left[\begin{array}{ll} U_{1} & U_{2} \end{array}\right]\left[\begin{array}{cc} \Sigma_{1} & 0 \\ 0 & 0 \end{array}\right]\left[\begin{array}{c} V_{1}^{\mathrm{T}} \\ V_{2}^{\mathrm{T}} \end{array}\right] \\ &=U_{1} \Sigma_{1} V_{1}^{\mathrm{T}} \\ &=A V_{1} V_{1}^{\mathrm{T}} \\ &=A \end{aligned} UΣVT​=[U1​​U2​​][Σ1​0​00​][V1T​V2T​​]=U1​Σ1​V1T​=AV1​V1T​=A​

    至此证明了矩阵 A A A 存在奇异值分解。


15.1.2 紧奇异值分解与截断奇异值分解


  1. 紧奇异值分解
    定义 15.2 15.2 15.2 设有 m × n m \times n m×n 实矩阵 A A A, 其秩为 rank ⁡ ( A ) = r , r ⩽ min ⁡ ( m , n ) \operatorname{rank}(A)=r, r \leqslant \min (m, n) rank(A)=r,r⩽min(m,n), 则称 U r Σ r V r T U_{r} \Sigma_{r} V_{r}^{\mathrm{T}} Ur​Σr​VrT​ 为 A A A 的紧奇异值分解 ( compact singular value decomposition ), 即

    A = U r Σ r V r T \begin{aligned} &A=U_{r} \Sigma_{r} V_{r}^{\mathrm{T}} \end{aligned} ​A=Ur​Σr​VrT​​

    其中 U r U_{r} Ur​ 是 m × r m \times r m×r 矩阵, V r V_{r} Vr​ 是 n × r n \times r n×r 矩阵, Σ r \Sigma_{r} Σr​ 是 r r r 阶对角矩阵; 矩阵 U r U_{r} Ur​ 由完全奇异值分解中 U U U 的前 r r r 列、矩阵 V r V_{r} Vr​ 由 V V V 的前 r r r 列、矩阵 Σ r \Sigma_{r} Σr​ 由 Σ \Sigma Σ 的前 r r r 个对角线元素得到。紧奇异值分解的对角矩阵 Σ r \Sigma_{r} Σr​ 的秩与原始矩阵 A A A 的秩相等。

  2. 截断奇异值分解
    在矩阵的奇异值分解中, 只取最大的 k k k 个奇异值 ( k < r , r (k<r, r (k<r,r 为矩阵的秩)对应的部分, 就得到矩阵的截断奇异值分解。实际应用中提到矩阵的奇异值分解时, 通常指截断奇异值分解。
    定义 15.3 15.3 15.3 设 A A A 为 m × n m \times n m×n 实矩阵, 其秩 rank ⁡ ( A ) = r \operatorname{rank}(A)=r rank(A)=r, 且 0 < k < r 0<k<r 0<k<r, 则称 U k Σ k V k T U_{k} \Sigma_{k} V_{k}^{\mathrm{T}} Uk​Σk​VkT​ 为矩阵 A A A 的截断奇异值分解 ( truncated singular value decomposition )
    A ≈ U k Σ k V k T A \approx U_{k} \Sigma_{k} V_{k}^{\mathrm{T}} A≈Uk​Σk​VkT​

    其中 U k U_{k} Uk​ 是 m × k m \times k m×k 矩阵, V k V_{k} Vk​ 是 n × k n \times k n×k 矩阵, Σ k \Sigma_{k} Σk​ 是 k k k 阶对角矩阵; 矩阵 U k U_{k} Uk​ 由完全奇异值分解中 U U U 的前 k k k 列、矩阵 V k V_{k} Vk​ 由 V V V 的前 k k k 列、矩阵 Σ k \Sigma_{k} Σk​ 由 Σ \Sigma Σ 的前 k k k 个对角线元素 得到。对角矩阵 Σ k \Sigma_{k} Σk​ 的秩比原始矩阵 A A A 的秩低。

  • 紧奇异值分解对应着无损压缩
  • 截断奇异值分解对应着有损压缩。

15.1.3 几何解释


任意一个向量 x ∈ R n x \in \mathbf{R}^{n} x∈Rn, 经过基于 A = U Σ V T A=U \Sigma V^{\mathrm{T}} A=UΣVT 的线性变换,等价于经过坐标系 的旋转或反射变换 V T V^{\mathrm{T}} VT, 坐标轴的缩放变换 Σ \Sigma Σ, 以及坐标系的旋转或反射变换 U U U, 得 到向量 A x ∈ R m A x \in \mathbf{R}^{m} Ax∈Rm 。

【李航】统计学习方法--15. 奇异值分解(详细推导)


15.1.4 主要性质


  1. 设矩阵 A A A 的奇异值分解为 A = U Σ V T A=U \Sigma V^{\mathrm{T}} A=UΣVT, 则以下关系成立:
    A T A = ( U Σ V T ) T ( U Σ V T ) = V ( Σ T Σ ) V T A A T = ( U Σ V T ) ( U Σ V T ) T = U ( Σ Σ T ) U T \begin{aligned} &A^{\mathrm{T}} A=\left(U \Sigma V^{\mathrm{T}}\right)^{\mathrm{T}}\left(U \Sigma V^{\mathrm{T}}\right)=V\left(\Sigma^{\mathrm{T}} \Sigma\right) V^{\mathrm{T}} \\ &A A^{\mathrm{T}}=\left(U \Sigma V^{\mathrm{T}}\right)\left(U \Sigma V^{\mathrm{T}}\right)^{\mathrm{T}}=U\left(\Sigma \Sigma^{\mathrm{T}}\right) U^{\mathrm{T}} \end{aligned} ​ATA=(UΣVT)T(UΣVT)=V(ΣTΣ)VTAAT=(UΣVT)(UΣVT)T=U(ΣΣT)UT​

    矩阵 A T A A^{\mathrm{T}} A ATA 和 A A T A A^{\mathrm{T}} AAT 的特征分解存在, 且可以由矩阵 A A A 的奇异值分解 的矩阵表示。 V V V 的列向量是 A T A A^{\mathrm{T}} A ATA 的特征向量, U U U 的列向量是 A A T A A^{\mathrm{T}} AAT 的特征向量, Σ \Sigma Σ 的 奇异值是 A T A A^{\mathrm{T}} A ATA 和 A A T A A^{\mathrm{T}} AAT 的特征值的平方根。

  2. 在矩阵 A A A 的奇异值分解中, 奇异值、左奇异向量和右奇异向量之间存在对应 关系。
    由 A = U Σ V T A=U \Sigma V^{\mathrm{T}} A=UΣVT 易知
    A V = U Σ A V=U \Sigma AV=UΣ

    比较这一等式两端的第 j j j 列, 得到
    A v j = σ j u j , j = 1 , 2 , ⋯   , n A v_{j}=\sigma_{j} u_{j}, \quad j=1,2, \cdots, n Avj​=σj​uj​,j=1,2,⋯,n

    这是矩阵 A A A 的右奇异向量和奇异值、左奇异向量的关系。
    类似地, 由
    A T U = V Σ T A^{\mathrm{T}} U=V \Sigma^{\mathrm{T}} ATU=VΣT

    得到
    A T u j = σ j v j , j = 1 , 2 , ⋯   , n A T u j = 0 , j = n + 1 , n + 2 , ⋯   , m \begin{gathered} A^{\mathrm{T}} u_{j}=\sigma_{j} v_{j}, \quad j=1,2, \cdots, n \\ A^{\mathrm{T}} u_{j}=0, \quad j=n+1, n+2, \cdots, m \end{gathered} ATuj​=σj​vj​,j=1,2,⋯,nATuj​=0,j=n+1,n+2,⋯,m​

    这是矩阵 A A A 的左奇异向量和奇异值、右奇异向量的关系。

  3. 矩阵 A A A 的奇异值分解中, 奇异值 σ 1 , σ 2 , ⋯   , σ n \sigma_{1}, \sigma_{2}, \cdots, \sigma_{n} σ1​,σ2​,⋯,σn​ 是唯一的, 而矩阵 U U U 和 V V V 不 是唯一的。

  4. 矩阵 A A A 和 Σ \Sigma Σ 的秩相等, 等于正奇异值 σ i \sigma_{i} σi​ 的个数 r r r (包含重复的奇异值)。

  5. 矩阵 A A A 的 r r r 个右奇异向量 v 1 , v 2 , ⋯   , v r v_{1}, v_{2}, \cdots, v_{r} v1​,v2​,⋯,vr​ 构成 A T A^{\mathrm{T}} AT 的值域 R ( A T ) R\left(A^{\mathrm{T}}\right) R(AT) 的一组标准 正交基。因为矩阵 A T A^{\mathrm{T}} AT 是从 R m \mathbf{R}^{m} Rm 映射到 R n \mathbf{R}^{n} Rn 的线性变换,则 A T A^{\mathrm{T}} AT 的值域 R ( A T ) R\left(A^{\mathrm{T}}\right) R(AT) 和 A T A^{\mathrm{T}} AT 的列空间是相同的, v 1 , v 2 , ⋯   , v r v_{1}, v_{2}, \cdots, v_{r} v1​,v2​,⋯,vr​ 是 A T A^{\mathrm{T}} AT 的一组标准正交基, 因而也是 R ( A T ) R\left(A^{\mathrm{T}}\right) R(AT) 的一组 标准正交基。
    矩阵 A A A 的 n − r n-r n−r 个右奇异向量 v r + 1 , v r + 2 , ⋯   , v n v_{r+1}, v_{r+2}, \cdots, v_{n} vr+1​,vr+2​,⋯,vn​ 构成 A A A 的零空间 N ( A ) N(A) N(A) 的一组 标准正交基。
    矩阵 A A A 的 r r r 个左奇异向量 u 1 , u 2 , ⋯   , u r u_{1}, u_{2}, \cdots, u_{r} u1​,u2​,⋯,ur​ 构成值域 R ( A ) R(A) R(A) 的一组标准正交基。 矩阵 A A A 的 m − r m-r m−r 个左奇异向量 u r + 1 , u r + 2 , ⋯   , u m u_{r+1}, u_{r+2}, \cdots, u_{m} ur+1​,ur+2​,⋯,um​ 构成 A T A^{\mathrm{T}} AT 的零空间 N ( A T ) N\left(A^{\mathrm{T}}\right) N(AT) 的 一组标准正交基。


15.2 奇异值分解的计算


矩阵奇异值分解的计算过程
给定 m × n m \times n m×n矩阵 A A A

  1. 首先求 A T A A^{\mathrm{T}} A ATA 的特征值和特征向量。
    计算对称矩阵 W = A T A W=A^{\mathrm{T}} A W=ATA 。
    求解特征方程
    ( W − λ I ) x = 0 (W-\lambda I) x=0 (W−λI)x=0

    得到特征值 λ i \lambda_{i} λi​, 并将特征值由大到小排列
    λ 1 ⩾ λ 2 ⩾ ⋯ ⩾ λ n ⩾ 0 \lambda_{1} \geqslant \lambda_{2} \geqslant \cdots \geqslant \lambda_{n} \geqslant 0 λ1​⩾λ2​⩾⋯⩾λn​⩾0

    将特征值 λ i ( i = 1 , 2 , ⋯   , n ) \lambda_{i}(i=1,2, \cdots, n) λi​(i=1,2,⋯,n) 代入特征方程求得对应的特征向量。

  2. 求 n n n 阶正交矩阵 V V V
    将特征向量单位化, 得到单位特征向量 v 1 , v 2 , ⋯   , v n v_{1}, v_{2}, \cdots, v_{n} v1​,v2​,⋯,vn​, 构成 n n n 阶正交矩阵 V V V :
    V = [ v 1 v 2 ⋯ v n ] V=\left[\begin{array}{llll} v_{1} & v_{2} & \cdots & v_{n} \end{array}\right] V=[v1​​v2​​⋯​vn​​]

  3. 求 m × n m \times n m×n 对角矩阵 Σ \Sigma Σ
    计算 A A A 的奇异值
    σ i = λ i , i = 1 , 2 , ⋯   , n \sigma_{i}=\sqrt{\lambda_{i}}, \quad i=1,2, \cdots, n σi​=λi​ ​,i=1,2,⋯,n

    构造 m × n m \times n m×n 矩形对角矩阵 Σ \Sigma Σ, 主对角线元素是奇异值, 其余元素是零,
    Σ = diag ⁡ ( σ 1 , σ 2 , ⋯   , σ n ) \Sigma=\operatorname{diag}\left(\sigma_{1}, \sigma_{2}, \cdots, \sigma_{n}\right) Σ=diag(σ1​,σ2​,⋯,σn​)

  4. 求 m m m 阶正交矩阵 U U U
    对 A A A 的前 r r r 个正奇异值, 令
    u j = 1 σ j A v j , j = 1 , 2 , ⋯   , r u_{j}=\frac{1}{\sigma_{j}} A v_{j}, \quad j=1,2, \cdots, r uj​=σj​1​Avj​,j=1,2,⋯,r

    得到
    U 1 = [ u 1 u 2 ⋯ u r ] U_{1}=\left[\begin{array}{llll} u_{1} & u_{2} & \cdots & u_{r} \end{array}\right] U1​=[u1​​u2​​⋯​ur​​]

    求 A T A^{\mathrm{T}} AT 的零空间的一组标准正交基 { u r + 1 , u r + 2 , ⋯   , u m } \left\{u_{r+1}, u_{r+2}, \cdots, u_{m}\right\} {ur+1​,ur+2​,⋯,um​}, 令
    U 2 = [ u r + 1 u r + 2 ⋯ u m ] U_{2}=\left[\begin{array}{llll} u_{r+1} & u_{r+2} & \cdots & u_{m} \end{array}\right] U2​=[ur+1​​ur+2​​⋯​um​​]

    并令
    U = [ U 1 U 2 ] U=\left[\begin{array}{ll} U_{1} & U_{2} \end{array}\right] U=[U1​​U2​​]

  5. 得到奇异值分解
    A = U Σ V T A=U \Sigma V^{\mathrm{T}} A=UΣVT


15.3 奇异值分解与矩阵近似


15.3.1 弗罗贝尼乌斯范数


定义 15.4 15.4 15.4 (弗罗贝尼乌斯范数) 设矩阵 A ∈ R m × n , A = [ a i j ] m × n A \in \mathbf{R}^{m \times n}, A=\left[a_{i j}\right]_{m \times n} A∈Rm×n,A=[aij​]m×n​, 定义矩阵 A A A 的弗罗贝尼乌斯范数为

∥ A ∥ F = ( ∑ i = 1 m ∑ j = 1 n ( a i j ) 2 ) 1 2 \|A\|_{F}=\left(\sum_{i=1}^{m} \sum_{j=1}^{n}\left(a_{i j}\right)^{2}\right)^{\frac{1}{2}} ∥A∥F​=(i=1∑m​j=1∑n​(aij​)2)21​

引理 15.1 15.1 15.1 设矩阵 A ∈ R m × n , A A \in \mathbf{R}^{m \times n}, A A∈Rm×n,A 的奇异值分解为 U Σ V T U \Sigma V^{\mathrm{T}} UΣVT, 其中 Σ = diag ⁡ ( σ 1 , \Sigma=\operatorname{diag}\left(\sigma_{1},\right. Σ=diag(σ1​,,
σ 2 , ⋯   , σ n ) \left.\sigma_{2}, \cdots, \sigma_{n}\right) σ2​,⋯,σn​), 则

∥ A ∥ F = ( σ 1 2 + σ 2 2 + ⋯ + σ n 2 ) 1 2 \|A\|_{F}=\left(\sigma_{1}^{2}+\sigma_{2}^{2}+\cdots+\sigma_{n}^{2}\right)^{\frac{1}{2}} ∥A∥F​=(σ12​+σ22​+⋯+σn2​)21​

证明 一般地, 若 Q Q Q 是 m m m 阶正交矩阵, 则有

∥ Q A ∥ F = ∥ A ∥ F \|Q A\|_{F}=\|A\|_{F} ∥QA∥F​=∥A∥F​

因为

∥ Q A ∥ F 2 = ∥ ( Q a 1 , Q a 2 , ⋯   , Q a n ) ∥ F 2 = ∑ i = 1 n ∥ Q a i ∥ 2 2 = ∑ i = 1 n ( Q a i ) T Q a i = ∑ i = 1 n a i T Q T Q a i = ∑ i = 1 n ∥ a i ∥ 2 2 = ∥ A ∥ F 2 \begin{aligned} \|Q A\|_{F}^{2} &=\left\|\left(Q a_{1}, Q a_{2}, \cdots, Q a_{n}\right)\right\|_{F}^{2} \\ &=\sum_{i=1}^{n}\left\|Q a_{i}\right\|_{2}^{2}=\sum_{i=1}^{n}(Q a_{i})^TQ a_{i}=\sum_{i=1}^{n}a_{i}^TQ^TQ a_{i}=\sum_{i=1}^{n}\left\|a_{i}\right\|_{2}^{2}=\|A\|_{F}^{2} \end{aligned} ∥QA∥F2​​=∥(Qa1​,Qa2​,⋯,Qan​)∥F2​=i=1∑n​∥Qai​∥22​=i=1∑n​(Qai​)TQai​=i=1∑n​aiT​QTQai​=i=1∑n​∥ai​∥22​=∥A∥F2​​

同样, 若 P P P 是 n n n 阶正交矩阵, 则有

∥ A P T ∥ F = ∥ A ∥ F \left\|A P^{\mathrm{T}}\right\|_{F}=\|A\|_{F} ∥∥​APT∥∥​F​=∥A∥F​

∥ A ∥ F = ∥ U Σ V T ∥ F = ∥ Σ ∥ F \|A\|_{F}=\left\|U \Sigma V^{\mathrm{T}}\right\|_{F}=\|\Sigma\|_{F} ∥A∥F​=∥∥​UΣVT∥∥​F​=∥Σ∥F​

∥ A ∥ F = ( σ 1 2 + σ 2 2 + ⋯ + σ n 2 ) 1 2 \|A\|_{F}=\left(\sigma_{1}^{2}+\sigma_{2}^{2}+\cdots+\sigma_{n}^{2}\right)^{\frac{1}{2}} ∥A∥F​=(σ12​+σ22​+⋯+σn2​)21​


15.3.2 矩阵的最优近似


定理 15.2 15.2 15.2 设矩阵 A ∈ R m × n A \in \mathbf{R}^{m \times n} A∈Rm×n, 矩阵的秩 rank ⁡ ( A ) = r \operatorname{rank}(A)=r rank(A)=r, 并设 M \mathcal{M} M 为 R m × n \mathbf{R}^{m \times n} Rm×n 中所
有秩不超过 k k k 的矩阵集合, 0 < k < r 0<k<r 0<k<r, 则存在一个秩为 k k k 的矩阵 X ∈ M X \in \mathcal{M} X∈M, 使得

∥ A − X ∥ F = min ⁡ S ∈ M ∥ A − S ∥ F \|A-X\|_{F}=\min _{S \in \mathcal{M}}\|A-S\|_{F} ∥A−X∥F​=S∈Mmin​∥A−S∥F​

称矩阵 X X X 为矩阵 A A A 在弗罗贝尼乌斯范数意义下的最优近似。

定理 15.3 15.3 15.3 设矩阵 A ∈ R m × n A \in \mathbf{R}^{m \times n} A∈Rm×n, 矩阵的秩 rank ⁡ ( A ) = r \operatorname{rank}(A)=r rank(A)=r, 有奇异值分解 A = A= A= U Σ V T U \Sigma V^{\mathrm{T}} UΣVT, 并设 M \mathcal{M} M 为 R m × n \mathrm{R}^{m \times n} Rm×n 中所有秩不超过 k k k 的矩阵的集合, 0 < k < r 0<k<r 0<k<r, 若秩为 k k k 的 矩阵 X ∈ M X \in \mathcal{M} X∈M 满足

∥ A − X ∥ F = min ⁡ S ∈ M ∥ A − S ∥ F ② \|A-X\|_{F}=\min _{S \in \mathcal{M}}\|A-S\|_{F}② ∥A−X∥F​=S∈Mmin​∥A−S∥F​②

∥ A − X ∥ F = ( σ k + 1 2 + σ k + 2 2 + ⋯ + σ n 2 ) 1 2 ① \|A-X\|_{F}=\left(\sigma_{k+1}^{2}+\sigma_{k+2}^{2}+\cdots+\sigma_{n}^{2}\right)^{\frac{1}{2}}① ∥A−X∥F​=(σk+12​+σk+22​+⋯+σn2​)21​①

特别地, 若 A ′ = U Σ ′ V T A^{\prime}=U \Sigma^{\prime} V^{\mathrm{T}} A′=UΣ′VT, 其中

Σ ′ = [ σ 1 ⋱ 0 σ k 0 0 ⋱ 0 ] = [ Σ k 0 0 0 ] \Sigma^{\prime}=\left[\begin{array}{ccccc} \sigma_{1} & & & & \\ & \ddots & & & 0 & \\ & & \sigma_{k} & & & \\ & & & 0 & & \\ & 0 & & & \ddots & \\ & & & & & 0 \end{array}\right]=\left[\begin{array}{cc} \Sigma_{k} & 0 \\ 0 & 0 \end{array}\right] Σ′=⎣⎢⎢⎢⎢⎢⎢⎡​σ1​​⋱0​σk​​0​0⋱​0​⎦⎥⎥⎥⎥⎥⎥⎤​=[Σk​0​00​]

A − A ′ = U [ 0 0 0 Σ n − k ] V T A-A^{\prime}=U\left[\begin{array}{cc} 0 & 0 \\ 0 & \Sigma_{n-k} \end{array}\right]V^T A−A′=U[00​0Σn−k​​]VT

∥ A − A ′ ∥ F = ( σ k + 1 2 + σ k + 2 2 + ⋯ + σ n 2 ) 1 2 = min ⁡ S ∈ M ∥ A − S ∥ F \left\|A-A^{\prime}\right\|_{F}=\left(\sigma_{k+1}^{2}+\sigma_{k+2}^{2}+\cdots+\sigma_{n}^{2}\right)^{\frac{1}{2}}=\min _{S \in \mathcal{M}}\|A-S\|_{F} ∥A−A′∥F​=(σk+12​+σk+22​+⋯+σn2​)21​=S∈Mmin​∥A−S∥F​

证明 令 X ∈ M X \in \mathcal{M} X∈M 为满足式 ② ② ② 的一个矩阵。由于

∥ A − X ∥ F ⩽ ∥ A − A ′ ∥ F = ( σ k + 1 2 + σ k + 2 2 + ⋯ + σ n 2 ) 1 2 ③ \|A-X\|_{F} \leqslant\left\|A-A^{\prime}\right\|_{F}=\left(\sigma_{k+1}^{2}+\sigma_{k+2}^{2}+\cdots+\sigma_{n}^{2}\right)^{\frac{1}{2}}③ ∥A−X∥F​⩽∥A−A′∥F​=(σk+12​+σk+22​+⋯+σn2​)21​③

下面证明

∥ A − X ∥ F ⩾ ( σ k + 1 2 + σ k + 2 2 + ⋯ + σ n 2 ) 1 2 \|A-X\|_{F} \geqslant\left(\sigma_{k+1}^{2}+\sigma_{k+2}^{2}+\cdots+\sigma_{n}^{2}\right)^{\frac{1}{2}} ∥A−X∥F​⩾(σk+12​+σk+22​+⋯+σn2​)21​

于是式 ①成立。

设 X X X 的奇异值分解为 Q Ω P T Q \Omega P^{\mathrm{T}} QΩPT, 其中
若令矩阵 B = Q T A P B=Q^{\mathrm{T}} A P B=QTAP, 则 A = Q B P T A=Q B P^{\mathrm{T}} A=QBPT 。由此得到

∥ A − X ∥ F = ∥ Q ( B − Ω ) P T ∥ F = ∥ B − Ω ∥ F \|A-X\|_{F}=\left\|Q(B-\Omega) P^{\mathrm{T}}\right\|_{F}=\|B-\Omega\|_{F} ∥A−X∥F​=∥∥​Q(B−Ω)PT∥∥​F​=∥B−Ω∥F​

用 Ω \Omega Ω 分块方法对 B B B 分块

B = [ B 11 B 12 B 21 B 22 ] B=\left[\begin{array}{ll} B_{11} & B_{12} \\ B_{21} & B_{22} \end{array}\right] B=[B11​B21​​B12​B22​​]

其中 B 11 B_{11} B11​ 是 k × k k \times k k×k 子矩阵, B 12 B_{12} B12​ 是 k × ( n − k ) k \times(n-k) k×(n−k) 子矩阵, B 21 B_{21} B21​ 是 ( m − k ) × k (m-k) \times k (m−k)×k 子矩阵, B 22 B_{22} B22​ 是 ( m − k ) × ( n − k ) (m-k) \times(n-k) (m−k)×(n−k) 子矩阵。可得

∥ A − X ∥ F 2 = ∥ B − Ω ∥ F 2 = ∥ B 11 − Ω k ∥ F 2 + ∥ B 12 ∥ F 2 + ∥ B 21 ∥ F 2 + ∥ B 22 ∥ F 2 \begin{aligned} \|A-X\|_{F}^{2} &=\|B-\Omega\|_{F}^{2} \\ &=\left\|B_{11}-\Omega_{k}\right\|_{F}^{2}+\left\|B_{12}\right\|_{F}^{2}+\left\|B_{21}\right\|_{F}^{2}+\left\|B_{22}\right\|_{F}^{2} \end{aligned} ∥A−X∥F2​​=∥B−Ω∥F2​=∥B11​−Ωk​∥F2​+∥B12​∥F2​+∥B21​∥F2​+∥B22​∥F2​​

现证 B 12 = 0 , B 21 = 0 B_{12}=0, B_{21}=0 B12​=0,B21​=0 。用反证法。若 B 12 ≠ 0 B_{12} \neq 0 B12​​=0, 令

Y = Q [ B 11 B 12 0 0 ] P T Y=Q\left[\begin{array}{cc} B_{11} & B_{12} \\ 0 & 0 \end{array}\right] P^{\mathrm{T}} Y=Q[B11​0​B12​0​]PT

则 Y ∈ M Y \in \mathcal{M} Y∈M, 且

∥ A − Y ∥ F 2 = ∥ B 21 ∥ F 2 + ∥ B 22 ∥ F 2 < ∥ A − X ∥ F 2 \|A-Y\|_{F}^{2}=\left\|B_{21}\right\|_{F}^{2}+\left\|B_{22}\right\|_{F}^{2}<\|A-X\|_{F}^{2} ∥A−Y∥F2​=∥B21​∥F2​+∥B22​∥F2​<∥A−X∥F2​

这与 X X X 的定义式 ③ ③ ③ 矛盾, 证明了 B 12 = 0 B_{12}=0 B12​=0 。同样可证 B 21 = 0 B_{21}=0 B21​=0 。于是

∥ A − X ∥ F 2 = ∥ B 11 − Ω k ∥ F 2 + ∥ B 22 ∥ F 2 \|A-X\|_{F}^{2}=\left\|B_{11}-\Omega_{k}\right\|_{F}^{2}+\left\|B_{22}\right\|_{F}^{2} ∥A−X∥F2​=∥B11​−Ωk​∥F2​+∥B22​∥F2​

再证 B 11 = Ω k B_{11}=\Omega_{k} B11​=Ωk​ 。为此令

Z = Q [ B 11 0 0 0 ] P T Z=Q\left[\begin{array}{cc} B_{11} & 0 \\ 0 & 0 \end{array}\right] P^{\mathrm{T}} Z=Q[B11​0​00​]PT

则 Z ∈ M Z \in \mathcal{M} Z∈M, 且

∥ A − Z ∥ F 2 = ∥ B 22 ∥ F 2 ⩽ ∥ B 11 − Ω k ∥ F 2 + ∥ B 22 ∥ F 2 = ∥ A − X ∥ F 2 \|A-Z\|_{F}^{2}=\left\|B_{22}\right\|_{F}^{2} \leqslant\left\|B_{11}-\Omega_{k}\right\|_{F}^{2}+\left\|B_{22}\right\|_{F}^{2}=\|A-X\|_{F}^{2} ∥A−Z∥F2​=∥B22​∥F2​⩽∥B11​−Ωk​∥F2​+∥B22​∥F2​=∥A−X∥F2​

由式③知, ∥ B 11 − Ω k ∥ F 2 = 0 \left\|B_{11}-\Omega_{k}\right\|_{F}^{2}=0 ∥B11​−Ωk​∥F2​=0, 即 B 11 = Ω k B_{11}=\Omega_{k} B11​=Ωk​ 。
最后看 B 22 B_{22} B22​ 。若 ( m − k ) × ( n − k ) (m-k) \times(n-k) (m−k)×(n−k) 子矩阵 B 22 B_{22} B22​ 有奇异值分解 U 1 Λ V 1 T U_{1} \Lambda V_{1}^{\mathrm{T}} U1​ΛV1T​, 则

∥ A − X ∥ F = ∥ B 22 ∥ F = ∥ Λ ∥ F \|A-X\|_{F}=\left\|B_{22}\right\|_{F}=\|\Lambda\|_{F} ∥A−X∥F​=∥B22​∥F​=∥Λ∥F​

证明 Λ \Lambda Λ 的对角线元素为 A A A 的奇异值。为此, 令

U 2 = [ I k 0 0 U 1 ] , V 2 = [ I k 0 0 V 1 ] U_{2}=\left[\begin{array}{cc} I_{k} & 0 \\ 0 & U_{1} \end{array}\right], \quad V_{2}=\left[\begin{array}{cc} I_{k} & 0 \\ 0 & V_{1} \end{array}\right] U2​=[Ik​0​0U1​​],V2​=[Ik​0​0V1​​]

其中 I k I_{k} Ik​ 是 k k k 阶单位矩阵, U 2 , V 2 U_{2}, V_{2} U2​,V2​ 的分块与 B B B 的分块一致。注意到 B B B 及 B 22 B_{22} B22​ 的奇异 值分解,即得

U 2 T Q T A P V 2 = [ Ω k 0 0 Λ ] U_{2}^{\mathrm{T}} Q^{\mathrm{T}} A P V_{2}=\left[\begin{array}{cc} \Omega_{k} & 0 \\ 0 & \Lambda \end{array}\right] U2T​QTAPV2​=[Ωk​0​0Λ​]

A = ( Q U 2 ) [ Ω k 0 0 Λ ] ( P V 2 ) T A=\left(Q U_{2}\right)\left[\begin{array}{cc} \Omega_{k} & 0 \\ 0 & \Lambda \end{array}\right]\left(P V_{2}\right)^{\mathrm{T}} A=(QU2​)[Ωk​0​0Λ​](PV2​)T

由此可知 Λ \Lambda Λ 的对角线元素为 A A A 的奇异值。故有

∥ A − X ∥ F = ∥ Λ ∥ F ⩾ ( σ k + 1 2 + σ k + 2 2 + ⋯ + σ n 2 ) 1 2 \|A-X\|_{F}=\|\Lambda\|_{F} \geqslant\left(\sigma_{k+1}^{2}+\sigma_{k+2}^{2}+\cdots+\sigma_{n}^{2}\right)^{\frac{1}{2}} ∥A−X∥F​=∥Λ∥F​⩾(σk+12​+σk+22​+⋯+σn2​)21​

于是证明了

∥ A − X ∥ F = ( σ k + 1 2 + σ k + 2 2 + ⋯ + σ n 2 ) 1 2 = ∥ A − A ′ ∥ F \|A-X\|_{F}=\left(\sigma_{k+1}^{2}+\sigma_{k+2}^{2}+\cdots+\sigma_{n}^{2}\right)^{\frac{1}{2}}=\left\|A-A^{\prime}\right\|_{F} ∥A−X∥F​=(σk+12​+σk+22​+⋯+σn2​)21​=∥A−A′∥F​


15.3.3 矩阵的外积展开式


下面介绍利用外积展开式对矩阵 A A A 的近似。矩阵 A A A 的奇异值分解 U Σ V T U \Sigma V^{\mathrm{T}} UΣVT 也可以 由外积形式表示。事实上, 若将 A A A 的奇异值分解看成矩阵 U Σ U \Sigma UΣ 和 V T V^{\mathrm{T}} VT 的乘积, 将 U Σ U \Sigma UΣ 按列向量分块, 将 V T V^{\mathrm{T}} VT 按行向量分块, 即得

U Σ = [ σ 1 u 1 σ 2 u 2 ⋯ σ n u n ] V T = [ v 1 T v 2 T ⋮ v n T ] \begin{gathered} U \Sigma=\left[\begin{array}{llll} \sigma_{1} u_{1} & \sigma_{2} u_{2} & \cdots & \sigma_{n} u_{n} \end{array}\right] \\ V^{\mathrm{T}}=\left[\begin{array}{c} v_{1}^{\mathrm{T}} \\ v_{2}^{\mathrm{T}} \\ \vdots \\ v_{n}^{\mathrm{T}} \end{array}\right] \end{gathered} UΣ=[σ1​u1​​σ2​u2​​⋯​σn​un​​]VT=⎣⎢⎢⎢⎡​v1T​v2T​⋮vnT​​⎦⎥⎥⎥⎤​​

A = σ 1 u 1 v 1 T + σ 2 u 2 v 2 T + ⋯ + σ n u n v n T A=\sigma_{1} u_{1} v_{1}^{\mathrm{T}}+\sigma_{2} u_{2} v_{2}^{\mathrm{T}}+\cdots+\sigma_{n} u_{n} v_{n}^{\mathrm{T}} A=σ1​u1​v1T​+σ2​u2​v2T​+⋯+σn​un​vnT​

上式称为矩阵 A A A 的外积展开式, 其中 u k v k T u_{k} v_{k}^{\mathrm{T}} uk​vkT​ 为 m × n m \times n m×n 矩阵, 是列向量 u k u_{k} uk​ 和行 向量 v k T v_{k}^{\mathrm{T}} vkT​ 的外积, 其第 i i i 行第 j j j 列元素为 u k u_{k} uk​ 的第 i i i 个元素与 v k T v_{k}^{\mathrm{T}} vkT​ 的第 j j j 个元素的乘积。即

u i v j T = [ u 1 i u 2 i ⋮ u m i ] [ v 1 j v 2 j ⋯ v n j ] = [ u 1 i v 1 j u 1 i v 2 j ⋯ u 1 i v n j u 2 i v 1 j u 2 i v 2 j ⋯ u 2 i v n j ⋮ ⋮ ⋮ u m i v 1 j u m i v 2 j ⋯ u m i v n j ] u_{i} v_{j}^{\mathrm{T}}=\left[\begin{array}{c} u_{1 i} \\ u_{2 i} \\ \vdots \\ u_{m i} \end{array}\right]\left[\begin{array}{llll} v_{1 j} & v_{2 j} & \cdots & v_{n j} \end{array}\right]=\left[\begin{array}{cccc} u_{1 i} v_{1 j} & u_{1 i} v_{2 j} & \cdots & u_{1 i} v_{n j} \\ u_{2 i} v_{1 j} & u_{2 i} v_{2 j} & \cdots & u_{2 i} v_{n j} \\ \vdots & \vdots & & \vdots \\ u_{m i} v_{1 j} & u_{m i} v_{2 j} & \cdots & u_{m i} v_{n j} \end{array}\right] ui​vjT​=⎣⎢⎢⎢⎡​u1i​u2i​⋮umi​​⎦⎥⎥⎥⎤​[v1j​​v2j​​⋯​vnj​​]=⎣⎢⎢⎢⎡​u1i​v1j​u2i​v1j​⋮umi​v1j​​u1i​v2j​u2i​v2j​⋮umi​v2j​​⋯⋯⋯​u1i​vnj​u2i​vnj​⋮umi​vnj​​⎦⎥⎥⎥⎤​

A A A 的外积展开式也可以写成下面的形式

A = ∑ k = 1 n A k = ∑ k = 1 n σ k u k v k T A=\sum_{k=1}^{n} A_{k}=\sum_{k=1}^{n} \sigma_{k} u_{k} v_{k}^{\mathrm{T}} A=k=1∑n​Ak​=k=1∑n​σk​uk​vkT​

其中 A k = σ k u k v k T A_{k}=\sigma_{k} u_{k} v_{k}^{\mathrm{T}} Ak​=σk​uk​vkT​ 是 m × n m \times n m×n 矩阵。上式将矩阵 A A A 分解为矩阵的有序加权和。
由矩阵 A A A 的外积展开式知, 若 A A A 的秩为 n n n, 则

A = σ 1 u 1 v 1 T + σ 2 u 2 v 2 T + ⋯ + σ n u n v n T A=\sigma_{1} u_{1} v_{1}^{\mathrm{T}}+\sigma_{2} u_{2} v_{2}^{\mathrm{T}}+\cdots+\sigma_{n} u_{n} v_{n}^{\mathrm{T}} A=σ1​u1​v1T​+σ2​u2​v2T​+⋯+σn​un​vnT​

设矩阵

A n − 1 = σ 1 u 1 v 1 T + σ 2 u 2 v 2 T + ⋯ + σ n − 1 u n − 1 v n − 1 T A_{n-1}=\sigma_{1} u_{1} v_{1}^{\mathrm{T}}+\sigma_{2} u_{2} v_{2}^{\mathrm{T}}+\cdots+\sigma_{n-1} u_{n-1} v_{n-1}^{\mathrm{T}} An−1​=σ1​u1​v1T​+σ2​u2​v2T​+⋯+σn−1​un−1​vn−1T​

则 A n − 1 A_{n-1} An−1​ 的秩为 n − 1 n-1 n−1, 并且 A n − 1 A_{n-1} An−1​ 是秩为 n − 1 n-1 n−1 矩阵在弗罗贝尼乌斯范数意义下 A A A 的 最优近似矩阵。
类似地, 设矩阵

A n − 2 = σ 1 u 1 v 1 T + σ 2 u 2 v 2 T + ⋯ + σ n − 2 u n − 2 v n − 2 T A_{n-2}=\sigma_{1} u_{1} v_{1}^{\mathrm{T}}+\sigma_{2} u_{2} v_{2}^{\mathrm{T}}+\cdots+\sigma_{n-2} u_{n-2} v_{n-2}^{\mathrm{T}} An−2​=σ1​u1​v1T​+σ2​u2​v2T​+⋯+σn−2​un−2​vn−2T​

则 A n − 2 A_{n-2} An−2​ 的秩为 n − 2 n-2 n−2, 并且 A n − 2 A_{n-2} An−2​ 是秩为 n − 2 n-2 n−2 矩阵中在弗罗贝尼乌斯范数意义下 A A A 的最优近似矩阵。以此类推。一般地,设矩阵

A k = σ 1 u 1 v 1 T + σ 2 u 2 v 2 T + ⋯ + σ k u k v k T A_{k}=\sigma_{1} u_{1} v_{1}^{\mathrm{T}}+\sigma_{2} u_{2} v_{2}^{\mathrm{T}}+\cdots+\sigma_{k} u_{k} v_{k}^{\mathrm{T}} Ak​=σ1​u1​v1T​+σ2​u2​v2T​+⋯+σk​uk​vkT​

则 A k A_{k} Ak​ 的秩为 k k k, 并且 A k A_{k} Ak​ 是秩为 k k k 的矩阵中在弗罗贝尼乌斯范数意义下 A A A 的最优近 似矩阵。矩阵 A k A_{k} Ak​ 就是 A A A 的截断奇异值分解。
由于通常奇异值 σ i \sigma_{i} σi​ 递减很快, 所以 k k k 取很小值时, A k A_{k} Ak​ 也可以对 A A A 有很好的近似。

上一篇:【变分法学习笔记(二)】变分法中的欧拉方程的退化形式


下一篇:深度学习算子优化-FFT