SVD奇异值分解

文章目录


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

奇异值分解的定义与性质

定义与定理

定 义 1 \large\color{magenta}{\boxed{\color{brown}{定义 1} }} 定义1​ (奇异值分解) 矩阵的奇此值分解是指,将一个非零的 m × n m \times n m×n 实矩阵 A , A ∈ R m × n , A, A \in \mathbf{R}^{m \times n}, A,A∈Rm×n, 表示为以下三个实矩阵乘积形式的运算 , 即进行矩阵的因子分解:
A = U Σ V T (1) A=U \Sigma V^{\mathrm{T}}\tag{1} A=UΣVT(1)
其中 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 \mathrm{SVD} SVD ), σ i \sigma_{i} σi​ 称为矩阵 A A A 的奇异值 ( singular value ) , U U U 的列向量称为左奇异向量(left singular vector ) , V ), V ),V 的列向量称为右奇异向量(right singular vector )。

注意奇异值分解不要求矩阵 A A A 是方阵,事实上矩阵的奇异值分解可以看作是方阵的对角化的推广。

下面看一个奇异值分解的例子。

例 1 \Large\color{violet}{例1} 例1 给定一个 5 × 4 5 \times 4 5×4 矩阵 A A A
A = [ 1 0 0 0 0 0 0 4 0 3 0 0 0 0 0 0 2 0 0 0 ] A=\left[\begin{array}{llll} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 4 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 \end{array}\right] A=⎣⎢⎢⎢⎢⎡​10002​00300​00000​04000​⎦⎥⎥⎥⎥⎤​
它的奇异值分解由三个矩阵的乘积 U Σ V T U \Sigma V^{\mathrm{T}} UΣVT 给出,矩阵 U , Σ , V T U, \Sigma, V^{\mathrm{T}} U,Σ,VT 分别为
U = [ 0 0 0.2 0 0.8 1 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0.8 0 − 0.2 ] , Σ = [ 4 0 0 0 0 3 0 0 0 0 5 0 0 0 0 0 0 0 0 0 ] V T = [ 0 0 0 1 0 1 0 0 1 0 0 0 0 0 1 0 ] \begin{array}{l} U=\left[\begin{array}{lllll} 0 & 0 & \sqrt{0.2} & 0 & \sqrt{0.8} \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & \sqrt{0.8} & 0 & -\sqrt{0.2} \end{array}\right], \quad \Sigma=\left[\begin{array}{llll} 4 & 0 & 0 & 0 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & \sqrt{5} & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{array}\right] \\ V^{\mathrm{T}}=\left[\begin{array}{llll} 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{array}\right] & \end{array} U=⎣⎢⎢⎢⎢⎡​01000​00100​0.2 ​0000.8 ​​00010​0.8 ​000−0.2 ​​⎦⎥⎥⎥⎥⎤​,Σ=⎣⎢⎢⎢⎢⎡​40000​03000​005 ​00​00000​⎦⎥⎥⎥⎥⎤​VT=⎣⎢⎢⎡​0010​0100​0001​1000​⎦⎥⎥⎤​​​
矩阵 Σ \Sigma Σ 是对角矩阵,对角线外的元素都是 0 , 0, 0, 对角线上的元素非负,按降序排列。矩阵 U U U 和 V V V 是正交矩阵,它们与各自的转置矩阵相乘是单位矩阵,即
U U T = E 5 , V V T = E 4 U U^{\mathrm{T}}=E_{5}, \quad V V^{\mathrm{T}}=E_{4} UUT=E5​,VVT=E4​
矩阵的奇异值分解不是唯一的。在此例中如果选择 U U U 为
U = [ 0 0 0.2 0.4 − 0.4 1 0 0 0 0 0 1 0 0 0 0 0 0 0.5 0.5 0 0 0.8 − 0.1 0.1 ] U=\left[\begin{array}{ccccc} 0 & 0 & \sqrt{0.2} & \sqrt{0.4} & -\sqrt{0.4} \\ 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & \sqrt{0.5} & \sqrt{0.5} \\ 0 & 0 & \sqrt{0.8} & -\sqrt{0.1} & \sqrt{0.1} \end{array}\right] U=⎣⎢⎢⎢⎢⎡​01000​00100​0.2 ​0000.8 ​​0.4 ​000.5 ​−0.1 ​​−0.4 ​000.5 ​0.1 ​​⎦⎥⎥⎥⎥⎤​
而 Σ \Sigma Σ 与 V V V 不变, 那么 U Σ V T U \Sigma V^{\mathrm{T}} UΣVT 也是 A A A 的一个奇异值分解。

任意给定一个实矩阵,其奇异值分解是否一定存在呢?答案是肯定的,下面的奇异值分解的基本定理给予保证。

定 理 1 \large\color{magenta}{\boxed{\color{brown}{定理 1} }} 定理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 (2) A=U \Sigma V^{\mathrm{T}}\tag{2} A=UΣVT(2)
其中 U U U 是 m m m 阶正交矩阵, V V V 是 n n n 阶正交矩阵, Σ \Sigma Σ 是 m × n m \times n m×n 矩形对角矩阵,其对角线元素非负,且按降序排列。

