计算方法（矩阵的外积展开式）

2024-02-16 10:10:34

奇异值分解，Singular value decomposition（SVD）

在推荐、图像等多个领域中，因为数据矩阵的庞大，所以经常需要对矩阵进行压缩；亦或有噪声，要进行去噪，奇异值分解就是解决方法中的一个。它将矩阵分解为三个矩阵相乘的形式，从而减小存储的大小；在截断奇异值分解中删掉奇异值，可以达到去噪的目的，而且它还可以得到一些数据中的隐语义，所以非常的通用。

矩阵 Am∗nA_{m*n}A
m∗n

，通过奇异值分解得到：UΣVTUΣV^TUΣV
T
，即 A=UΣVTA=UΣV^TA=UΣV
T

其中，UUU 为 m 阶正交矩阵，VVV 为 n 阶正交矩阵，ΣΣΣ 为由降序排列的非负元素组成的 m∗nm*nm∗n 的对角矩阵。

UUT=I，VVT=I，Σ=diag(σ1，σ2，…，σk)UU^T=I，VV^T=I，Σ=diag(σ_1，σ_2，…，σ_k)UU
T
=I，VV
T
=I，Σ=diag(σ
1

，σ
2

，…，σ
k

)

σiσ_iσ
i

为矩阵的奇异值，U为左奇异向量，V为右奇异向量。

奇异值分解有一个特殊定理：奇异值分解一定存在，但不是唯一的。

奇异值分解中，奇异值 σ1，σ2，…，σkσ_1，σ_2，…，σ_kσ
1

，σ
2

，…，σ
k

是唯一的，而矩阵 U，V 不是唯一的。

奇异值分解可以看做是矩阵压缩的方法，用因子分解近似原始数据矩阵，它是在平方损失意义下的最优近似。

几何解释
以几何对奇异值分解进行解释：

奇异值分解可以理解为对于矩阵AAA，从 n 维空间 RnR^nR
n
到 m 维空间的一个线性变换

T:x→Ax，x∈Rn，Ax∈RmT: x→Ax，x∈R^n，Ax∈R^mT:x→Ax，x∈R
n
，Ax∈R
m

而对这一线性变换可分解为三个简单变换（奇异值定理保证此三部分解一定存在）：

① 一个坐标系的旋转或反射变换；
② 一个坐标轴的缩放变换；
③ 另一个坐标系的旋转或反射变换。

紧奇异值分解（无损压缩）
rank(A)=r，r≤min(m,n)rank(A)=r，r\le min(m,n)rank(A)=r，r≤min(m,n)，

A=UrΣrVTr，Um∗r，Vn∗r，ΣrA=U_rΣ_rV_r^T，U_{m*r}，V_{n*r}，Σ_rA=U
r

Σ
r

V
r
T

，U
m∗r

，V
n∗r

，Σ
r

由 ΣΣΣ 的前 r 个对角元素得到。

当 rank(Σ)=rrank(Σ)=rrank(Σ)=r 时，此分解称为紧奇异值分解。

计算方法
① 首先计算 AATAA^TAA
T
的特征值，并按降序进行排列得到 λ1≥λ2≥…≥λn≥0λ_1 \ge λ_2 \ge…\geλ_n\ge0λ
1

≥λ
2

≥…≥λ
n

≥0；

② 将特征值 λiλ_iλ
i

代入特征方程计算对应的特征向量；

③ 将特征向量单位化，得到单位特征向量 v1，v2，…，vnv_1，v_2，…，v_nv
1

，v
2

，…，v
n

，构成 n 阶正交矩阵 V；

④ 计算奇异值 σi=λi−−√，i=1,2,…,nσ_i=\sqrt{λ_i}，i=1,2,…,nσ
i

=
λ
i

，i=1,2,…,n，将 σiσ_iσ
i

作为对角元素构成对角矩阵 Σ=diag(σ1，σ2，…，σk)Σ=diag(σ_1，σ_2，…，σ_k)Σ=diag(σ
1

，σ
2

，…，σ
k

)

⑤ 对 A 的前 r 个正奇异值计算，uj=1σjAvj，j=1,2,…,ru_j=\frac{1}{σ_j}Av_j，j=1,2,…,ru
j

=
σ
j

1

Av
j

，j=1,2,…,r，得到 U1=[u1  u2  …  ur]U_1=[u_1~~u_2~~…~~u_r]U
1

=[u
1

  u
2

  …  u
r

]；

⑥ 求 AT的零空间的一组标准正交基 {ur+1，ur+2，…，umu_{r+1}，u_{r+2}，…，u_mu
r+1

，u
r+2

，…，u
m

}，即求解 ATx=0A^Tx=0A
T
x=0，U2=[ur+1  ur+2  …  um]U_2=[u_{r+1}~~u_{r+2}~~…~~u_m]U
2

=[u
r+1

  u
r+2

  …  u
m

]

⑦ 令 U=[U1 U2]U=[U_1~~U_2]U=[U
1

U
2

]，得到 m 阶正交矩阵 U；

⑧ 最终得到 A=UΣVTA=UΣV^TA=UΣV
T

截断奇异值分解（有损压缩）
截断奇异值分解，顾名思义是选取了部分进行分解。即只取最大的 k 个奇异值组成 Σk，k<rΣ_k，k<rΣ
k

，k<r

当 rank(Σ)<rrank(Σ)<rrank(Σ)<r 时，此分解称为截断奇异值分解。

A≈UkΣkVTk，0<k<rA\approx U_kΣ_kV_k^T，0<k<rA≈U
k

Σ
k

V
k
T

，0<k<r

Um∗k，UU_{m*k}，UU
m∗k

，U 的前 k 列；Vn∗k，VV_{n*k}，VV
n∗k

，V 的前 k 列；ΣkΣ_kΣ
k

由 ΣΣΣ 前 k 个奇异值组成。

由于通常奇异值 σiσ_iσ
i

递减很快，所以当 k 很小时，AkA_kA
k

也可以对 A 有很好的近似。所以截断奇异值分解更加常用。

计算方法（矩阵的外积展开式）
将 A 的奇异值分解看成两部分：UΣUΣUΣ 和 VTV^TV
T
乘积，将 UΣUΣUΣ 按列向量分块，将 VVV 也按列向量分块，得

UΣ=[σ1u1  σ2u2  …  σnun]UΣ=[σ_1u_1~~σ_2u_2~~…~~σ_nu_n]UΣ=[σ
1

u
1

  σ
2

u
2

  …  σ
n

u
n

]

V=[v1  v2  …  vn]V=[v_1~~v_2~~…~~v_n]V=[v
1

  v
2

  …  v
n

]

则 A=σ1u1vT1+σ2u2vT2+…+σnunvTnA=σ_1u_1v_1^T+σ_2u_2v_2^T+…+σ_nu_nv_n^TA=σ
1

u
1

v
1
T

+σ
2

u
2

v
2
T

+…+σ
n

u
n

，此式称为外积展开式。

根据紧奇异值分解的计算方法易得 σi、uiσ_i、u_iσ
i

、u
i

。其中 i=(1→n)i=(1→n)i=(1→n) 按照降序排列。

所以在选择（截断）前 k 个奇异值时，只需计算外积展开式的前 k 项和即可。
————————————————

码农公寓

相关文章