整体或局部: 图形计算基础，SVD方法奇异分解还不了解吗？
7 写在前面
侠骨耐风霜, 雄心吞宇宙。
浩然一点气, 清风万里飘。
磨磨唧唧终于到达这里。 我们经历了哪些，从方程组消元到方阵行列式变换最简型，到CR分解块运算。
现在是矩形矩阵特征值。 也就是 奇异值(singular values)。
我们仍然需要解决零空间 A->x = 0 问题。
写在前面
SVD算法大量在图形计算中应用。这是类似于前面讲过的一种矩阵分解算法，可以将一个矩阵分解为三个矩阵：U、Σ和V。U和V是正交矩阵，Σ是奇异值矩阵。 正交分解方法在后续章节将会陆续讲解。
降维PCA应用
图形特征提取
图形压缩
这里先讲解如何手算一个矩阵的奇异分解，并在最后介绍现在常用的图形计算领域。
7.0 奇异值和奇异矩阵
注意：有些书有 奇异矩阵，这 与 奇异值 不是同一个东西。
我的理解是 奇异值 是 矩形矩阵的特征值，为了与方阵的特征值区别，专有名称为 奇异值。
奇异矩阵是矩阵，只是没有逆矩阵，所以称为 奇异矩阵。
如果矩阵A为奇异矩阵，那么A的长度 |A| = 0
相对奇异矩阵的是满秩矩阵，非奇异矩阵。 |A| != 0
矩形矩阵可能是奇异的或非奇异的，但是都可以尝试获取奇异值。
因为奇异值是一种近似值，类似最小二乘解(这将在下一部分了解)。
设 S = S^T 的特征值 与 正交特征向量，它有 X^t*Y = 0,首先它有如下事实
S_x = λX
S_y = αY
λ ！= α 有 S^t = S
证明正交性 X^t * y = 0
(1) 转置到 X^t*S^t = λX^t 和使用 S^t = S
X^t*S_y = λX^t*y
(2) 也可以 乘以 S_y = αY
X^t*S_y = αX^t*Y
(3) 现在 λX^t*Y = αX^t*Y
由于 λ ！= α 所以 X^t*Y 必须为 0
对于对角矩阵 (2 1 上下对角线元素相同， 每一个对称矩阵都是正交矩阵。
1 2)
S[q1 ... qr] = [λ*q1 ... λn*qn] = [q1 ... qn] (λ1 ... 0
0 λ2 ... 0
0 0 ... λn)
这表示 SQ = QA
S = Q ⋀ Q^-1 = Q ⋀ Q^t # 合取
S = Q ⋀ Q^t
这等同于求和 λ1q1q1^t + … + λrqrqn^t 为秩为1的矩阵
S = A^t*A 这里将取得奇异值
所以奇异分解公式: A = UΣV^t 是对以下方程的求和
α1U1V1^t + ... + αrUrVr^t (秩为1的矩阵)
奇异值 α1 … αr 存在于求和过程中，奇异向量在 U 和 V中
那么对于非对称矩阵，也就是矩形矩阵
A[X1 ... Xn] = [λ1X1 ... λrXr]
AX = X⋀
n阶为独立特征向量
A = X ⋀ X^-1
这里A^2 和 A^3 拥有相同的特征向量，类似A
A^2*X = A(λX) = λ(A*X) = λ^2*X A^n*X = λ^n*X
A^2 = (X ⋀ X^-1)(XAX^-1) = X⋀^2X^-1 A^n = X⋀^nX^-1
A^n -> 0 当 ⋀^n -> 0 时 有以下结论:
|λ_i| < 1
证明: A^t*A 是方阵，对称，明确非负的
(1) A^t*A = (n x m)(m x n) = n x n #方阵
(2) (BA)^t = A^t*B^t (A^t*A)^t = A^t*A^tt = A^t*A #对称
(3) S = S^t 是非负的明确的有以下条件特征值
1 全部特征值 >= 0 Sx = λx
2 对于每个向量x有: x^t * Sx >= 0
非方阵可能没有特征值和特征向量。 此时，可以使用计算奇异值的方式。
7.1 奇异分解: 矩形矩阵的 SVD过程
SVD(Sigular Value Decomposition) 又称奇异值分解过程:
A = UΣV^t （公式一）
SVD常常用于高维数据的降维操作，比如百万图像，高清晰视频提取，用于它们的高清晰关键信息提取。
它也是傅里叶变换（Fourier transform）的数据驱动概括(FFT)的基本步骤。 从大型计算中提取近似方程，做为数字转换映射系统到某个坐标系统中。比如湍流分析，大型飞机高速飞行的湍流和气流研究。
也可以用于解决 Ax = b 在零空间的解的问题。
在互联网行业如脸书，谷歌，微软用于主成分统计分析PCA(principal component analysis),这是一种基于用户主要行为模式和相关性的数据分析提取，并蒸馏它到关键信息，以方便理解数据。另一些以一种奇异分解的方式，用于特征识别。如AMZ的商品推荐算法，或Netfix的视频推荐算法，它是简要的可解释的，用于哪些被喜欢，哪些被讨厌的简要列表,总之它被广泛使用于建模。
当 U^tU = I 并且 V^tV = 1
A*V = UΣ 这意思是：（σ sigma 为奇异值）
A(V1 ... Vr) = (U1 ... Ur)(σ1
...
σ_r)
并且 AVi = σ_iU_i
奇异值 σ1 >= σ_2 >= … >= σ_r > 0 (r为A的秩)
我们使全部 U 和V，因为 V1 … Vr 是相互正交的，我们可以仅仅在对称矩阵先进行验证。
σ表示奇异值，奇异值或奇异向量，拉伸 或 翻转 矩形矩阵。
分解矩阵为奇异小矩阵后，如果乘 向量 ->x 第一件事就是获得 V的转置 V^t, 并且V^t 是正交矩阵。
我们可以求取奇异向量。先解决以下两个问题：
(1) 怎样在A的行空间 选择正交 Vi
设Vi是特征向量，取自 A^t*A
A^t*A*Vi = λiVi = σi^2*Ui # 此处Vi是正交的，即 V^t*V = I
(2) 在A的列空间选择 Ui 因为Ui 是正交的，所以重要的性质是 U^t*U = I,因此
(AVj/σj)^t*(AVi/σi) = (Vj^t*A^t*A*Vi)/(σj*σi)
= (Vj^t*σi^2*Vi)/(σj*σi)
=( 1 当 i = j
0 当 i != j)
如下图所示关系，为奇异值如何变化并且使空间变化的：
(1) U 和 V 是旋转并且可能反射的。 (rptationis and reflections)
(2) U是左奇异向量，V是右奇异向量。
(3) 求和Σ 拉伸圆到椭圆。 当矩阵对称时，右奇异值，将进入V，
左奇异值 = 左特征向量
右奇异值 = 右特征向量
7.2 手工分解的实际例子
例1 SVD分解：
设A为 m x n矩阵， U 为 m x m 矩阵，V 为 n x n 矩阵
A = UΣV^t （公式）
参数含义:
设 U_r+1 到 U_m 为: N(A^t)
设 V_r+1 到 V_n 为： N(A)
Σ = (σ1 ... 0
..σr
0 ... 0)
V^t = ( v1 为矩阵A的特征向量集合
...
vn )
现在有 矩阵 A 如下，获取其奇异值:
A = (3 0
4 5)
因此有
A^t*A = (3 4 * (3 0 = (25 20
0 5) 4 5) 20 25)
同时有
A*A^t = (3 0 * (3 4 = (9 12
4 5) 0 5) 12 41)
V^t = 1/√2 * (1 1 = (1/√2 1/√2
-1 1) -1/√2 1/√2)
U = (1/√10 -3/√10
3/√10 1/√10)
Σ = (3√5 0
0 √5)
因此 σ1u1v1^t + σ2u2v2^t = 3/2*(1 1 + 1/2*(3 -3
3 3) -1 1)
= (3 0
4 5)
如果有100 x 100的矩阵，或 100 x 1000的矩阵，这里可能得到100个奇异值，但是人们只关心 σ1
或者前5个 σ1 ~ σ5， 也许5个奇异值就可以做相关的事情。
从SVD奇异分解开始
A = UΣV^t = σ1*u1*v1^t + ... +σr*ur*vr^t
保留k个最大的即σ1 到σk
Ak = σ1*u1*v1^t + ... +σk*uk*vk^t
Ak时最接近K阶的矩阵(closest rank A)，它最接近原矩阵A
||A - Ak || <= ||A - Bk||
一般地
||A|| = σ_max
||A||_F = √σ1^2 + ... +σr^2
||A||_N = σ1 + ... + σr
随机数值线性代数是基于此的变化。
σ1 为最大权重
σr 为最小权重
因此奇异值分解将大型矩阵分解为许多块，人们选择自己关心的，规范的想法是如何测量矩阵。
每一个巨型矩阵的随机化，都带去一次变革。 例如乘以AB 与行列采样一起
(AS)(S^t*B)
AS = (σ1 σ2 σ3)(s11 0 = (s11*σ1 s32*σ3)
0 0
0 s32)
并且S^t*B = (s11 b1^t
s32 b3^t)
注意 SS^t 不会接近I，但是可以有如下方程
E(SS^t) = I
E((AS)(S^t*B)) = AB
一般平方采样 Norm-squared sampling，选择行列的概率为
~ ||σ1||*||bi^t||
这个选择的是最小化的采样变异率。
通常数据是有规则的，数据的分析提取已经有千年历史，如果从其中提取随机样本是有深度的问题，概率论在讨论这个问题。
7.3 生成空间 - SVD 实例二
矩阵奇异值，通过奇异分解获得。
通常某些矩阵不只一种分解办法，可以使用正交分解，也可以使用奇异分解。
例二:
现在有以下矩阵，获取其奇异分解式:
A = (1 1
0 1
-1 1)
奇异分解因子公式:
A = UΣV^t
设未知数 V（特征向量集合）， 而特征值为 λ
V^t = e_set(A^t*A)
= (v1
v2)
U = [(1/σ1)*Av1
(1/σ2)*Av2
NS(A^t)/|NS(A^t)|]
Σ = (σ1 0 <=> σn = √λn （λ是特征值）
0 σ2
0 0)
因此有 A = UΣV^t = [(1/σ1)*Av1 * (σ1 0 * (v1 v2)^t
(1/σ2)*Av2 0 σ2
NS(A^t)/|NS(A^t)|] 0 0)
计算全部值
A = （1 1 => A^t*A => (2 0 => {λ1 λ2}
0 1 0 3)
1 1）
=> {3 2} ⋀ {v1 v2} = (0 1
1 0)
σ1 = √3
σ2 = √2
Σ = (√3 0
0 √2
0 0)
V 特征向量集合为
V^t = (0 1
1 0)
U = [(1/√3)*(1 1 * (0 (1/√2)*(1 1 * (1 NS(A^t) /|NS(A^t)|
0 1 1) 0 1 0)
-1 1) -1 1)
√3 为 A的奇异值的3平方根，√2为 A的奇异值 2的平方根
增广
NS(A^t) => A^t*X = 0 => (1 1 1 | 0 ~ （ 1 0 -1 | 0
1 0 -1 | 0) 0 1 2 | 0)
=> x = x3*(1
-2
1)
x3 是自由变量，假设 x3 = 1，因此：
u3 = (1 而u3长度 |u3| = √1+4+1 = √6
-2
1)
=> U = (1/√3 1/√2 1/√6
1/√3 0 -2/√6
1/√3 -1/√3 1/√6)
最后验证该结果，可正确得到初始矩阵：
A = UΣV^t = (1/√3 1/√2 1/√6 * (√3 0 * (0 1
1/√3 0 -2/√6 0 √2 1 0)
1/√3 -1/√3 1/√6) 0 0)
= (1 1
0 1
-1 1)
小结
这里通过一个例子了解了SVD的计算过程，主要包括
1 降维：SVD算法可以将高维图像数据降维到低维空间，从而提高图像处理的效率。
图像分类：SVD算法可以用于对图像进行分类。例如，可以使用SVD算法将图像分解为若干个低维特征向量，然后使用机器学习算法对这些特征向量进行分类。
图像检索：SVD算法可以用于对图像进行检索。例如，可以使用SVD算法将图像库中的图像进行降维，然后使用K-近邻算法对查询图像进行检索。
2 特征提取：SVD算法可以用于从图像中提取特征，这些特征可以用于图像识别、分类等任务.
SVD算法可以用于从图像中提取特征，这些特征可以用于图像识别、分类等任务。例如，可以使用SVD算法将图像分解为若干个低维特征向量，这些特征向量可以用来表示图像的纹理、颜色等信息。
3 图像压缩：SVD算法可以用于压缩图像，从而减少图像的存储空间。
总之，SVD算法是一种重要的矩阵分解算法，在图形识别中具有广泛的应用。
下一节继续旅程，举例说明QR正交分解及最小二乘，了解其类似于SVD过程的强大功能。
- 点赞
- 收藏
- 关注作者
评论（0）