【证明】 \quad 证明是构造性的,对给定的矩阵 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^{\mathrm{T}} A ATA 的特征值都是非负的。事实上, 令 λ \lambda λ 是 A T A A^{\mathrm{T}} A ATA 的一个特征值, x x x 是对应的特征向量,则
∥ A x ∥ 2 = x T A T A x = λ x T x = λ ∥ x ∥ 2 \|A x\|^{2}=x^{\mathrm{T}} A^{\mathrm{T}} A x=\lambda x^{\mathrm{T}} x=\lambda\|x\|^{2} ∥Ax∥2=xTATAx=λxTx=λ∥x∥2
于是
λ = ∥ A x ∥ 2 ∥ x ∥ 2 ⩾ 0 (3) \lambda=\frac{\|A x\|^{2}}{\|x\|^{2}} \geqslant 0\tag{3} λ=∥x∥2∥Ax∥2​⩾0(3)
可以假设正交矩阵 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 (4) \lambda_{1} \geqslant \lambda_{2} \geqslant \cdots \geqslant \lambda_{r}>0, \quad \lambda_{r+1}=\lambda_{r+2}=\cdots=\lambda_{n}=0\tag{4} λ1​⩾λ2​⩾⋯⩾λr​>0,λr+1​=λr+2​=⋯=λn​=0(4)
对应地有
σ 1 ⩾ σ 2 ⩾ ⋯ ⩾ σ r > 0 , σ r + 1 = σ r + 2 = ⋯ = σ n = 0 (5) \begin{array}{l} \sigma_{1} \geqslant \sigma_{2} \geqslant \cdots \geqslant \sigma_{r}>0, \quad \sigma_{r+1}=\sigma_{r+2}=\cdots=\sigma_{n}=0 \\ \end{array}\tag{5} σ1​⩾σ2​⩾⋯⩾σr​>0,σr+1​=σr+2​=⋯=σn​=0​(5)

V 1 = [ ν 1 ν 2 ⋯ ν r ] , V 2 = [ ν r + 1 ν r + 2 ⋯ ν n ] V_{1}=\left[\begin{array}{llll} \nu_{1} & \nu_{2} & \cdots & \nu_{r} \end{array}\right], \quad V_{2}=\left[\begin{array}{llll} \nu_{r+1} & \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 ] (6) V=\left[\begin{array}{ll} V_{1} & V_{2} \end{array}\right]\tag{6} V=[V1​​V2​​](6)
这就是矩阵 A A A 的奇异值分解中的 n n n 阶正交矩阵 V V V 。


Σ 1 = [ σ 1 σ 2 ⋱ σ r ] \Sigma_{1}=\left[\begin{array}{llll} \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 ] (7) \Sigma=\left[\begin{array}{cc} \Sigma_{1} & 0 \\ 0 & 0 \end{array}\right]\tag{7} Σ=[Σ1​0​00​](7)
这就是矩阵 A A A 的奇异值分解中的 m × n m \times n m×n 矩形对角矩阵 Σ \Sigma Σ 。

下面推出后面要用到的一个公式。在式 (6) 中, V 2 V_{2} V2​ 的列向量是 A T A A^{\mathrm{T}} A ATA 对应于特征值为 0 的特征向量。因此
A T A v j = 0 , j = r + 1 , ⋯   , n (8) A^{\mathrm{T}} A v_{j}=0, \quad j=r+1, \cdots, n\tag{8} ATAvj​=0,j=r+1,⋯,n(8)
于是, 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 (9) A V_{2}=0\tag{9} AV2​=0(9)
由于 V V V 是正交矩阵,由式 (6) 可得
I = V V T = V 1 V 1 T + V 2 V 2 T                                ( 10 ) A = A I = A V 1 V 1 T + A V 2 V 2 T = A V 1 V 1 T            ( 11 ) \begin{array}{c} I=V V^{\mathrm{T}}=V_{1} V_{1}^{\mathrm{T}}+V_{2} V_{2}^{\mathrm{T}} ~~~~~~~~~~~~~~~~~~~~ ~~~~~~~~~~ (10)\\ A=A I=A V_{1} V_{1}^{\mathrm{T}}+A V_{2} V_{2}^{\mathrm{T}}=A V_{1} V_{1}^{\mathrm{T}}~~~~~~~~~~ (11) \end{array} I=VVT=V1​V1T​+V2​V2T​                              (10)A=AI=AV1​V1T​+AV2​V2T​=AV1​V1T​          (11)​
(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 ] (5) \begin{array}{c} 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{array}\tag{5} uj​=σj​1​Avj​,j=1,2,⋯,rU1​=[u1​​u2​​⋯​ur​​]​(5)
则有
A V 1 = U 1 Σ 1 (6) A V_{1}=U_{1} \Sigma_{1}\tag{6} AV1​=U1​Σ1​(6)
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 ) = σ j σ i v i T v j = δ i j , i = 1 , 2 , ⋯   , r ; j = 1 , 2 , ⋯   , r (7) \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{\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}\tag{7} uiT​uj​​=(σi​1​viT​AT)(σj​1​Avj​)=σi​σj​1​viT​(ATAvj​)=σi​σj​​viT​vj​=δij​,i=1,2,⋯,r;j=1,2,⋯,r​(7)
由式 (5) 和式 (7) 可知, u 1 , u 2 , ⋯   , u r u_{1}, u_{2}, \cdots, u_{r} u1​,u2​,⋯,ur​ 构成 A A A 的列空间的一组标准正交基, 列空间的维数为 r r_{} 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 ] (8) \begin{array}{l} 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{array}\tag{8} U2​=[ur+1​​ur+2​​⋯​um​​]U=[U1​​U2​​]​(8)
则 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 存在奇异值分解。   \large\color{magenta}{\boxed{\color{magenta}{~} }}  ​

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

定理 1给出的奇异值分解
A = U Σ V T A=U \Sigma V^{\mathrm{T}} A=UΣVT
又称为矩阵的完全奇异值分解(full singular value decomposition)。实际常用的是奇异值分解的紧奏形式和截断形式。紧奇异值分解是与原始矩阵等秩的奇异值分解,截断奇异值分解是比原始矩阵低秩的奇异值分解。

紧奇异值分解

