文章目录
- 奇异值分解(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 T A = I A^{T} A=I ATA=I 的矩阵.
理解正交矩阵 https://zhuanlan.zhihu.com/p/258464098?utm_source=wechat_session- 是正交矩阵,自然满足 A T = A − 1 A^T=A^{-1} AT=A−1
注意:奇异值分解不要求矩阵 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 证明仍然成立。证明由三步完成。
确定 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=[V1V2]这就是矩阵 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] Σ=[Σ1000]这就是矩阵 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} & V_{2}\end{array}\right] V=[V1amp;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} & V_{2}\end{array}\right] V=[V1amp;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=V1V1T+V2V2TA=AI=AV1V1T+AV2V2T=AV1V1T
确定 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=σj1Avj,j=1,2,⋯,r①U1=[u1u2⋯ur]则有
A V 1 = U 1 Σ 1 A V_{1}=U_{1} \Sigma_{1} AV1=U1Σ1A 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]=[u1u2⋯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}② uiTuj=(σi1viTAT)(σj1Avj)=σiσj1viT(ATAvj)=σiσj1viT(σj2vj)=σiσjviTvj=δ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+1ur+2⋯um]U=[U1U2]则 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=[U1U2][Σ1000][V1TV2T]=U1Σ1V1T=AV1V1T=A至此证明了矩阵 A A A 存在奇异值分解。
15.1.2 紧奇异值分解与截断奇异值分解
-
紧奇异值分解
定义 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ΣrVrT 为 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ΣrVrT其中 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 的秩相等。
-
截断奇异值分解
在矩阵的奇异值分解中, 只取最大的 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ΣkVkT 为矩阵 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ΣkVkT其中 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.1.4 主要性质
-
设矩阵 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 的特征值的平方根。
-
在矩阵 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=σjuj,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=σjvj,j=1,2,⋯,nATuj=0,j=n+1,n+2,⋯,m这是矩阵 A A A 的左奇异向量和奇异值、右奇异向量的关系。
-
矩阵 A A A 的奇异值分解中, 奇异值 σ 1 , σ 2 , ⋯ , σ n \sigma_{1}, \sigma_{2}, \cdots, \sigma_{n} σ1,σ2,⋯,σn 是唯一的, 而矩阵 U U U 和 V V V 不 是唯一的。
-
矩阵 A A A 和 Σ \Sigma Σ 的秩相等, 等于正奇异值 σ i \sigma_{i} σi 的个数 r r r (包含重复的奇异值)。
-
矩阵 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
-
首先求 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) 代入特征方程求得对应的特征向量。
-
求 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=[v1v2⋯vn] -
求 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) -
求 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=σj1Avj,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=[u1u2⋯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+1ur+2⋯um]并令
U = [ U 1 U 2 ] U=\left[\begin{array}{ll} U_{1} & U_{2} \end{array}\right] U=[U1U2] -
得到奇异值分解
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∑mj=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∑naiTQTQai=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σk00⋱0⎦⎥⎥⎥⎥⎥⎥⎤=[Σk000]
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[000Σ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=[B11B21B12B22]
其中 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[B110B120]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[B11000]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=[Ik00U1],V2=[Ik00V1]
其中 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] U2TQTAPV2=[Ωk00Λ]
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)[Ωk00Λ](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Σ=[σ1u1σ2u2⋯σnun]VT=⎣⎢⎢⎢⎡v1Tv2T⋮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=σ1u1v1T+σ2u2v2T+⋯+σnunvnT
上式称为矩阵 A A A 的外积展开式, 其中 u k v k T u_{k} v_{k}^{\mathrm{T}} ukvkT 为 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] uivjT=⎣⎢⎢⎢⎡u1iu2i⋮umi⎦⎥⎥⎥⎤[v1jv2j⋯vnj]=⎣⎢⎢⎢⎡u1iv1ju2iv1j⋮umiv1ju1iv2ju2iv2j⋮umiv2j⋯⋯⋯u1ivnju2ivnj⋮umivnj⎦⎥⎥⎥⎤
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∑nAk=k=1∑nσkukvkT
其中
A
k
=
σ
k
u
k
v
k
T
A_{k}=\sigma_{k} u_{k} v_{k}^{\mathrm{T}}
Ak=σkukvkT 是
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=σ1u1v1T+σ2u2v2T+⋯+σnunvnT
设矩阵
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=σ1u1v1T+σ2u2v2T+⋯+σn−1un−1vn−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=σ1u1v1T+σ2u2v2T+⋯+σn−2un−2vn−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=σ1u1v1T+σ2u2v2T+⋯+σkukvkT
则
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 有很好的近似。