svd(奇异值分解)算法及其评估

《svd(奇异值分解)算法及其评估》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、SVD（奇异值分解）算法及其评估本文第一部分对SVD进行了简单的介绍，给出了定义和奇异值分解定理；第二部分简要地列举了SVD的应用；第三部分则构造和分析了各种求解SVD的算法，特别对传统QR迭代算法和零位移QR迭代算法进行了详细完整的分析；第四部分给出了复矩阵时的处理办法；第五部分是对各种算法的一个简要的总结。一、SVD简介mn×T定义1.1设AR∈，AA的特征值的非负平方根称作A的奇异值；A的奇异值的全体记作σ(A)[1]。mn×TH当A为复矩阵C时，只需将AA改为AA，定义1.1仍然成立。mn×定理1.

2、1（奇异值分解定理）设AR∈，则必存在正交矩阵mm×nn×UuuR=[1,...,m]∈和VvvR=[1,...,n]∈使得Σ0rTrUAV=，…(1.1)00mr−rnr−其中Σ=diag(,...,σσσ),≥≥>...σ0[2]。r11rrmn×当A为复矩阵C时，只需将定理中UV,改为酉矩阵，其它不变，定理1.2仍然成立[1]。称分解式(1.1)为矩阵A的奇异值分解，通常简称为SVD。σ是A的奇异值，向i量u和v分别是第i个左奇异向量和第i个右奇异向量。ii从A的奇异值分解，我们可以得到A

3、的一些非常有用的信息，下面的推论就列举其中几条最基本的结论[1]：mn×推论1.2设AC∈，则r(1)A的非零奇异值的个数就等于r=rankA()；(2)vv,...,是()A的一组标准正交基；rn+1(3)uv,...,是()A的一组标准正交基；1rrH(4)A=∑σiiiuv称为A的满秩奇异值分解；i=1其中()A，()A分别指得是A的零空间和值域。为了方便，我们采用如下表示奇异值的记号：σ()AA＝的第i大奇异值；iσ()AA＝的最大奇异值；maxσ()AA＝的最小奇异值。min现在来考察矩阵

4、奇异值的几何意义[1,2]，不妨设mn=，此时有nnE={y∈=∈=C:,,1yAxxCx}n21是一个超椭球面，它的n个半轴长正好是A的n个奇异值σσ≥≥≥≥...σ0，这些12n轴所在的直线正好是A的左奇异向量所在的直线，它们分别是对应的右奇异向量所在直线的象。一般地我们假设mn≥，（对于mn<的情况，我们可以先对A转置，然后进行奇异值分解，最后对所求得的SVD分解式进行转置就可以得到原式SVD分解式），此时我们对(1.1)进行化简将U表示为：UUU=(,),…(1.2)12则可以得到更加细腻的SVD分

5、解式[2,3]：TAUV=Σ…(1.3)1其中U具有n列m维正交向量，V和(1.1)式中的定义相同；Σ=diag(,σσ,...,σ)，112n并且σσ≥≥≥≥...σ0为矩阵A的奇异值。12n二、SVD应用在现代科学计算中SVD具有广泛的应用，在已经比较成熟的软件包LINPACK中列举的应用有以下几点[3]:(1)确定矩阵的秩(rank)假设矩阵A的秩为r，那么A的奇异值满足如下式子σ≥≥>...σσ===...σ0；11rr+n反之，如果σ≠0，且σσ=...==0，那么矩阵A的秩为r，这样奇异值rrn

6、+1分解就可以被用来确定矩阵的秩了。事实的计算中我们几乎不可能计算得到奇异值正好等于0，所以我们还要确定什么时候计算得到的奇异值足够接近于0，以致可以忽略而近似为0。关于这个问题，不同的算法有不同的判断标准，将在给出各种算法的时候详细说明。(2)确定投影算子假设矩阵A的秩为r,那么我们可以将(1.3)式中的U划分为以下的形式1(1)(1)UUU=(,)112(1)(1)其中U为mr×的矩阵，并且U的列向量构成了矩阵A的列空间的正交向11量基。(1)(1)T容易得到PUU=为投影到矩阵A的列空间上的正交投影算

7、子；而A11⊥(1)(1)TPUUUU=(,)(,)则是到矩阵A列空间的正交补空间上的投影。A2222同理如果将V划分为以下的形式VVV=(,)12其中V为nr×的矩阵，则V的列向量构成矩阵A的行空间的正交向量11T⊥T基。且R=VV为投影到矩阵A的行空间上的正交投影算子；而R=VVA11A22则是到矩阵A行空间的正交补空间上的投影。(3)最小二乘法问题(LS问题)2促进人们研究SVD并且应用SVD比较早的应该是最小二乘法问题了，在前一份关于QR分解的报告已经对LS问题进行了一些介绍，这里继续讨论SVD在L

8、S问题中的应用。mn×mnLS问题即相当于，设AR∈(mnbR>∈),，求xR∈使得nAxb−=min{Avb−∈:vR}.……(2.1)22T假设已知矩阵A有式子(1.1)得到的SVD分解式为UVΣ，U和V分别为mn,阶正交方阵，而∑为和A具有相同维数的对角矩阵，那么我们可以得到[4]：TAxbUVxb−=Σ−TT=Σ−UVxUUb()()......(2.2)=Σ−Uyc()TT其中yVx=，cUb=。因为U