定 义 2 \large\color{magenta}{\boxed{\color{brown}{定义 2} }} 定义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 (9) A=U_{r} \Sigma_{r} V_{r}^{\mathrm{T}}\tag{9} A=Ur​Σr​VrT​(9)
其中 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 \Large\color{violet}{例2} 例2 由例1给出的矩阵 A A A的秩 r = 3 r= 3 r=3,
A = [ 1 0 0 0 0 0 0 4 0 3 0 0 0 0 0 0 2 0 0 0 ] A=\left[\begin{array}{llll} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 4 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 \end{array}\right] A=⎣⎢⎢⎢⎢⎡​10002​00300​00000​04000​⎦⎥⎥⎥⎥⎤​
A A A 的紧奇异值分解是
A = U r Σ r V r T A=U_{r} \Sigma_{r} V_{r}^{\mathrm{T}} A=Ur​Σr​VrT​
其中
U r = [ 0 0 0.2 1 0 0 0 1 0 0 0 0 0 0 0.8 ] , Σ r = [ 4 0 0 0 3 0 0 0 5 ] , V r T = [ 0 0 0 1 0 1 0 0 1 0 0 0 ] U_{r}=\left[\begin{array}{ccc} 0 & 0 & \sqrt{0.2} \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & \sqrt{0.8} \end{array}\right], \quad \Sigma_{r}=\left[\begin{array}{ccc} 4 & 0 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & \sqrt{5} \end{array}\right], \quad V_{r}^{\mathrm{T}}=\left[\begin{array}{cccc} 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \end{array}\right] Ur​=⎣⎢⎢⎢⎢⎡​01000​00100​0.2 ​0000.8 ​​⎦⎥⎥⎥⎥⎤​,Σr​=⎣⎡​400​030​005 ​​⎦⎤​,VrT​=⎣⎡​001​010​000​100​⎦⎤​

截断奇异值分解

在矩阵的奇异值分解中,只取最大的 k k k 个奇异值 ( k < r , r (k<r, r (k<r,r 为矩阵的秩 ) ) ) 对应的部分,就得到矩阵的截断奇异值分解。实际应用中提到矩阵的奇异值分解时, 通常指截断奇异值分解。

定 义 3 \large\color{magenta}{\boxed{\color{brown}{定义 3} }} 定义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 (10) A \approx U_{k} \Sigma_{k} V_{k}^{\mathrm{T}}\tag{10} A≈Uk​Σk​VkT​(10)
其中 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 的秩低。

例 3 \Large\color{violet}{例3} 例3 由例1给出的矩阵 A A A
A = [ 1 0 0 0 0 0 0 4 0 3 0 0 0 0 0 0 2 0 0 0 ] A=\left[\begin{array}{llll} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 4 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 \end{array}\right] A=⎣⎢⎢⎢⎢⎡​10002​00300​00000​04000​⎦⎥⎥⎥⎥⎤​
的秩为 3,若取 k = 2 k=2 k=2 则其截断奇异值分解是
A ≈ A 2 = U 2 Σ 2 V 2 T A \approx A_{2}=U_{2} \Sigma_{2} V_{2}^{\mathrm{T}} A≈A2​=U2​Σ2​V2T​
其中
U 2 = [ 0 0 1 0 0 1 0 0 0 0 ] , Σ 2 = [ 4 0 0 3 ] , V 2 T = [ 0 0 0 1 0 1 0 0 ] A 2 = U 2 Σ 2 V 2 T = [ 0 0 0 0 0 0 0 4 0 3 0 0 0 0 0 0 0 0 0 0 ] \begin{array}{l} U_{2}=\left[\begin{array}{ll} 0 & 0 \\ 1 & 0 \\ 0 & 1 \\ 0 & 0 \\ 0 & 0 \end{array}\right], \quad \Sigma_{2}=\left[\begin{array}{ll} 4 & 0 \\ 0 & 3 \end{array}\right], \quad V_{2}^{\mathrm{T}}=\left[\begin{array}{llll} 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{array}\right] \\ A_{2}=U_{2} \Sigma_{2} V_{2}^{\mathrm{T}}=\left[\begin{array}{llll} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 4 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{array}\right] \end{array} U2​=⎣⎢⎢⎢⎢⎡​01000​00100​⎦⎥⎥⎥⎥⎤​,Σ2​=[40​03​],V2T​=[00​01​00​10​]A2​=U2​Σ2​V2T​=⎣⎢⎢⎢⎢⎡​00000​00300​00000​04000​⎦⎥⎥⎥⎥⎤​​
这里的 U 2 , V 2 U_{2}, V_{2} U2​,V2​ 是例 1 的 U U U 和 V V V 的前 2 列, Σ 2 \Sigma_{2} Σ2​ 是 Σ \Sigma Σ 的前 2 行前 2 列。 A 2 A_{2} A2​ 与 A A A 比 较, A A A 的元素 1 和 2 在 A 2 A_{2} A2​ 中均变成 0 。

在实际应用中,常常需要对矩阵的数据进行压缩,将其近似表示,奇异值分解提供了一种方法。后面将要叙述,奇异值分解是在平方损失(弗罗贝尼乌斯范数)意义下对矩阵的最优近似。紧奇异值分解对应着无损压缩,截断奇异值分解对应着有损压缩。

几何解析

从线性变换的角度理解奇异值分解, m × n m \times n m×n 矩阵 A A A 表示从 n n n 维空间 R n \mathbf{R}^{n} Rn 到 m m m 维 空间 R m \mathbf{R}^{m} Rm 的一个线性变换,
T : x → A x T: x \rightarrow A x T:x→Ax
x ∈ R n , A x ∈ R m , x x \in \mathbf{R}^{n}, A x \in \mathbf{R}^{m}, x x∈Rn,Ax∈Rm,x 和 A x A x Ax 分别是各自空间的向量。线性变换可以分解为三个简单的变换: 一个坐标系的旋转或反射变换、一个坐标轴的缩放变换、另一个坐标系的旋转或反射变换。奇异值定理保证这种分解一定存在。这就是奇异值分解的几何解释。

对矩阵 A A A 进行奇异值分解,得到 A = U Σ V T , V A=U \Sigma V^{\mathrm{T}}, V A=UΣVT,V 和 U U U 都是正交矩阵,所以 V V V 的 列向量 v 1 , v 2 , ⋯   , v n v_{1}, v_{2}, \cdots, v_{n} v1​,v2​,⋯,vn​ 构成 R n \mathbf{R}^{n} Rn 空间的一组标准正交基,表示 R n \mathbf{R}^{n} Rn 中的正交坐标系的旋转或反射变换; U U U 的列向量 u 1 , u 2 , ⋯   , u m u_{1}, u_{2}, \cdots, u_{m} u1​,u2​,⋯,um​ 构成 R m \mathbf{R}^{m} Rm 空间的一组标准正交基,表示 R m \mathbf{R}^{m} Rm 中的正交坐标系的旋转或反射变换; Σ \Sigma Σ 的对角元素 σ 1 , σ 2 , ⋯   , σ n \sigma_{1}, \sigma_{2}, \cdots, \sigma_{n} σ1​,σ2​,⋯,σn​ 是一组非负实数,表示 R n \mathbf{R}^{n} Rn 中的原始正交坐标系坐标轴的 σ 1 , σ 2 , ⋯   , σ n \sigma_{1}, \sigma_{2}, \cdots, \sigma_{n} σ1​,σ2​,⋯,σn​ 倍的缩放变换。

