SVD算法的全面介绍
SVD（奇异值分解）算法及其评估
本文第一部分对SVD进行了简单的介绍，给出了定义和奇异值分解定理；第二部分简要地列举了SVD的应用；第三部分则构造和分析了各种求解SVD的算法，特别对传统QR迭代算法和零位移QR迭代算法进行了详细完整的分析；第四部分给出了复矩阵时的处理办法；第五部分是对各种算法的一个简要的总结。
一、 SVD简介
定义1.1 设A Rm n，ATA的特征值的非负平方根称作A的奇异值；A的奇异值的全体记作 A [1]。
当A为复矩阵Cm n时，只需将ATA改为AHA，定义1.1仍然成立。 定理1.1（奇异值分解定理） 设A Rm n，则必存在正交矩阵
U u1,...,um Rm m和V v1,...,vn Rn n 使得
UTAV r
0
rn r
0 r
，…(1.1) 0 m r
其中 r diag( 1,..., r), 1 ... r 0[2]。
，其它当A为复矩阵Cm n时，只需将定理中U,V改为酉矩阵（Unitary Matrix）
不变，定理1.2仍然成立[1]。
称分解式(1.1)为矩阵A的奇异值分解，通常简称为SVD。 i是A的奇异值，向量ui和vi分别是第i个左奇异向量和第i个右奇异向量。
从A的奇异值分解，我们可以得到A的一些非常有用的信息，下面的推论就列举其中几条最基本的结论[1]：
推论1.2 设A Crm n，则
(1) A的非零奇异值的个数就等于r rank(A) ； (2) vr 1,...,vn是 (A)的一组标准正交基；
(3) u1,...,vr是 (A)的一组标准正交基； (4) A iuiviH称为A的满秩奇异值分解；
i 1r
其中 (A)， (A)分别指得是A的零空间和值域。
为了方便，我们采用如下表示奇异值的记号： i(A)＝A的第i大奇异值； max(A)＝A的最大奇异值； min(A)＝A的最小奇异值。
现在来考察矩阵奇异值的几何意义[1,2]，不妨设m n，此时有 En y Cn:y Ax,x Cn,x2 1