- 一、奇异值的 Q R QR QR 分解算法
- 二、构造二重对角矩阵并利用 Q R QR QR 分解
- 三、奇异值分解的右边 J a c o b i 算 法 mathrm{Jacobi}算法 Jacobi算法
和之前利用 A A T AA^{mathrm{T}} AAT 的特征值求奇异值不同的是, 这个方法看起来不太能够理解, 在书上的描述也比较简单.
其实就是简单的两步, 第一步通过 H o u s e h o l d mathrm{Household} Household 变换使得矩阵 A A A 变成二重对角矩阵. 所谓二重对角矩阵就是除了主对角线以及主对角线上面一条对角线外的其余元素全为 0.
第二步就是反复利用正交变换使得除主对角线外的那些元素逐渐减小靠近 0.
虽然看起来很简单, 但是没有公式和实际例子, 自己也只能慢慢来摸索方法.
二、构造二重对角矩阵并利用 Q R QR QR 分解现有这样一个矩阵 A A A
A = [ 1 2 2 2 1 2 2 2 1 ] A = begin{bmatrix} 1 & 2 & 2\ 2 & 1 & 2\ 2 & 2 & 1 end{bmatrix} A=⎣⎡122212221⎦⎤
对第一列进行 H o u s e h o l d e r mathrm{Householder} Householder 变换, 先把第一列提出来
a 1 = [ 1 2 2 ] a_1 = begin{bmatrix} 1\ 2\ 2 end{bmatrix} a1=⎣⎡122⎦⎤
求 a 1 a_1 a1 的二范数
α 2 = ∥ a 1 ∥ 2 = 1 2 + 2 2 + 2 2 = 1 + 4 + 4 = 3 alpha_2 = lVert a_1 rVert_2 = sqrt{1^2+2^2+2^2} = sqrt{1+4+4} = 3 α2=∥a1∥2=12+22+22 =1+4+4 =3
然后有
a 1 − α 2 e 2 = [ 1 2 2 ] − 3 [ 1 0 0 ] = [ − 2 2 2 ] a_1 - alpha_2e_2 = begin{bmatrix} 1\ 2\ 2 end{bmatrix} - 3begin{bmatrix} 1\ 0\ 0 end{bmatrix} = begin{bmatrix} -2\ 2\ 2 end{bmatrix} a1−α2e2=⎣⎡122⎦⎤−3⎣⎡100⎦⎤=⎣⎡−222⎦⎤
其中 e 2 e_2 e2 是单位向量 [ 1 0 0 ] begin{bmatrix}1\0\0end{bmatrix} ⎣⎡100⎦⎤.
∥ a 1 − α 2 e 2 ∥ 2 = ( − 2 ) 2 + 2 2 + 2 2 = 4 + 4 + 4 = 12 lVert a_1 - alpha_2e_2rVert_2 = sqrt{(-2)^2+2^2+2^2} = sqrt{4+4+4} = sqrt{12} ∥a1−α2e2∥2=(−2)2+22+22 =4+4+4 =12
那么就有
u 1 = a 1 − α 2 e 2 ∥ a 1 − α 2 e 2 ∥ 2 = 1 12 [ − 2 2 2 ] u_1 = frac{a_1 - alpha_2e_2}{lVert a_1 - alpha_2e_2rVert_2}=frac{1}{sqrt{12}} begin{bmatrix} -2\ 2\ 2 end{bmatrix} u1=∥a1−α2e2∥2a1−α2e2=12 1⎣⎡−222⎦⎤
根据 H 1 = I − 2 u 1 u 1 T H_1 = I - 2u_1u_1^{mathrm{T}} H1=I−2u1u1T 可得
H 1 = [ 1 0 0 0 1 0 0 0 1 ] − 2 × 1 12 [ − 2 2 2 ] [ − 2 2 2 ] = [ 1 0 0 0 1 0 0 0 1 ] − 1 6 [ 4 − 4 − 4 − 4 4 4 − 4 4 4 ] = [ 1 / 3 2 / 3 2 / 3 2 / 3 1 / 3 − 2 / 3 2 / 3 − 2 / 3 1 / 3 ] begin{aligned}H_1 &= begin{bmatrix} 1 & 0 & 0\ 0 & 1 & 0\ 0 & 0 & 1 end{bmatrix} - 2 times frac{1}{12} begin{bmatrix} -2\ 2\ 2 end{bmatrix} begin{bmatrix} -2 & 2 & 2 end{bmatrix} \ &= begin{bmatrix} 1 & 0 & 0\ 0 & 1 & 0\ 0 & 0 & 1 end{bmatrix} - frac{1}{6} begin{bmatrix} 4 & -4 & -4\ -4 & 4 & 4\ -4 & 4 & 4 end{bmatrix} \ &= begin{bmatrix} 1/3 & 2/3 & 2/3\ 2/3 & 1/3 & -2/3\ 2/3 & -2/3 & 1/3 end{bmatrix} end{aligned} H1=⎣⎡100010001⎦⎤−2×121⎣⎡−222⎦⎤[−222]=⎣⎡100010001⎦⎤−61⎣⎡4−4−4−444−444⎦⎤=⎣⎡1/32/32/32/31/3−2/32/3−2/31/3⎦⎤
神奇的事情来了, 这里有 H A HA HA
H 1 A = [ 1 / 3 2 / 3 2 / 3 2 / 3 1 / 3 − 2 / 3 2 / 3 − 2 / 3 1 / 3 ] [ 1 2 2 2 1 2 2 2 1 ] = [ 3 8 / 3 8 / 3 0 1 / 3 8 / 3 0 4 / 3 1 / 3 ] begin{aligned}H_1A &= begin{bmatrix} 1/3 & 2/3 & 2/3\ 2/3 & 1/3 & -2/3\ 2/3 & -2/3 & 1/3 end{bmatrix} begin{bmatrix} 1 & 2 & 2\ 2 & 1 & 2\ 2 & 2 & 1 end{bmatrix} \ &=begin{bmatrix} 3 & 8/3 & 8/3\ 0 & 1/3 & 8/3\ 0 & 4/3 & 1/3 end{bmatrix} end{aligned} H1A=⎣⎡1/32/32/32/31/3−2/32/3−2/31/3⎦⎤⎣⎡122212221⎦⎤=⎣⎡3008/31/34/38/38/31/3⎦⎤
然后这里对于一个 3 × 3 3 times 3 3×3 的矩阵只是将第一列除 ( 1 , 1 ) (1,1) (1,1) 位置的元素归 0, 但是并没有完成对第一行除 ( 1 , 1 ) (1,1) (1,1) 和 ( 1 , 2 ) (1,2) (1,2) 位置的元素归 0. 书上也没有提到这么做的方法, 只是轻描淡写一句还是通过 H o u s e h o l d e r mathrm{Householder} Householder 变换.
无奈这个算法实在搞不懂, 暂且搁置. 未完待续…
三、奇异值分解的右边 J a c o b i 算 法 mathrm{Jacobi}算法 Jacobi算法现有矩阵 A = [ 1 2 2 1 ] A=begin{bmatrix} 1& 2\ 2& 1end{bmatrix} A=[1221], 求其 SVD 分解.
第一步先计算矩阵
A
T
A
A^{mathrm{T}}A
ATA 的
(
i
,
j
)
(i,j)
(i,j) 子矩阵
[
a
c
c
b
]
begin{bmatrix} a& c\ c& bend{bmatrix}
[accb], 因为要求
i
<
j
i < j
i
A
T
A
=
[
5
4
4
5
]
A^{mathrm{T}}A=begin{bmatrix} 5 & 4 \ 4 & 5 end{bmatrix}
ATA=[5445]
a
=
∑
k
−
1
n
A
k
i
2
=
A
11
2
+
A
21
2
=
5
2
+
4
2
=
25
+
16
=
41
a = sum_{k-1}^{n}A_{ki}^2 = A_{11}^2 + A_{21}^2 = 5^2 + 4^2 = 25 + 16 = 41
a=k−1∑nAki2=A112+A212=52+42=25+16=41
b
=
∑
k
−
1
n
A
k
j
2
=
A
12
2
+
A
22
2
=
4
2
+
5
2
=
16
+
25
=
41
b = sum_{k-1}^{n}A_{kj}^2 = A_{12}^2 + A_{22}^2 = 4^2 + 5^2 = 16 + 25 = 41
b=k−1∑nAkj2=A122+A222=42+52=16+25=41
c
=
∑
k
−
1
n
A
k
i
∗
A
k
j
=
(
A
11
×
A
12
)
+
(
A
21
×
A
22
)
=
(
5
×
4
)
+
(
4
×
5
)
=
20
+
20
=
40
c = sum_{k-1}^{n}A_{ki}*A_{kj} = (A_{11} times A_{12}) + (A_{21} times A_{22}) = (5 times 4) + (4 times 5) = 20 + 20 = 40
c=k−1∑nAki∗Akj=(A11×A12)+(A21×A22)=(5×4)+(4×5)=20+20=40 可以得到子矩阵
[
80
60
60
45
]
begin{bmatrix} 80& 60\ 60& 45end{bmatrix}
[80606045], 计算使其对角化的右边
J
a
c
o
b
i
mathrm{Jacobi}
Jacobi 旋转矩阵
[
c
s
−
s
n
s
n
c
s
]
begin{bmatrix} cs& -sn\ sn& csend{bmatrix}
[cssn−sncs]
ξ
=
(
b
−
a
)
/
(
2
c
)
=
(
45
−
80
)
/
(
2
×
60
)
=
(
−
35
)
/
(
120
)
=
−
7
24
xi = (b - a)/(2c) = (45 - 80)/(2 times 60) = (-35)/(120) = -frac{7}{24}
ξ=(b−a)/(2c)=(45−80)/(2×60)=(−35)/(120)=−247
t
=
s
g
n
(
ξ
)
/
(
∣
ξ
∣
+
1
+
ξ
2
)
=
s
g
n
(
−
7
24
)
/
(
∣
−
7
24
∣
+
1
+
(
−
7
24
)
2
)
=
−
3
4
t = mathrm{sgn}(xi)/(|xi|+ sqrt{1 + xi^2}) = mathrm{sgn}(-frac{7}{24})/(|-frac{7}{24}| + sqrt{1 + (-frac{7}{24})^2}) = -frac{3}{4}
t=sgn(ξ)/(∣ξ∣+1+ξ2
)=sgn(−247)/(∣−247∣+1+(−247)2
)=−43 所以就有
c
s
=
1
/
1
+
t
2
=
1
1
+
9
16
=
4
5
cs = 1/sqrt{1+t^2} = frac{1}{sqrt{1 + frac{9}{16}}}= frac{4}{5}
cs=1/1+t2
=1+169
1=54
s
n
=
c
s
×
t
=
4
5
×
−
3
4
=
−
3
5
sn = cs times t = frac{4}{5} times -frac{3}{4} = -frac{3}{5}
sn=cs×t=54×−43=−53 更新矩阵
A
A
A
A
=
[
1
2
2
1
]
⟶
[
2
1
11
/
5
−
2
/
5
]
A = begin{bmatrix} 1& 2\ 2& 1 end{bmatrix} longrightarrow begin{bmatrix} 2& 1\ 11/5& -2/5 end{bmatrix}
A=[1221]⟶[211/51−2/5] 更新右奇异向量的矩阵
V
V
V
V
=
[
1
0
0
1
]
⟶
[
4
/
5
−
3
/
5
3
/
5
4
/
5
]
V = begin{bmatrix} 1& 0\ 0& 1 end{bmatrix} longrightarrow begin{bmatrix} 4/5& -3/5\ 3/5& 4/5 end{bmatrix}
V=[1001]⟶[4/53/5−3/54/5] 感觉过程中出现了错误, 和实际奇异值分解有误差. 或许是迭代次数不够, 然而在网上搜索之后说的是可能是印刷问题, 那么这部分内容就还是交到明天去做.