任意一个向量 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 。图 1 给出直观的几何解释。原始空间的标准正交基(红色与黄色), 经过坐标系的旋转变换 V T V^{\mathrm{T}} VT 、坐标轴的缩放变换 Σ \Sigma Σ (黑色 σ 1 , σ 2 \sigma_{1}, \sigma_{2} σ1​,σ2​ )、 坐标系的旋转变换 U U U ,得到和经过线性变换 A A A 等价的结果。

SVD奇异值分解

图 1 奇 异 值 分 解 的 几 何 解 释 图 1 奇异值分解的几何解释 图1奇异值分解的几何解释

下面通过一个例子直观地说明奇异值分解的几何意义。

例 4 \Large\color{violet}{例4} 例4 给定一个2阶矩阵
A = [ 3 1 2 1 ] A=\left[\begin{array}{ll} 3 & 1 \\ 2 & 1 \end{array}\right] A=[32​11​]
其奇异值分解为
U = [ 0.8174 − 0.5760 0.5760 0.8174 ] , Σ = [ 3.8643 0 0 0.2588 ] , V T = [ 0.9327 0.3606 − 0.3606 0.9327 ] U=\left[\begin{array}{cc} 0.8174 & -0.5760 \\ 0.5760 & 0.8174 \end{array}\right], \quad \Sigma=\left[\begin{array}{ll} 3.8643 & 0 \\ 0 & 0.2588 \end{array}\right], \quad V^{\mathrm{T}}=\left[\begin{array}{ccc} 0.9327 & 0.3606 \\ -0.3606 & 0.9327 \end{array}\right] U=[0.81740.5760​−0.57600.8174​],Σ=[3.86430​00.2588​],VT=[0.9327−0.3606​0.36060.9327​]
观察基于矩阵 A A A 的奇异值分解将 R 2 \mathbf{R}^{2} R2 的标准正交基
e 1 = [ 1 0 ] , e 2 = [ 0 1 ] e_{1}=\left[\begin{array}{l} 1 \\ 0 \end{array}\right], \quad e_{2}=\left[\begin{array}{l} 0 \\ 1 \end{array}\right] e1​=[10​],e2​=[01​]
进行线性转换的情况。

首先, V T V^{\mathrm{T}} VT 表示一个旋转变换, 将标准正交基 e 1 , e 2 e_{1}, e_{2} e1​,e2​ 旋转, 得到向量 V T e 1 , V T e 2 V^{\mathrm{T}} e_{1}, V^{\mathrm{T}} e_{2} VTe1​,VTe2​ :
V T e 1 = [ 0.9327 − 0.3606 ] , V T e 2 = [ 0.3606 0.9327 ] V^{\mathrm{T}} e_{1}=\left[\begin{array}{r} 0.9327 \\ -0.3606 \end{array}\right], \quad V^{\mathrm{T}} e_{2}=\left[\begin{array}{l} 0.3606 \\ 0.9327 \end{array}\right] VTe1​=[0.9327−0.3606​],VTe2​=[0.36060.9327​]
其次, Σ \Sigma Σ 表示一个缩放变换,将向量 V T e 1 , V T e 2 V^{\mathrm{T}} e_{1}, V^{\mathrm{T}} e_{2} VTe1​,VTe2​ 在坐标轴方向缩放 σ 1 \sigma_{1} σ1​ 倍和 σ 2 \sigma_{2} σ2​倍,得到向量 Σ V T e 1 , Σ V T e 2 \Sigma V^{\mathrm{T}} e_{1}, \Sigma V^{\mathrm{T}} e_{2} ΣVTe1​,ΣVTe2​ :
Σ V T e 1 = [ 3.6042 − 0.0933 ] , Σ V T e 2 = [ 1.3935 0.2414 ] \Sigma V^{\mathrm{T}} e_{1}=\left[\begin{array}{r} 3.6042 \\ -0.0933 \end{array}\right], \quad \Sigma V^{\mathrm{T}} e_{2}=\left[\begin{array}{l} 1.3935 \\ 0.2414 \end{array}\right] ΣVTe1​=[3.6042−0.0933​],ΣVTe2​=[1.39350.2414​]
最后, U U U 表示一个旋转变换,再将向量 Σ V T e 1 , Σ V T e 2 \Sigma V^{\mathrm{T}} e_{1}, \Sigma V^{\mathrm{T}} e_{2} ΣVTe1​,ΣVTe2​ 旋转,得到向量 U Σ V T e 1 , U Σ V T e 2 , U \Sigma V^{\mathrm{T}} e_{1}, U \Sigma V^{\mathrm{T}} e_{2}, UΣVTe1​,UΣVTe2​, 也就是向量 A e 1 A e_{1} Ae1​ 和 A e 2 : A e_{2}: Ae2​:
A e 1 = U Σ V T e 1 = [ 3 2 ] , A e 2 = U Σ V T e 2 [ 1 1 ] A e_{1}=U \Sigma V^{\mathrm{T}} e_{1}=\left[\begin{array}{l} 3 \\ 2 \end{array}\right], \quad A e_{2}=U \Sigma V^{\mathrm{T}} e_{2}\left[\begin{array}{l} 1 \\ 1 \end{array}\right] Ae1​=UΣVTe1​=[32​],Ae2​=UΣVTe2​[11​]
综上,矩阵的奇异值分解也可以看作是将其对应的线性变换分解为旋转变换、缩放变换及旋转变换的组合。根据定理1,这个变换的组合一定存在。

