没有合适的资源?快使用搜索试试~ 我知道了~
首页SVD(奇异值分解)算法及其评估
SVD(奇异值分解)算法及其评估
5星 · 超过95%的资源 需积分: 12 15 下载量 148 浏览量
更新于2023-06-16
评论
收藏 420KB PDF 举报
本文第一部分对SVD进行了简单的介绍,给出了定义和奇异值分解定理;第二部分简要地列举了SVD的应用;第三部分则构造和分析了各种求解SVD的算法,特别对传统QR迭代算法和零位移QR迭代算法进行了详细完整的分析;第四部分给出了复矩阵时的处理办法;第五部分是对各种算法的一个简要的总结。
资源详情
资源评论
资源推荐
1
SVD(奇异值分解)算法及其评估
本文第一部分对 SVD 进行了简单的介绍,给出了定义和奇异值分解定理;第二
部分简要地列举了 SVD 的应用;第三部分则构造和分析了各种求解 SVD 的算法,
特别对传统 QR 迭代算法和零位移 QR 迭代算法进行了详细完整的分析;第四部分
给出了复矩阵时的处理办法;第五部分是对各种算法的一个简要的总结。
一、 SVD 简介
定义 1.1 设
mn
AR
×
∈
,
T
AA
的特征值的非负平方根称作
A
的奇异值;
A
的奇异
值的全体记作
( )
A
σ
[1]。
当
A
为复矩阵
mn
C
×
时,只需将
T
AA
改为
H
AA
,定义 1.1 仍然成立。
定理 1.1(奇异值分解定理) 设
mn
AR
×
∈
,则必存在正交矩阵
[ ]
1
,...,
mm
m
Uu u R
×
= ∈
和
[ ]
1
,...,
nn
n
Vv v R
×
= ∈
使得
0
00
r
T
r nr
r
U AV
mr
−
Σ
=
−
,…(1.1)
其中
11
( ,..., ), ... 0
r rr
diag
σ σσ σ
Σ= ≥ ≥ >
[2]。
当
A
为复矩阵
mn
C
×
时,只需将定理中
,UV
改为酉矩阵,其它不变,定理 1.2 仍
然成立[1]。
称分解式(1.1)为矩阵
A
的奇异值分解,通常简称为 SVD。
i
σ
是
A
的奇异值,向
量
i
u
和
i
v
分别是第
i
个左奇异向量和第
i
个右奇异向量。
从
A
的奇异值分解,我们可以得到
A
的一些非常有用的信息,下面的推论就列
举其中几条最基本的结论[1]:
推论 1.2 设
mn
r
AC
×
∈
,则
(1)
A
的非零奇异值的个数就等于
()r rank A=
;
(2)
1
,...,
rn
vv
+
是
()A
的一组标准正交基;
(3)
1
,...,
r
uv
是
()A
的一组标准正交基;
(4)
1
r
H
iii
i
A uv
σ
=
=
∑
称为
A
的满秩奇异值分解;
其中
()A
,
()A
分别指得是
A
的零空间和值域。
为了方便,我们采用如下表示奇异值的记号:
() A
i
A
σ
=
的第
i
大奇异值;
max
() AA
σ
=
的最大奇异值;
min
() A
A
σ
=
的最小奇异值。
现在来考察矩阵奇异值的几何意义[1,2],不妨设
mn=
,此时有
{ }
2
: , ,1
nn
n
E y C y Ax x C x=∈=∈ =
2
是一个超椭球面,它的
n
个半轴长正好是
A
的
n
个奇异值
12
... 0
n
σσ σ
≥ ≥≥ ≥
,这些
轴所在的直线正好是
A
的左奇异向量所在的直线,它们分别是对应的右奇异向量所
在直线的象。
一般地我们假设
mn≥
,(对于
mn<
的情况,我们可以先对
A
转置,然后进行
奇异值分解,最后对所求得的 SVD 分解式进行转置就可以得到原式 SVD 分解式),
此时我们对(1.1)进行化简将
U
表示为:
12
( , ),U UU=
…(1.2)
则可以得到更加细腻的 SVD 分解式[2,3]:
1
T
AUV= Σ
…(1.3)
其中
1
U
具有
n
列
m
维正交向量,
V
和(1.1)式中的定义相同;
12
( , ,..., )
n
diag
σσ σ
Σ=
,
并且
12
... 0
n
σσ σ
≥ ≥≥ ≥
为矩阵
A
的奇异值。
二、 SVD 应用
在现代科学计算中 SVD 具有广泛的应用,在已经比较成熟的软件包 LINPACK
中列举的应用有以下几点[3]:
(1) 确定矩阵的秩(rank)
假设矩阵
A
的秩为
r
,那么
A
的奇异值满足如下式子
11
... ... 0
rr n
σ σσ σ
+
≥≥ > == =
;
反之,如果
0
r
σ
≠
,且
1
... 0
rn
σσ
+
= = =
,那么矩阵
A
的秩为
r
,这样奇异值
分解就可以被用来确定矩阵的秩了。
事实的计算中我们几乎不可能计算得到奇异值正好等于 0,所以我们还
要确定什么时候计算得到的奇异值足够接近于 0,以致可以忽略而近似为 0。
关于这个问题,不同的算法有不同的判断标准,将在给出各种算法的时候详
细说明。
(2) 确定投影算子
假设矩阵
A
的秩为
r
,那么我们可以将(1.3)式中的
1
U
划分为以下的形式
( )
(1) (1)
1 12
,U UU=
其中
(1)
1
U
为
mr×
的矩阵,并且
(1)
1
U
的列向量构成了矩阵
A
的列空间的正交向
量基。
容易得到
(1) (1)
11
T
A
P UU=
为投影到矩阵
A
的列空间上的正交投影算子;而
(1) (1)
2222
( ,)( ,)
T
A
P UUUU
⊥
=
则是到矩阵
A
列空间的正交补空间上的投影。
同理如果将
V
划分为以下的形式
( )
12
,V VV=
其中
1
V
为
nr×
的矩阵,则
1
V
的列向量构成矩阵
A
的行空间的正交向量
基。且
11
T
A
R VV=
为投影到矩阵
A
的行空间上的正交投影算子;而
22
T
A
R VV
⊥
=
则是到矩阵
A
行空间的正交补空间上的投影。
(3) 最小二乘法问题(LS 问题)
3
促进人们研究 SVD 并且应用 SVD 比较早的应该是最小二乘法问题了,
在前一份关于 QR 分解的报告已经对 LS 问题进行了一些介绍,这里继续讨
论 SVD 在 LS 问题中的应用。
LS 问题即相当于,设
mn
AR
×
∈
( ),
m
m nb R
>∈
,求
n
xR∈
使得
22
min{ : }.
n
Ax b Av b v R−= − ∈
……(2.1)
假设已知矩阵
A
有式子(1.1)得到的 SVD分解式为
T
UV
Σ
,
U
和
V
分别为
,mn
阶正交方阵,而
∑
为和
A
具有相同维数的对角矩阵,那么我们可以得到[4]:
( ) ( )......(2.2)
()
T
TT
AxbUVxb
U V x UUb
U yc
−=Σ −
=Σ−
= Σ−
其中
T
y Vx
=
,
T
c Ub=
。
因为
U
是一正交矩阵,所以
2 22
()Axb U yc yc− = Σ− =Σ−
,从而把原
最小二乘法问题化为求使
2
ycΣ−
最小的
y
这一最小二乘法问题,因为
Σ
为
对角矩阵,所以使得新的这一最小二乘法问题简单的多,接着将对此仔细分
析[4]。
假设矩阵
A
的秩为
r
,则有:
11
0
0
0
rr
y
y
y
σ
σ
Σ=
,
11 1
1
2
rr r
r
r
m
yc
yc
yc c
c
c
σ
σ
+
+
−
−
Σ− = −
−
−
可知
/ ,( 1,2,..., )
i ii
yc i r
σ
= =
使得
ycΣ−
达到它的最小长度
1/2
2
1
m
i
ir
c
= +
∑
,并且可
见当
rm=
时,上面的这一长度为 0,也就是当矩阵
A
的列张成
m
空间时最
小二乘法问题可以无误差地求解。而当
rn<
时,
1
,...,
kn
yy
+
可以任意取,而
不影响
ycΣ−
的长度。
我们将对
∑
转置并且对非零的对角元素求逆所得到的矩阵定义为
+
∑
,
那么
yc
+
= Σ
的前
r
个元素将等于
/ ,( 1,2,..., )
ii
ci r
σ
=
,并且其余的元素为 0。
并且由
T
y Vx
=
,
T
c Ub=
,容易得到:
......(2.3)
T
x V Ub
+
= ∑
由此得到的是 LS 问题的最小范数解。
而文献[3]中还给出了一般通解的形式如下:
2
......(2.4)
T
x V U b Vw
+
=∑+
其中
2
V
如前定义,而
w
是任意的
nr−
维向量。
4
(4) 广义逆问题(pseudo-inverse)
记
T
AVU
++
= ∑ ,从(2.3)式我们可以看出,最小二乘法的解为
x Ab
+
=
,
和一般的线性方程组
Ax b=
的解为
1
x Ab
−
=
相类似,所以我们当我们已知矩
阵
A
的奇异值分解
T
A UV= Σ
后可以定义
A
的广义逆为
T
AVU
++
= ∑
。
(5) 条件数
如果已知矩阵
A
的秩为
r
,那么在式子(2.3)中,解
x
随着矩阵
A
的扰动
而改变的剧烈程度有多大呢?这可以用矩阵的条件数来衡量,条件数的定义
如下:
1
( ) / ......(2.5)
rr
A
κ σσ
=
以上只是针对 SVD 的应用,而简单地介绍了 LS 问题,广义逆;而在文献[5,6]
中则对这两个问题有详细的说明,在以后的报告中也将进行更进一步的分析,并且
综合其它方法来全面分析和处理这些问题。
除了这些传统的应用以外,在图像压缩和大型数据库的数据恢复中,SVD 也具
有广泛的应用[7]。
三、 各种 SVD 算法及其特点
首先来对 SVD 算法的发展来做简单的回顾[11,12]:关于 SVD 算法的研究最早
可以追溯到 1873 年 Beltrami 所做的工作,这中间在理论方面进行了大量的工作,这
个历史过程可以参考 Stewart 的文献[8]。但是直到 1965 年 Golub 和 Kahan 才在 SVD
的数值计算领域取得突破性进展[9],并且于 1969 给出了比较稳定的算法[10](以下
简称传统 QR 迭代算法),这也是后来在 LINPACK 中所采用的方法[3]。它的中心思
想是用正交变换将原矩阵化为双对角线矩阵,然后再对双对角线矩阵迭代进行 QR
分解。
六十年代一份没有出版的技术报告中,Kahan 证明了双对角线矩阵的奇异值可
以精确地计算,具有和原矩阵元素的相对的精确度;进一步,1990 年 Demmel 和
Kahan 给出了一种零位移的 QR 算法(zero-shift QR algorithm),这种算法计算双对角
矩阵的奇异值具有很高的相对精度[13],并且由此得到的奇异向量也具有很高的精
度[14]。
Fernando 和 Parlett 在 1994 年将 qd 算法应用到奇异值的计算上,从而得到了一
种全新的比 zero-shift QR algorithm 更加精确和快速的计算奇异值的算法[15,16]。
而 Demmel 和 Veselic 在文献[17]中则说明了用 Jacobi 方法与其它方法相比计算
所得到的奇异值和奇异向量具有更高的精度,可惜 Jacobi 算法比 DK 算法速度要慢
的多;在文献[18]中对 Jacobi 方法进行了改进使得其在速度上几乎和 DK 算法相当。
和 Strassen 算法类似,SVD 问题也有快速的分而制之算法,在文献[19,20]对其
有详细的介绍,由此得到的算法在总计算量上比现有的 LAPACK 软件包中所采用的
方法要少的多。
在文献[21,22]中给出的 bisection 算法也可以对双对角线矩阵计算得到具有相对
精度的全部奇异值。
以下就开始对各种算法原理进行详细说明,并分析它们的计算量,计算的精确
度,以及所占得内存。
5
3.1:传统 QR 迭代算法[1,2,3]
设
()
mn
AR mn
×
∈≥
,可知奇异值分解可从实对称矩阵
T
C AA=
的 Schur 分解导出
[1],因此我们自然想到先利用对称 QR 方法来实现 C 的 Schur 分解,然后借助 C 的
Schur 分解来实现 A 的奇异值分解,然而这样做有两个缺点:一是计算
T
C AA=
要
很大的计算量;二是计算
T
C AA
=
会引入较大的误差。因此 Golub 和 Kahan 在 1965
年提出了另一种十分稳定的方法,其基本思想就是隐含地应用对称 QR 算法于
T
AA
上,而并不需要将
T
C AA=
计算出来。
方法第一步是:将 A 二对角化,即求正交矩阵
1
U
和
1
V
,使得
11
0
n
T
mn
B
U AV
−
=
……(3.1.1)
其中
12
23
000
0 00
00 0
000
0000
n
n
B
δγ
δγ
γ
δ
=
……(3.1.2)
分解式(3.1.1)可以用 Householder 变换来实现,将 A 分块为
[ ]
11
11n
AvA
−
=
先计算 m 阶 Householder 变换
1
P
使得
11 11 1 1
(, )
m
Pv e R e R
δδ
= ∈∈
并且形成:
1
11
1
1
1
T
u
PA
m
A
=
−
再计算 n-1 阶 Householder 变换
1
H
使得
1
11 21 2 1
(, )
n
Hu e Re R
γγ
−
= ∈∈
并形成:
[ ]
11 2 2
12n
AH v A
−
=
然后对
2,3,..., 2kn= −
依次进行:
(a) 计算 m-k+1 阶 Householder 变换
k
P
使得
1
11
(, )
mk
kk k k
Pv e R e R
δδ
−+
= ∈∈
并且形成:
1
1
T
k
kk
k
u
PA
m
A
=
−
(b) 计算 n-k 阶 Householder 变换
k
H
使得
剩余42页未读,继续阅读
whucs小牛-诺维斯基
- 粉丝: 1
- 资源: 5
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- RTL8188FU-Linux-v5.7.4.2-36687.20200602.tar(20765).gz
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
- SPC统计方法基础知识.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论2