目录
1 奇异值分解的定义与性质
1.1 定义与定理
定义（singular value decomposition） 矩阵的因子分解
A
=
U
Σ
V
T
A=U\Sigma V^T
A=UΣVT，
A
∈
R
m
×
n
A\in \mathbb{R}^{m\times n}
A∈Rm×n，满足
U
U
T
=
I
UU^T=I
UUT=I
\quad
m阶orthogonal matrix
V
V
T
=
I
VV^T=I
VVT=I
\quad
n阶正交矩阵
Σ
=
d
i
a
g
(
σ
1
,
σ
2
,
⋯
,
σ
p
)
\Sigma=diag(\sigma_1,\sigma_2,\cdots,\sigma_p)
Σ=diag(σ1,σ2,⋯,σp)，
σ
1
≥
σ
2
≥
⋯
≥
σ
p
≥
0
\sigma_1\ge\sigma_2\ge\cdots\ge\sigma_p\ge0
σ1≥σ2≥⋯≥σp≥0
p
=
min
(
m
,
n
)
p=\min(m,n)
p=min(m,n)
矩阵的奇异值分解不要求矩阵A是方阵，可以看作是方阵的对角化的推广。
任意给定一个实矩阵，其奇异值分解一定存在！
定理（奇异值分解基本定理）
A
∈
R
m
×
n
A\in \mathbb{R}^{m\times n}
A∈Rm×n，则A的奇异值分解存在
A
=
U
Σ
V
T
A=U\Sigma V^T
A=UΣVT，其中U和V分别是m阶和n阶正交矩阵，
Σ
\Sigma
Σ是
m
×
n
m\times n
m×n矩阵对角矩阵，其对角线元素非负，且按降序排列。
（证明太~太长了，不写了。）
1.2 紧奇异值分解与截断奇异值分解
上述定理是完全奇异值分解（full singular value decomposition）
1 compact singular value decomposition
定义
A
∈
R
m
×
n
A\in \mathbb{R}^{m\times n}
A∈Rm×n，
r
a
n
k
(
A
)
=
r
rank(A)=r
rank(A)=r，
r
≤
min
(
m
,
n
)
r\le \min(m,n)
r≤min(m,n)，则
A
=
U
r
Σ
r
V
r
T
A=U_r\Sigma_rV_r^T
A=UrΣrVrT
U
r
∈
R
m
×
r
U_r\in \mathbb{R}^{m\times r}
Ur∈Rm×r，U的前r列
V
r
∈
R
n
×
r
V_r\in \mathbb{R}^{n\times r}
Vr∈Rn×r，V的前r列
Σ
r
∈
R
r
×
r
\Sigma_r\in \mathbb{R}^{r\times r}
Σr∈Rr×r，
Σ
\Sigma
Σ的前r个对角线元素
r
a
n
k
(
Σ
r
)
=
r
a
n
k
(
A
)
rank(\Sigma_r)=rank(A)
rank(Σr)=rank(A)
2 truncated singular value decomposition
定义
A
∈
R
m
×
n
A\in \mathbb{R}^{m\times n}
A∈Rm×n，
r
a
n
k
(
A
)
=
r
rank(A)=r
rank(A)=r，
0
<
k
<
r
0<k<r
0<k<r，则
A
≈
U
k
Σ
k
V
k
T
A\approx U_k\Sigma_kV_k^T
A≈UkΣkVkT
U
k
∈
R
m
×
k
U_k\in \mathbb{R}^{m\times k}
Uk∈Rm×k，U的前k列
V
k
∈
R
n
×
k
V_k\in \mathbb{R}^{n\times k}
Vk∈Rn×k，V的前k列
Σ
k
∈
R
k
×
k
\Sigma_k\in \mathbb{R}^{k\times k}
Σk∈Rk×k，
Σ
\Sigma
Σ的前k个对角线元素
r
a
n
k
(
Σ
k
)
<
r
a
n
k
(
A
)
rank(\Sigma_k)<rank(A)
rank(Σk)<rank(A)
紧奇异值分解对应着无损压缩，截断奇异值分解对应着有损压缩。
1.3 几何解释
复习线性变换：
A
m
×
n
A_{m\times n}
Am×n表示从
R
n
R^n
Rn到
R
m
R^m
Rm的一个线性变换，
T
:
x
→
A
x
T:x\to Ax
T:x→Ax。
线性变换可以分解为三个简单的变换：
①一个坐标系的旋转或反射变换；
②一个坐标轴的缩放变换；
③另一个坐标系的旋转或反射变换。
A
=
U
Σ
V
T
A=U\Sigma V^T
A=UΣVT
V
V
V的列向量
v
1
,
v
2
,
⋯
,
v
n
v_1,v_2,\cdots,v_n
v1,v2,⋯,vn构成
R
n
R^n
Rn空间的一组标准正交基，表示
R
n
R^n
Rn中的正交坐标系的旋转或反射变换；
U
U
U的列向量
u
1
,
u
2
,
⋯
,
u
n
u_1,u_2,\cdots,u_n
u1,u2,⋯,un构成
R
m
R^m
Rm空间的一组标准正交基，表示
R
m
R^m
Rm中的正交坐标系的旋转或反射变换；
Σ
\Sigma
Σ的对角元素
σ
1
,
σ
2
,
⋯
,
σ
n
\sigma_1,\sigma_2,\cdots,\sigma_n
σ1,σ2,⋯,σn表示
R
n
R^n
Rn中的原始正交坐标系坐标轴的
σ
1
,
σ
2
,
⋯
,
σ
n
\sigma_1,\sigma_2,\cdots,\sigma_n
σ1,σ2,⋯,σn的缩放变换。
综上，矩阵的奇异值分解可以看作是将其对应的线性变换分解为旋转变换、缩放变换及旋转变换的组合。根据奇异值分解基本定理，这个变换的组合一定存在。
1.4 主要性质
1
A
=
U
Σ
V
T
A=U\Sigma V^T
A=UΣVT
A
T
A
=
(
U
Σ
V
T
)
T
(
U
Σ
V
T
)
=
V
(
Σ
T
Σ
)
V
T
A^TA=(U\Sigma V^T)^T(U\Sigma V^T)=V(\Sigma^T\Sigma)V^T
ATA=(UΣVT)T(UΣVT)=V(ΣTΣ)VT
A
A
T
=
(
U
Σ
V
T
)
(
U
Σ
V
T
)
T
=
U
(
Σ
Σ
T
)
U
T
AA^T=(U\Sigma V^T)(U\Sigma V^T)^T=U(\Sigma\Sigma^T)U^T
AAT=(UΣVT)(UΣVT)T=U(ΣΣT)UT
矩阵
A
T
A
A^TA
ATA和
A
A
T
AA^T
AAT的特征分解存在，V的列向量是
A
T
A
A^TA
ATA的特征向量，U的列向量是
A
A
T
AA^T
AAT的特征向量，
Σ
\Sigma
Σ的奇异值是
A
T
A
A^TA
ATA和
A
A
T
AA^T
AAT的特征值的平方根。
2 奇异值、左、右奇异向量之间的关系
(1)
A
V
=
U
Σ
AV=U\Sigma
AV=UΣ
比较这一等式两端的第j列，得到
A
v
j
=
σ
j
u
j
,
j
=
1
,
2
,
⋯
,
n
Av_j=\sigma_ju_j,\quad j=1,2,\cdots,n
Avj=σjuj,j=1,2,⋯,n，这是矩阵A的右奇异向量和奇异值、左奇异向量的关系。
(2)
A
T
U
=
V
Σ
T
A^TU=V\Sigma^T
ATU=VΣT
比较这一等式两端的第j列，得到
A
T
u
j
=
σ
j
v
j
,
j
=
1
,
2
,
⋯
,
n
A^Tu_j=\sigma_jv_j,\quad j=1,2,\cdots,n
ATuj=σjvj,j=1,2,⋯,n，
A
T
u
j
=
0
,
j
=
n
+
1
,
n
+
2
,
⋯
,
m
A^Tu_j=0,\quad j=n+1,n+2,\cdots,m
ATuj=0,j=n+1,n+2,⋯,m
这是矩阵A的左奇异向量和奇异值、右奇异向量的关系。
3 奇异值唯一，U和V不唯一。
4 r a n k ( A ) = r a n k ( Σ ) rank(A)=rank(\Sigma) rank(A)=rank(Σ)，等于 σ i \sigma_i σi的个数 r r r(包含重复的奇异值)。
5 不想看。
2 奇异值分解的计算
① 求
A
T
A
A^TA
ATA的特征值和特征向量
② 求
V
n
×
n
V_{n\times n}
Vn×n
③ 求
Σ
m
×
n
\Sigma_{m\times n}
Σm×n
④ 求
U
m
×
m
U_{m\times m}
Um×m
对A的前r个正奇异值，令
u
j
=
1
σ
j
A
v
j
,
j
=
1
,
2
,
⋯
,
r
u_j=\frac{1}{\sigma_j}Av_j,\quad j=1,2,\cdots,r
uj=σj1Avj,j=1,2,⋯,r
得到
U
1
=
[
u
1
u
2
⋯
u
r
]
U_1=[u_1\quad u_2\quad\cdots\quad u_r]
U1=[u1u2⋯ur]
然后求
A
T
A^T
AT的零空间的一组标准正交基
{
u
r
+
1
,
u
r
+
2
,
⋯
,
u
m
}
\{u_{r+1},u_{r+2},\cdots,u_m\}
{ur+1,ur+2,⋯,um}
令
U
2
=
[
u
r
+
1
u
r
+
2
⋯
u
m
]
U_2=[u_{r+1}\quad u_{r+2}\quad\cdots\quad u_m]
U2=[ur+1ur+2⋯um]
U
=
[
U
1
U
2
]
U=[U_1\quad U_2]
U=[U1U2]
⑤ 得到奇异值分解 A = U Σ V T A=U\Sigma V^T A=UΣVT
3 奇异值分解与矩阵近似
3.1 Frobenius norm
Definition(Frobenius norm) A ∈ R m × n A\in\mathbb R^{m\times n} A∈Rm×n， A = [ a i j ] m × n A=[a_{ij}]_{m\times n} A=[aij]m×n， ∣ ∣ A ∣ ∣ F = ( ∑ i = 1 m ∑ j = 1 n a i j 2 ) 1 2 ||A||_F=\bigg(\sum\limits_{i=1}^m\sum\limits_{j=1}^na_{ij}^2\bigg)^\frac{1}{2} ∣∣A∣∣F=(i=1∑mj=1∑naij2)21
Lemma A ∈ R m × n A\in\mathbb R^{m\times n} A∈Rm×n， A = U Σ V T A=U\Sigma V^T A=UΣVT， Σ = d i a g ( σ 1 , σ 2 , ⋯ , σ n ) \Sigma=diag(\sigma_1,\sigma_2,\cdots,\sigma_n) Σ=diag(σ1,σ2,⋯,σn)，则 ∣ ∣ A ∣ ∣ F = ( σ 1 2 + σ 2 2 + ⋯ + σ n 2 ) 1 2 ||A||_F=(\sigma_1^2+\sigma_2^2+\cdots+\sigma_n^2)^\frac{1}{2} ∣∣A∣∣F=(σ12+σ22+⋯+σn2)21
3.2 矩阵的最优近似
奇异值分解是在平方损失（Frobenius norm）意义下对矩阵的最优近似，即数据压缩。
Theorem 1 A ∈ R m × n A\in\mathbb R^{m\times n} A∈Rm×n， r a n k ( A ) = r rank(A)=r rank(A)=r， M = { X ∈ R m × n ∣ r a n k ( X ) ≤ k , 0 < k < r } M=\{X\in \mathbb R^{m\times n}|rank(X)\le k,0<k<r\} M={X∈Rm×n∣rank(X)≤k,0<k<r}，则 ∃ X ∈ M \exist X\in M ∃X∈M， r a n k ( X ) = k rank(X)=k rank(X)=k，使得 ∣ ∣ A − X ∣ ∣ F = min S ∈ M ∣ ∣ A − S ∣ ∣ F ||A-X||_F=\min\limits_{S\in M}||A-S||_F ∣∣A−X∣∣F=S∈Mmin∣∣A−S∣∣F，称矩阵X为矩阵A在Frobenius norm意义下的最优近似。
Theorem 2
A
∈
R
m
×
n
A\in\mathbb R^{m\times n}
A∈Rm×n，
r
a
n
k
(
A
)
=
r
rank(A)=r
rank(A)=r，
A
=
U
Σ
V
T
A=U\Sigma V^T
A=UΣVT，
M
=
{
X
∈
R
m
×
n
∣
r
a
n
k
(
X
)
≤
k
,
0
<
k
<
r
}
M=\{X\in \mathbb R^{m\times n}|rank(X)\le k,0<k<r\}
M={X∈Rm×n∣rank(X)≤k,0<k<r}，若
X
∈
M
X\in M
X∈M且
r
a
n
k
(
X
)
=
k
rank(X)=k
rank(X)=k满足
∣
∣
A
−
X
∣
∣
F
=
min
S
∈
M
∣
∣
A
−
S
∣
∣
F
||A-X||_F=\min\limits_{S\in 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=(\sigma_{k+1}^2+\sigma_{k+2}^2+\cdots+\sigma_n^2)^\frac{1}{2}
∣∣A−X∣∣F=(σk+12+σk+22+⋯+σn2)21
特别地，若
A
′
=
U
Σ
′
V
T
A^\prime=U\Sigma^\prime V^T
A′=UΣ′VT，其中
Σ
′
=
[
Σ
k
0
0
0
]
\Sigma^\prime=\left[ \begin{matrix} \Sigma_k & 0\\ 0& 0 \end{matrix} \right]
Σ′=[Σk000]，则
∣
∣
A
−
A
′
∣
∣
F
=
(
σ
k
+
1
2
+
σ
k
+
2
2
+
⋯
+
σ
n
2
)
1
2
=
min
S
∈
M
∣
∣
A
−
S
∣
∣
F
||A-A^\prime||_F=(\sigma_{k+1}^2+\sigma_{k+2}^2+\cdots+\sigma_n^2)^\frac{1}{2}=\min\limits_{S\in M}||A-S||_F
∣∣A−A′∣∣F=(σk+12+σk+22+⋯+σn2)21=S∈Mmin∣∣A−S∣∣F.
3.3 矩阵的外积展开式
U
Σ
=
[
σ
1
u
1
σ
2
u
2
⋯
σ
n
u
n
]
U\Sigma=[\sigma_1u_1 \quad\sigma_2u_2\quad\cdots\quad\sigma_nu_n]
UΣ=[σ1u1σ2u2⋯σnun]
V
T
=
[
v
1
v
2
⋯
v
n
]
T
V^T=[v_1\quad v_2\quad\cdots\quad v_n]^T
VT=[v1v2⋯vn]T
A
=
σ
1
u
1
v
1
T
+
σ
2
u
2
v
2
T
+
⋯
+
σ
n
u
n
v
n
T
A=\sigma_1u_1v_1^T+\sigma_2u_2v_2^T+\cdots+\sigma_nu_nv_n^T
A=σ1u1v1T+σ2u2v2T+⋯+σnunvnT称为矩阵A的外积展开式。
u i v j T = [ u 1 i u 2 i ⋮ u m i ] [ v 1 j v 2 j ⋯ v n j ] u_iv_j^T=\left[ \begin{matrix} u_{1i}\\ u_{2i}\\ \vdots\\ u_{mi} \end{matrix} \right]\left[v_{1j}\quad v_{2j} \quad\cdots\quad v_{nj}\right] uivjT=⎣⎢⎢⎢⎡u1iu2i⋮umi⎦⎥⎥⎥⎤[v1jv2j⋯vnj]
A = ∑ k = 1 n A k = ∑ k = 1 n σ k u k v k T , A k = σ k u k v k T ∈ R m × n A=\sum\limits_{k=1}^nA_k=\sum\limits_{k=1}^n\sigma_ku_kv_k^T,\quad A_k=\sigma_ku_kv_k^T\in R^{m\times n} A=k=1∑nAk=k=1∑nσkukvkT,Ak=σkukvkT∈Rm×n
若 r a n k ( A ) = n rank(A)=n rank(A)=n，则 A = σ 1 u 1 v 1 T + σ 2 u 2 v 2 T + ⋯ + σ n u n v n T A=\sigma_1u_1v_1^T+\sigma_2u_2v_2^T+\cdots+\sigma_nu_nv_n^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_1u_1v_1^T+\sigma_2u_2v_2^T+\cdots+\sigma_{n-1}u_{n-1}v_{n-1}^T An−1=σ1u1v1T+σ2u2v2T+⋯+σn−1un−1vn−1T，则 r a n k ( A n − 1 ) = n − 1 rank(A_{n-1})=n-1 rank(An−1)=n−1，且 A n − 1 A_{n-1} An−1是秩为 n − 1 n-1 n−1矩阵在Frobenius norm意义下A的最优近似矩阵。以此类推。
通常奇异值 σ i \sigma_i σi递减很快，所以k取很小值时， A k A_k Ak也可以对A有很好的近似。
总结
唉，一章比一章难起来了！这一章书上有两大证明我略过去了，说实话没必要弄懂证明是不是？公式打得好累，矩阵看得头疼！但是会做题就行了，例题可以自行翻书，我就不搬上来了，超级简单，作者为了照顾我们这些渣渣真的有心了！如果有书写错误可以告诉我哦，抱拳~