代码实现

def draw_arrow(origin, e1, e2):
    size = 3
    alpha = 0.6
    head_width = 0.2
    head_length = 0.3
    fig = plt.figure(figsize=(size, size))
    ax = fig.add_subplot(1, 1, 1, aspect=1)
    circle1 = plt.Circle((0.5, 0.5), 0.5,
                            color="pink", fill=True, alpha=alpha)
    ax.add_artist(circle1)
    plt.arrow(origin[0], origin[1], e1[0], e1[1], fc="r", ec="r",
                alpha=alpha, head_width=head_width, head_length=head_length)
    plt.arrow(origin[0], origin[1], e2[0], e2[1], fc="y", ec="y",
                alpha=alpha, head_width=head_width, head_length=head_length)

    plt.axis('off')
    return fig

def e_15_4():

    e1 = np.array([1, 0])
    e2 = np.array([0, 1])

    origin = np.array([0.5, 0.5])
    fig = draw_arrow(origin, e1, e2)
    # folder = sys.path[0]
    # plt.savefig(folder+"/e15-4.png")
    # img = plt.imread(folder+"/e15-4.png")
    plt.axis('on')
    # plt.imshow(img)
    plt.show()

    A = np.array([[3, 1],
                    [2, 1]])
    u, s, vh = np.linalg.svd(A)
    arr1 = np.dot(vh, e1)
    arr2 = np.dot(vh, e2)
    fig = draw_arrow(origin, arr1, arr2)
    plt.axis('on')
    plt.show()

    arr1 = np.dot(s*np.eye(2), arr1)
    arr2 = np.dot(s*np.eye(2), arr2)
    fig = draw_arrow(origin, arr1, arr2)
    plt.axis('on')
    plt.show()

    arr1 = np.dot(u, arr1)
    arr2 = np.dot(u, arr2)
    fig = draw_arrow(origin, arr1, arr2)
    plt.axis('on')
    plt.show()

    print(40*"*"+"u"+40*"*")
    print(u)
    print(40*"*"+"s"+40*"*")
    print(s)
    print(s*np.eye(2))
    print(40*"*"+"vh"+40*"*")
    print(vh)
    print(40*"*"+"ATA"+40*"*")
    print(np.linalg.eig(np.dot(A.T, A)))
    print(np.linalg.eigvals(np.dot(A.T, A)))
    print(np.sqrt(np.linalg.eigvals(np.dot(A.T, A))))

    print(40*"*")
    print(vh)
    vhe1 = np.dot(vh, e1)
    vhe2 = np.dot(vh, e2)

    print(40*"*"+"vhe"+40*"*")
    print(vhe1)
    print(vhe2)
    svhe1 = np.dot(s*np.eye(2), vhe1)
    svhe2 = np.dot(s*np.eye(2), vhe2)

    print(40*"*"+"svhe"+40*"*")
    print(svhe1)
    print(svhe2)
    
    print(40*"*"+"usvhe"+40*"*")
    usvhe1 = np.dot(u, svhe1)
    usvhe2 = np.dot(u, svhe2)
    print(usvhe1)
    print(usvhe2)

主要性质

(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 (11) \begin{array}{l} 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{array}\tag{11} ATA=(UΣVT)T(UΣVT)=V(ΣTΣ)VTAAT=(UΣVT)(UΣVT)T=U(ΣΣT)UT​(11)
也就是说,矩阵 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 Σ (12) A V=U \Sigma\tag{12} AV=UΣ(12)
比较这一等式两端的第 j j j 列,得到
A v j = σ j u j , j = 1 , 2 , ⋯   , n (13) A v_{j}=\sigma_{j} u_{j}, \quad j=1,2, \cdots, n\tag{13} Avj​=σj​uj​,j=1,2,⋯,n(13)
这是矩阵 A A A 的右奇异向量和奇异值、左奇异向量的关系。

类似地,由
A T U = V Σ T (14) A^{\mathrm{T}} U=V \Sigma^{\mathrm{T}}\tag{14} ATU=VΣT(14)
得到
A T u j = σ j v j , j = 1 , 2 , ⋯   , n A T u j = 0 , j = n + 1 , n + 2 , ⋯   , m (15) \begin{array}{c} 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{array}\tag{15} ATuj​=σj​vj​,j=1,2,⋯,nATuj​=0,j=n+1,n+2,⋯,m​(15)
这是矩阵 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) 的 一组标准正交基。

奇异值分解的计算

奇异值分解基本定理证明的过程蕴含了奇异值分解的计算方法。矩阵 A A A 的奇异值分解可以通过求对称矩阵 A T A A^{\mathrm{T}} A ATA 的特征值和特征向量得到。 A T A A^{\mathrm{T}} A ATA 的特征向量构成正交矩阵 V V V 的列 ; A T A ; A^{\mathrm{T}} A ;ATA 的特征值 λ j \lambda_{j} λj​ 的平方根为奇异值 σ i , \sigma_{i}, σi​, 即
σ j = λ j , j = 1 , 2 , ⋯   , n \sigma_{j}=\sqrt{\lambda_{j}}, \quad j=1,2, \cdots, n σj​=λj​ ​,j=1,2,⋯,n
对其由大到小排列作为对角线元素,构成对角矩阵 Σ \Sigma Σ; 求正奇异值对应的左奇异向量,再求扩充的 A T A^{\mathrm{T}} AT 的标准正交基,构成正交矩阵 U U U 的列。从而得到 A A A 的奇异值分解 A = U Σ V T A=U \Sigma V^{\mathrm{T}} A=UΣVT。

给定 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 − λ E ) x = 0 (W-\lambda E) x=0 (W−λE)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
下面通过一个简单的例题,说明奇异值分解的算法。

例 5 \Large\color{violet}{例5} 例5 试求矩阵
A = [ 1 1 2 2 0 0 ] A=\left[\begin{array}{ll} 1 & 1 \\ 2 & 2 \\ 0 & 0 \end{array}\right] A=⎣⎡​120​120​⎦⎤​
的奇异值分解。

