计算方法(矩阵的外积展开式)

奇异值分解,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(Σ)&lt;rrank(Σ)&lt;rrank(Σ)<r 时,此分解称为截断奇异值分解。

A≈UkΣkVTk,0&lt;k&lt;rA\approx U_kΣ_kV_k^T,0&lt;k&lt;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

<a href="https://www.cnblogs.com/lucongrui/articles/12963229.html" target="_blank">
<a href="https://www.cnblogs.com/lucongrui/articles/12963222.html" target="_blank">
<a href="https://www.cnblogs.com/lucongrui/articles/12963216.html" target="_blank">
<a href="https://www.cnblogs.com/lucongrui/articles/12963208.html" target="_blank">
<a href="https://www.cnblogs.com/lucongrui/articles/12963203.html" target="_blank">
<a href="https://www.cnblogs.com/lucongrui/articles/12963198.html" target="_blank">
<a href="https://www.cnblogs.com/lucongrui/articles/12963192.html" target="_blank">
<a href="https://www.cnblogs.com/lucongrui/articles/12963188.html" target="_blank">
<a href="https://www.cnblogs.com/lucongrui/articles/12963183.html" target="_blank">
<a href="https://www.cnblogs.com/lucongrui/articles/12963175.html" target="_blank">
<a href="https://www.cnblogs.com/lucongrui/articles/12963171.html" target="_blank">
<a href="https://www.cnblogs.com/lucongrui/articles/12963163.html" target="_blank">
<a href="https://www.cnblogs.com/lucongrui/articles/12963155.html" target="_blank">
<a href="https://www.cnblogs.com/lucongrui/articles/12963147.html" target="_blank">
<a href="https://www.cnblogs.com/lucongrui/articles/12963143.html" target="_blank">
<a href="https://www.cnblogs.com/lucongrui/articles/12963141.html" target="_blank">
<a href="https://www.cnblogs.com/lucongrui/articles/12963137.html" target="_blank">
<a href="https://www.cnblogs.com/lucongrui/articles/12963130.html" target="_blank">
<a href="https://www.cnblogs.com/lucongrui/articles/12963125.html" target="_blank">
<a href="https://www.cnblogs.com/lucongrui/articles/12963118.html" target="_blank">
<a href="https://www.cnblogs.com/lucongrui/articles/12963114.html" target="_blank">
<a href="https://www.cnblogs.com/lucongrui/articles/12963110.html" target="_blank">
<a href="https://www.cnblogs.com/lucongrui/articles/12963103.html" target="_blank">
<a href="https://www.cnblogs.com/lucongrui/articles/12963099.html" target="_blank">
<a href="https://www.cnblogs.com/wxy8/articles/12963233.html" target="_blank">
<a href="https://www.cnblogs.com/wxy8/articles/12963230.html" target="_blank">
<a href="https://www.cnblogs.com/wxy8/articles/12963220.html" target="_blank">
<a href="https://www.cnblogs.com/wxy8/articles/12963215.html" target="_blank">
<a href="https://www.cnblogs.com/wxy8/articles/12963207.html" target="_blank">
<a href="https://www.cnblogs.com/wxy8/articles/12963202.html" target="_blank">
<a href="https://www.cnblogs.com/wxy8/articles/12963196.html" target="_blank">
<a href="https://www.cnblogs.com/wxy8/articles/12963193.html" target="_blank">
<a href="https://www.cnblogs.com/wxy8/articles/12963189.html" target="_blank">
<a href="https://www.cnblogs.com/wxy8/articles/12963184.html" target="_blank">
<a href="https://www.cnblogs.com/wxy8/articles/12963176.html" target="_blank">
<a href="https://www.cnblogs.com/wxy8/articles/12963169.html" target="_blank">
<a href="https://www.cnblogs.com/wxy8/articles/12963161.html" target="_blank">
<a href="https://www.cnblogs.com/wxy8/articles/12963152.html" target="_blank">
<a href="https://www.cnblogs.com/wxy8/articles/12963146.html" target="_blank">
<a href="https://www.cnblogs.com/wxy8/articles/12963142.html" target="_blank">
<a href="https://www.cnblogs.com/wxy8/articles/12963139.html" target="_blank">
<a href="https://www.cnblogs.com/wxy8/articles/12963134.html" target="_blank">
<a href="https://www.cnblogs.com/wxy8/articles/12963129.html" target="_blank">
<a href="https://www.cnblogs.com/wxy8/articles/12963123.html" target="_blank">
<a href="https://www.cnblogs.com/wxy8/articles/12963117.html" target="_blank">
<a href="https://www.cnblogs.com/wxy8/articles/12963113.html" target="_blank">
<a href="https://www.cnblogs.com/wxy8/articles/12963109.html" target="_blank">
<a href="https://www.cnblogs.com/wxy8/articles/12963101.html" target="_blank">
<a href="https://www.cnblogs.com/wxy8/articles/12963096.html" target="_blank">
<a href="https://www.cnblogs.com/sflhw/articles/12963234.html" target="_blank">
<a href="https://www.cnblogs.com/sflhw/articles/12963227.html" target="_blank">
<a href="https://www.cnblogs.com/sflhw/articles/12963221.html" target="_blank">
<a href="https://www.cnblogs.com/sflhw/articles/12963213.html" target="_blank">
<a href="https://www.cnblogs.com/sflhw/articles/12963205.html" target="_blank">
<a href="https://www.cnblogs.com/sflhw/articles/12963201.html" target="_blank">
<a href="https://www.cnblogs.com/sflhw/articles/12963194.html" target="_blank">
<a href="https://www.cnblogs.com/sflhw/articles/12963190.html" target="_blank">
<a href="https://www.cnblogs.com/sflhw/articles/12963185.html" target="_blank">
<a href="https://www.cnblogs.com/sflhw/articles/12963177.html" target="_blank">
<a href="https://www.cnblogs.com/sflhw/articles/12963173.html" target="_blank">
<a href="https://www.cnblogs.com/sflhw/articles/12963167.html" target="_blank">
<a href="https://www.cnblogs.com/sflhw/articles/12963158.html" target="_blank">
<a href="https://www.cnblogs.com/sflhw/articles/12963150.html" target="_blank">
<a href="https://www.cnblogs.com/sflhw/articles/12963145.html" target="_blank">
<a href="https://www.cnblogs.com/sflhw/articles/12963140.html" target="_blank">
<a href="https://www.cnblogs.com/sflhw/articles/12963133.html" target="_blank">
<a href="https://www.cnblogs.com/sflhw/articles/12963128.html" target="_blank">
<a href="https://www.cnblogs.com/sflhw/articles/12963124.html" target="_blank">
<a href="https://www.cnblogs.com/sflhw/articles/12963119.html" target="_blank">
<a href="https://www.cnblogs.com/sflhw/articles/12963115.html" target="_blank">
<a href="https://www.cnblogs.com/sflhw/articles/12963111.html" target="_blank">
<a href="https://www.cnblogs.com/sflhw/articles/12963105.html" target="_blank">
<a href="https://www.cnblogs.com/sflhw/articles/12963098.html" target="_blank">
<a href="https://www.cnblogs.com/cutman/articles/12963235.html" target="_blank">
<a href="https://www.cnblogs.com/cutman/articles/12963225.html" target="_blank">
<a href="https://www.cnblogs.com/cutman/articles/12963219.html" target="_blank">
<a href="https://www.cnblogs.com/cutman/articles/12963212.html" target="_blank">
<a href="https://www.cnblogs.com/cutman/articles/12963204.html" target="_blank">
<a href="https://www.cnblogs.com/cutman/articles/12963197.html" target="_blank">
<a href="https://www.cnblogs.com/cutman/articles/12963191.html" target="_blank">
<a href="https://www.cnblogs.com/cutman/articles/12963186.html" target="_blank">
<a href="https://www.cnblogs.com/cutman/articles/12963178.html" target="_blank">
<a href="https://www.cnblogs.com/cutman/articles/12963168.html" target="_blank">
<a href="https://www.cnblogs.com/cutman/articles/12963165.html" target="_blank">
<a href="https://www.cnblogs.com/cutman/articles/12963156.html" target="_blank">
<a href="https://www.cnblogs.com/cutman/articles/12963149.html" target="_blank">
<a href="https://www.cnblogs.com/cutman/articles/12963138.html" target="_blank">
<a href="https://www.cnblogs.com/cutman/articles/12963132.html" target="_blank">
<a href="https://www.cnblogs.com/cutman/articles/12963127.html" target="_blank">
<a href="https://www.cnblogs.com/cutman/articles/12963120.html" target="_blank">
<a href="https://www.cnblogs.com/cutman/articles/12963116.html" target="_blank">
<a href="https://www.cnblogs.com/cutman/articles/12963112.html" target="_blank">
<a href="https://www.cnblogs.com/cutman/articles/12963106.html" target="_blank">



,此式称为外积展开式。

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

、u
i

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

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

上一篇:[开发杂项][编译][C/C++]Suppressing GCC Warnings


下一篇:相抵,相似,合同,