(1)求矩阵 A T A A^{\mathrm{T}} A ATA 的特征值和特征向量.

求对称矩阵 A T A A^{\mathrm{T}} A ATA
A T A = [ 1 2 0 1 2 0 ] [ 1 1 2 2 0 0 ] = [ 5 5 5 5 ] A^{\mathrm{T}} A=\left[\begin{array}{lll} 1 & 2 & 0 \\ 1 & 2 & 0 \end{array}\right]\left[\begin{array}{ll} 1 & 1 \\ 2 & 2 \\ 0 & 0 \end{array}\right]=\left[\begin{array}{ll} 5 & 5 \\ 5 & 5 \end{array}\right] ATA=[11​22​00​]⎣⎡​120​120​⎦⎤​=[55​55​]
特征值 λ \lambda λ 和特征向量 x x x 满足特征方程
( A T A − λ E ) x = 0 \left(A^{\mathrm{T}} A-\lambda E\right) x=0 (ATA−λE)x=0
得到齐次线性方程组
{ ( 5 − λ ) x 1 + 5 x 2 = 0 5 x 1 + ( 5 − λ ) x 2 = 0 \left\{\begin{array}{cc} (5-\lambda) x_{1}+ & 5 x_{2}=0 \\ 5 x_{1}+ & (5-\lambda) x_{2}=0 \end{array}\right. {(5−λ)x1​+5x1​+​5x2​=0(5−λ)x2​=0​
该方程组有非零解的充要条件是
∣ 5 − λ 5 5 5 − λ ∣ = 0 \left|\begin{array}{cc} 5-\lambda & 5 \\ 5 & 5-\lambda \end{array}\right|=0 ∣∣∣∣​5−λ5​55−λ​∣∣∣∣​=0

λ 2 − 10 λ = 0 \lambda^{2}-10 \lambda=0 λ2−10λ=0
解此方程,得矩阵 A T A A^{\mathrm{T}} A ATA 的特征值 λ 1 = 10 \lambda_{1}=10 λ1​=10 和 λ 2 = 0 \lambda_{2}=0 λ2​=0 。

将特征值 λ 1 = 10 \lambda_{1}=10 λ1​=10 代入线性方程组,得到对应的单位特征向量
v 1 = [ 1 2 1 2 ] v_{1}=\left[\begin{array}{c} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{array}\right] v1​=[2 ​1​2 ​1​​]
同样得到特征值 λ 2 = 0 \lambda_{2}=0 λ2​=0 对应的单位特征向量
v 2 = [ 1 2 − 1 2 ] v_{2}=\left[\begin{array}{c} \frac{1}{\sqrt{2}} \\ -\frac{1}{\sqrt{2}} \end{array}\right] v2​=[2 ​1​−2 ​1​​]
(2)求正交矩阵 V V V.

构造正交矩阵 V V V
V = [ 1 2 1 2 1 2 − 1 2 ] V=\left[\begin{array}{cc} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & -\frac{1}{\sqrt{2}} \end{array}\right] V=[2 ​1​2 ​1​​2 ​1​−2 ​1​​]
(3)求对角矩阵 Σ \Sigma Σ.

奇异值为 σ 1 = λ 1 = 10 \sigma_{1}=\sqrt{\lambda_{1}}=\sqrt{10} σ1​=λ1​ ​=10 ​ 和 σ 2 = 0 \sigma_{2}=0 σ2​=0 。构造对角矩阵
Σ = [ 10 0 0 0 0 0 ] \Sigma=\left[\begin{array}{cc} \sqrt{10} & 0 \\ 0 & 0 \\ 0 & 0 \end{array}\right] Σ=⎣⎡​10 ​00​000​⎦⎤​
注意在 Σ \Sigma Σ 中要加上零行向量,使得 Σ \Sigma Σ 能够与 U , V U, V U,V 进行矩阵乘法运算。

(4) 求正交矩阵 U U U .

基于 A A A 的正奇异值计算得到列向量 u 1 u_{1} u1​
u 1 = 1 σ 1 A v 1 = 1 10 [ 1 1 2 2 0 0 ] [ 1 2 1 2 ] = [ 1 5 2 5 0 ] u_{1}=\frac{1}{\sigma_{1}} A v_{1}=\frac{1}{\sqrt{10}}\left[\begin{array}{cc} 1 & 1 \\ 2 & 2 \\ 0 & 0 \end{array}\right]\left[\begin{array}{c} \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} \end{array}\right]=\left[\begin{array}{c} \frac{1}{\sqrt{5}} \\ \frac{2}{\sqrt{5}} \\ 0 \end{array}\right] u1​=σ1​1​Av1​=10 ​1​⎣⎡​120​120​⎦⎤​[2 ​1​2 ​1​​]=⎣⎡​5 ​1​5 ​2​0​⎦⎤​
列向量 u 2 , u 3 u_{2}, u_{3} u2​,u3​ 是 A T A^{\mathrm{T}} AT 的零空间 N ( A T ) N\left(A^{\mathrm{T}}\right) N(AT) 的一组标准正交基。为此,求解以下线性 方程组
A T x = [ 1 2 0 1 2 0 ] [ x 1 x 2 x 3 ] = [ 0 0 ] A^{\mathrm{T}} x=\left[\begin{array}{lll} 1 & 2 & 0 \\ 1 & 2 & 0 \end{array}\right]\left[\begin{array}{l} x_{1} \\ x_{2} \\ x_{3} \end{array}\right]=\left[\begin{array}{l} 0 \\ 0 \end{array}\right] ATx=[11​22​00​]⎣⎡​x1​x2​x3​​⎦⎤​=[00​]

x 1 + 2 x 2 + 0 x 3 = 0 x 1 = − 2 x 2 + 0 x 3 \begin{array}{c} x_{1}+2 x_{2}+0 x_{3}=0 \\ x_{1}=-2 x_{2}+0 x_{3} \end{array} x1​+2x2​+0x3​=0x1​=−2x2​+0x3​​
分别取 ( x 2 , x 3 ) \left(x_{2}, x_{3}\right) (x2​,x3​) 为 ( 1 , 0 ) (1,0) (1,0) 和 ( 0 , 1 ) , (0,1), (0,1), 得到 N ( A T ) N\left(A^{\mathrm{T}}\right) N(AT) 的基
( − 2 , 1 , 0 ) T , ( 0 , 0 , 1 ) T (-2,1,0)^{\mathrm{T}}, \quad(0,0,1)^{\mathrm{T}} (−2,1,0)T,(0,0,1)T
N ( A T ) N\left(A^{\mathrm{T}}\right) N(AT) 的一组标准正交基是
u 2 = ( − 2 5 , 1 5 , 0 ) T , u 3 = ( 0 , 0 , 1 ) T u_{2}=\left(-\frac{2}{\sqrt{5}}, \frac{1}{\sqrt{5}}, 0\right)^{\mathrm{T}}, \quad u_{3}=(0,0,1)^{\mathrm{T}} u2​=(−5 ​2​,5 ​1​,0)T,u3​=(0,0,1)T
构造正交矩阵 U U U
U = [ 1 5 − 2 5 0 2 5 1 5 0 0 0 1 ] U=\left[\begin{array}{ccc} \frac{1}{\sqrt{5}} & -\frac{2}{\sqrt{5}} & 0 \\ \frac{2}{\sqrt{5}} & \frac{1}{\sqrt{5}} & 0 \\ 0 & 0 & 1 \end{array}\right] U=⎣⎡​5 ​1​5 ​2​0​−5 ​2​5 ​1​0​001​⎦⎤​
(5)矩阵 A A A 的奇异值分解
A = U Σ V T = [ 1 5 − 2 5 0 2 5 1 5 0 0 0 1 ] [ 10 0 0 0 0 0 ] [ 1 2 1 2 1 2 − 1 2 ] A=U \Sigma V^{\mathrm{T}}=\left[\begin{array}{ccc} \frac{1}{\sqrt{5}} & -\frac{2}{\sqrt{5}} & 0 \\ \frac{2}{\sqrt{5}} & \frac{1}{\sqrt{5}} & 0 \\ 0 & 0 & 1 \end{array}\right]\left[\begin{array}{cc} \sqrt{10} & 0 \\ 0 & 0 \\ 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] A=UΣVT=⎣⎡​5 ​1​5 ​2​0​−5 ​2​5 ​1​0​001​⎦⎤​⎣⎡​10 ​00​000​⎦⎤​[2 ​1​2 ​1​​2 ​1​−2 ​1​​]
上面的算法和例题只是为了说明计算的过程,并不是实际应用中的算法。可以看 出,奇异值分解算法关键在于 A T A A^{\mathrm{T}} A ATA 的特征值的计算。实际应用的奇异值分解算法是 通过求 A T A A^{\mathrm{T}} A ATA 的特征值进行,但不直接计算 A T A ∘ A^{\mathrm{T}} A_{\circ} ATA∘​ 按照这个思路产生了许多矩阵奇异 值分解的有效算法.

奇异值分解与矩阵近似

F-范数

奇异值分解也是一种矩阵近似的方法, 这个近似是在F-范数 (Frobenius norm)意义下的近似。矩阵的F-范数是向量的 L 2 L_{2} L2​ 范数的直接推广,对应着机器学习中的平方损失函数。

定 义 4 \large\color{magenta}{\boxed{\color{brown}{定义 4} }} 定义4​ (F-范数) 设矩阵 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 的F-范数为
∥ A ∥ F = ( ∑ i = 1 m ∑ j = 1 n ( a i j ) 2 ) 1 2 (16) \|A\|_{F}=\left(\sum_{i=1}^{m} \sum_{j=1}^{n}\left(a_{i j}\right)^{2}\right)^{\frac{1}{2}}\tag{16} ∥A∥F​=(i=1∑m​j=1∑n​(aij​)2)21​(16)
引 理 1 \large\color{magenta}{\boxed{\color{brown}{引理 1} }} 引理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 (17) \|A\|_{F}=\left(\sigma_{1}^{2}+\sigma_{2}^{2}+\cdots+\sigma_{n}^{2}\right)^{\frac{1}{2}}\tag{17} ∥A∥F​=(σ12​+σ22​+⋯+σn2​)21​(17)
【证明】 一般地,若 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 ∥ 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}\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​∥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​
  \large\color{magenta}{\boxed{\color{magenta}{~} }}  ​

矩阵的最优近似

奇异值分解是在平方损失(F-范数)意义下对矩阵的最优近似,即数据压缩。

定 理 2 \large\color{magenta}{\boxed{\color{brown}{定理 2} }} 定理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 (18) \|A-X\|_{F}=\min _{S \in \mathcal{M}}\|A-S\|_{F}\tag{18} ∥A−X∥F​=S∈Mmin​∥A−S∥F​(18)
称矩阵 X X X 为矩阵 A A A 在F-范数意义下的最优近似。

应用这个结果, 通过矩阵 A A A 的奇异值分解求出近似矩阵 X X X 。

定 理 3 \large\color{magenta}{\boxed{\color{brown}{定理 3} }} 定理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 \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 (19) \|A-X\|_{F}=\min _{S \in \mathcal{M}}\|A-S\|_{F}\tag{19} ∥A−X∥F​=S∈Mmin​∥A−S∥F​(19)

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

特别地, 若 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}{llllll} \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 ′ ∥ 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​
【证明】 \quad 令 X ∈ M X \in \mathcal{M} X∈M 为满足式 (19) 的一个矩阵。由于
∥ 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​
于是式 (20) 成立。

设 X X X 的奇异值分解为 Q Ω P T Q \Omega P^{\mathrm{T}} QΩPT ,其中
Ω = [ ω 1 ⋱ 0 ω k 0 0 ⋱ 0 ] = [ Ω k 0 0 0 ] \Omega=\left[\begin{array}{llllll} \omega_{1} & & & & & \\ & \ddots & & & 0 & \\ & & \omega_{k} & & & \\ & & & 0 & & & \\ & 0 & & & \ddots \\ & & & & & 0 \end{array}\right]=\left[\begin{array}{cc} \Omega_{k} & 0 \\ 0 & 0 \end{array}\right] Ω=⎣⎢⎢⎢⎢⎢⎢⎡​ω1​​⋱0​ωk​​0​0⋱​0​​⎦⎥⎥⎥⎥⎥⎥⎤​=[Ωk​0​00​]

定理 3 表明,在秩不超过 k k k 的 m × n m \times n m×n 矩阵的集合中,存在矩阵 A A A 的F-范数意义下的最优近似矩阵 X ∘    A ′ = U Σ ′ V T X_{\circ}~~ A^{\prime}=U \Sigma^{\prime} V^{\mathrm{T}} X∘​  A′=UΣ′VT 是达到最优值的一个矩阵。

前面定义了矩阵的紧奇异值分解与截断奇异值分解。事实上紧奇异值分解是在F-范数意义下的无损压缩,截断奇异值分解是有损压缩。截断奇异值分解得 到的矩阵的秩为 k , k, k, 通常远小于原始矩阵的秩 r , r, r, 所以是由低秩矩阵实现了对原始矩阵的压缩。

矩阵的外积展开式

下面介绍利用外积展开式对矩阵 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{array}{l} U \Sigma=\left[\begin{array}{cccc} \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{array} 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 (30) 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}}\tag{30} A=σ1​u1​v1T​+σ2​u2​v2T​+⋯+σn​un​vnT​(30)
式 (30) 称为矩阵 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 (31) A=\sum_{k=1}^{n} A_{k}=\sum_{k=1}^{n} \sigma_{k} u_{k} v_{k}^{\mathrm{T}}\tag{31} A=k=1∑n​Ak​=k=1∑n​σk​uk​vkT​(31)
其中 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 矩阵。式 (31) 将矩阵 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 矩阵在F-范数意义下 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 矩阵中在F-范数意义下 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 的矩阵中在F-范数意义下 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 有很好的近似。

例 6 \Large\color{violet}{例6} 例6 由例1给出的矩阵 A A A
A = [ 1 0 0 0 0 0 0 4 0 3 0 0 0 0 0 0 2 0 0 0 ] A=\left[\begin{array}{llll} 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 4 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 2 & 0 & 0 & 0 \end{array}\right] A=⎣⎢⎢⎢⎢⎡​10002​00300​00000​04000​⎦⎥⎥⎥⎥⎤​
的秩为 3 ,求 A A A 的秩为 2 的最优近似。

【解】 由例 3 可知
u 1 = [ 0 1 0 0 0 ] , u 2 = [ 0 0 1 0 0 ] , v 1 = [ 0 0 0 1 ] , v 2 = [ 0 1 0 0 ] σ 1 = 4 , σ 2 = 3 \begin{array}{l} u_{1}=\left[\begin{array}{l} 0 \\ 1 \\ 0 \\ 0 \\ 0 \end{array}\right], \quad u_{2}=\left[\begin{array}{l} 0 \\ 0 \\ 1 \\ 0 \\ 0 \end{array}\right], \quad v_{1}=\left[\begin{array}{l} 0 \\ 0 \\ 0 \\ 1 \end{array}\right], \quad v_{2}=\left[\begin{array}{c} 0 \\ 1 \\ 0 \\ 0 \end{array}\right] \\ \sigma_{1}=4, \quad \sigma_{2}=3 \end{array} u1​=⎣⎢⎢⎢⎢⎡​01000​⎦⎥⎥⎥⎥⎤​,u2​=⎣⎢⎢⎢⎢⎡​00100​⎦⎥⎥⎥⎥⎤​,v1​=⎣⎢⎢⎡​0001​⎦⎥⎥⎤​,v2​=⎣⎢⎢⎡​0100​⎦⎥⎥⎤​σ1​=4,σ2​=3​
于是得到
A 2 = σ 1 u 1 v 1 T + σ 2 u 2 v 2 T = [ 0 0 0 0 0 0 0 4 0 3 0 0 0 0 0 0 0 0 0 0 ] A_{2}=\sigma_{1} u_{1} v_{1}^{\mathrm{T}}+\sigma_{2} u_{2} v_{2}^{\mathrm{T}}=\left[\begin{array}{llll} 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 4 \\ 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \end{array}\right] A2​=σ1​u1​v1T​+σ2​u2​v2T​=⎣⎢⎢⎢⎢⎡​00000​00300​00000​04000​⎦⎥⎥⎥⎥⎤​
以此矩阵作为 A A A 的最优近似。

def e_15_6(self):
    A = np.array([[1, 0, 0, 0],
                    [0, 0, 0, 4],
                    [0, 3, 0, 0],
                    [0, 0, 0, 0],
                    [2, 0, 0, 0]])
    u, s, vh = np.linalg.svd(A)
    print(u)
    print(s)
    print(vh)
    print(u[:, 0], u[:, 1], vh[0], vh[1])

    # print(np.dot(u[:, 0].reshape(-1, 1), vh[0].reshape(1, -1)))
    # print(np.dot(u[:, 1].reshape(-1, 1), vh[1].reshape(1, -1)))

    A_2 =s[0] * np.dot(u[:, 0].reshape(-1, 1), vh[0].reshape(1, -1)) +s[1] * np.dot(u[:, 1].reshape(-1, 1), vh[1].reshape(1, -1))
    print(A_2)
    # 非方阵求特征值
    print(40*"*"+"ATA Eig Vector"+40*"*")
    print(np.linalg.eigh(np.dot(A.T, A)))
    print(40*"*"+"AAT Eig Vector"+40*"*")
    print(np.linalg.eigh(np.dot(A, A.T)))

参考资料

统计学习方法,李航

机器学习,周志华

上一篇:【论文精炼】 | Revisiting the Continuity of Rotation Representations in Neural Networks | 再次探讨神经网络中旋转表示的连续


下一篇:优化理论12有约束优化---Rosen的梯度投影法和既约梯度法