第15章 奇异值分解.pptx

1、第十五章 奇异值分解 定义与定理 定义与定理 ：矩阵A的奇异值分解（singular value decomposition, SVD) ：矩阵 A的奇异值（singular value) U的列向量：左奇异向量（left singular vector) V 的列向量：右奇异向量（right singular vector) 注意奇异值分解不要求矩阵A是方阵，事实上矩阵的奇异值分解 可以看作是方阵的对角化的推广。 例 给定一个5x4矩阵A 例 它的奇异值分解由三个矩阵的乘积 给出 例 矩阵 是对角矩阵，对角线外的元素都是0，对角线上的元素 非负，按降序排列。 矩阵U和V是正交矩阵，它们与各自

2、的转置矩阵相乘是单位矩阵， 即 例 矩阵的奇异值分解不是唯一的。在此例中如果选择U为 而 和V不变，那么 也是A的一个奇异值分解 奇异值分解基本定理 若A为一 m x n 实矩阵， ，则A 的奇异值分解存在 其中U是m阶正交矩阵，V是n阶正交矩阵， 是 m x n 矩形对角 矩阵，其对角线元素非负，且按降序排列。 奇异值分解基本定理 证明 证明是构造性的，对给定的矩阵A，构造出其奇异值分解的各个 矩阵。 为了方便，不妨假设mn，如果mn证明仍然成立。 奇异值分解基本定理 (1）确定V和 首先构造n阶正交实矩阵V和 m x n 矩形对角实矩阵 矩阵A是 m x n 实矩阵，则矩阵ATA是n阶实对

3、称矩阵。 因而ATA的特征值都是实数，并且存在一个n阶正交实矩阵V实现ATA的 对角化，使得 VT(ATA)V = A 成立 其中A是n阶对角矩阵，其对角线元素由ATA的特征值组成。 奇异值分解基本定理 而且，ATA的特征值都是非负的。事实上，令 是ATA的一个特 征值，x是对应的特征向量，则 于是 奇异值分解基本定理 可以假设正交矩阵V的列的排列使得对应的特征值形成降序排列 计算特征值的平方根（实际就是矩阵A的奇异值） 设矩阵A的秩是r, rank(A) = r，则矩阵ATA的秩也是r 奇异值分解基本定理 由于ATA是对称矩阵， 它的秩等于正的特征值的个数，所以 对应地有 令 其中v1, ,

4、vr为ATA的正特征值对应的特征向量，vr+1, ,vn为0 特征值对应的特征向量，则 这就是矩阵A的奇异值分解中的n阶正交矩阵V。 15.6 奇异值分解基本定理 令 则 是一个r阶对角矩阵，其对角线元素为按降序排列的正的 ，于是 m x n 矩形对角矩阵 可以表为 这就是矩阵A的奇异值分解中的 m x n 矩形对角矩阵 15.7 奇异值分解基本定理 在式（15.6）中，V2的列向量是ATA对应于特征值为0的特征向量， 因此 于是，V2的列向量构成了ATA的零空间N(ATA)，而N(ATA) = N(A)。 所以V2的列向量构成A的零空间的一组标准正交基。因此， 由于V是正交矩阵，由式（15.

5、6）可得 15.11 奇异值分解基本定理 （2）确定U 接着构造m阶正交实矩阵 令 则有 15.12 15.14 奇异值分解基本定理 U1的列向量构成了一组标准正交集，因为 15.15 奇异值分解基本定理 由式（15.12）和式（15.15）可知，u1, u2, ur 构成A的列空 间的一组标准正交基， 列空间的维数为r。 如果将A看成是从Rn到Rm的线性变换，则A的列空间和A的值域 R(A）是相同的。因此u1, u2, ur 也是R(A）的一组标准正交 基。 若 表示R(A)的正交补，则有R(A)的维数为r, 的 维数为 m r，两者的维数之和等于m。而且有 = N(AT）成立 奇异值分解基

6、本定理 令 为N(AT）的一组标准正交基，并令 则u1, u2, um 构成了Rm的一组标准正交基。因此，U是m阶正交 矩阵。 这就是矩阵A的奇异值分解中的m阶正交矩阵。 15.16 奇异值分解基本定理 （3）证明 由式（15.6)、式（15.7)、式（15.11)、式（15.14）和式 （15.16）得 紧奇异值分解与截断奇异值分解 又称为矩阵的完全奇异值分解（full singular value decomposition)。 实际常用的是奇异值分解的紧凑形式和截断形式。 紧奇异值分解是与原始矩阵等秩的奇异值分解 截断奇异值分解是比原始矩阵低秩的奇异值分解。 紧奇异值分解 设有 m x

7、n 实矩阵A，其秋为rank(A)=r, rmin(m,n)，则称 为A的紧奇异值分解（compact singular value decomposition)，即 Ur： m x r 矩阵 Vr： n x r 矩阵 ： r阶对角矩阵 矩阵Ur 由完全奇异值分解中的U的前r列、矩阵Vr的前r列、矩阵 凡由 的前r个对角线元素得到。紧奇异值分解的对角矩阵 的秩与 原始矩阵A的秩相等。 例 矩阵A的秩r = 3 例 A的紧奇异值分解是 截断奇异值分解 在矩阵的奇异值分解中，只取最大的k个奇异值（kr, r为矩阵 的秩）对应的部分，就得到矩阵的截断奇异值分解。 实际应用中提到矩阵的奇异值分解时，通

8、常指截断奇异值分解。 截断奇异值分解 例 矩阵A的秩为3， 若取k=2，则其截断奇异值分解是 几何解释 从线性变换的角度理解奇异值分解， m x n 矩阵A表示从n维空间Rn到 m维空间Rm的一个线性变换， x和Ax分别是各自空间的向量。 线性变换可以分解为三个简单的变换： 一个坐标系的旋转或反射变换 一个坐标轴的缩放变换 另一个坐标系的旋转或反射变换 奇异值定理保证这种分解一定存在。这就是奇异值分解的几何解释。 几何解释 对矩阵A进行奇异值分解，得到 ,V和U都是正交矩阵 V的列向量v1, v2, , vn构成Rn空间的一组标准正交基，表示R中 的正交坐标系的旋转或反射变换 U的列向量u1,

9、 u2, , um构成Rm空间的一组标准正交基，表示 Rm 中的正交坐标系的旋转或反射变换 的对角元素 是一组非负实数，表示Rn中的原始正交 坐标系坐标轴的 倍的缩放变换。 几何解释 任意一个向量 ，经过基于 的线性变换，等价于 经过坐标系的旋转或反射变换VT，坐标轴的缩放变换 ，以及 坐标系的旋转或反射变换U，得到向量 。 原始空间的标准正交基， 经过坐标系的旋转变换VT、 坐标轴的缩放变换刃、 坐标系的旋转变换U， 得到和经过线性变换A等价的结果。 例 给定一个2阶矩阵 其奇异值分解为 例 观察基于矩阵A的奇异值分解将R2的标准正交基 进行线性转换的情况 首先，VT表示一个旋转变换，将标准

10、正交基e1, e2旋转，得到向 量VT e1, VT e2: 例 其次， 表示一个缩放变换，将向量VT e1, VT e2 在坐标轴方向 缩放 倍和 倍，得到向量 : 最后，U表示一个旋转变换，再将向量 旋转，得到 向量 ，也就是向量Ae1，Ae2： 主要性质 （1）设矩阵A的奇异值分解为 ，则一下关系成立： 也就是说，矩阵ATA和AAT的特征分解存在，且可以由矩阵A的奇异 值分解 的矩阵表示。 V的列向量是ATA的特征向量 U的列向量是AAT的特征向量 的奇异值是ATA和AAT的特征值的平方根。 主要性质 （2）在矩阵A的奇异值分解中，奇异值、左奇异向量和右奇异向量之 间存在对应关系。 由

11、易知 比较这一等式两端的第j列，得到 这是矩阵A的右奇异向量和奇异值、 左奇异向量的关系 类似地，由 得到 这是矩阵A的左奇异向量和奇异值、右奇异向量的关系。 主要性质 （3）矩阵A的奇异值分解中，奇异值 是唯一的，而 矩阵U和V不是唯一的。 （4）矩阵A和 的秩相等，等于正奇异值 的个数r（包含 重复的奇异值）。 主要性质 （5） 矩阵A的r个右奇异向量v1, v2, , vr构成AT的值域R(AT）的一组 标准正交基。 因为矩阵AT是从Rm映射到砂的线性变换，则AT的值域R(AT ）和AT 的列空间是相同的， v1, v2, , vr是AT的一组标准正交基，因 而也是R(AT ）的一组标准

12、正交基。 标准性质 矩阵A的n-r个右奇异向量vr+1,vr+2, ,vn构成A的零空间N(A)的一 组 标准正交基。 矩阵A的r个左奇异向量u1, u2, , ur构成值域R(A）的一组标准 正交基。 矩阵A的m-r个左奇异向量ur+1,ur+2, ,um构成AT的零空间N(AT ） 的 一组标准正交基。 奇异值分解的计算 矩阵A的奇异值分解可以通过求对称矩阵ATA的特征值和特征向量 得到。 ATA的特征向量构成正交矩阵V的列 ATA的特征值 的平方根为奇异值 ，即 对其由大到小排列作为对角线元素，构成对角矩阵 求正奇异值对应的左奇异向量，再求扩充的AT的标准正交基，构 成正交矩阵U的列 从

13、而得到A的奇异值分解 奇异值分解的计算 （1）求ATA的特征值和特征向量 计算对称矩阵W=ATA 求解特征方程 得到特征值 ，并将特征值由大到小排列 将特征值 代入特征方程求得对应的特征向量 （2）求n阶正交矩阵V 将特征向量单位化，得到单位特征向量v1,v2, ,vn，构成n阶正 交矩阵V: 奇异值分解的计算 （3）求 m x n 对角矩阵 计算A的奇异值 构造 m x n 矩形对角矩阵 ，主对角线元素是奇异值，其余 元素是零 奇异值分解的计算 （4） 求m阶正交矩阵U 对A的前r个正奇异值，令 得到 求AT的零空间的一组标准正交基 ，令 并令 （5）得到奇异值分解 例 试求矩阵 的奇异值分

14、解 例 （1）求ATA的特征值和特征向量 得到齐次线性方程组 例 该方程有非零解的充要条件是 解此方程，得矩阵ATA的特征值 和 。 将特征值代入线性方程组，得到对应的单位特征向量 例 （2）求正交矩阵V 构造正交矩阵V （3）求对角矩阵 奇异值为 和 构造对角矩阵 例 （4）求正交矩阵U 基于A的正奇异值计算得到列向量u1 列向量u2, u3是AT的零空间N(AT)的一组标准正交基 例 求解 分别取(x2, x3)为(1,0)和(0,1)，得到N(AT)的基 N(AT)的一组标准正交基是 构造正交矩阵U 例 （5）矩阵A的奇异值分解 弗罗贝尼乌斯范数 奇异值分解也是一种矩阵近似的方法，这个近

15、似是在弗罗贝尼乌 斯范数（Frobenius norm）意义下的近似。 矩阵的弗罗贝尼乌斯范数是向量的LZ范数的直接推广，对应着机 器学习中的平方损失函数。 设矩阵 ，定义矩阵A的弗罗贝尼乌斯范数为 弗罗贝尼乌斯范数 引理15.1 弗罗贝尼乌斯范数 证明： 一般地，若Q是m阶正交矩阵，则有 因为 同样，若P是n阶正交矩阵，则有 故 即 矩阵的最优近似 奇异值分解是在平方损失弗罗贝尼乌斯范数）意义下对矩阵的最 优近似，即数据压缩。 矩阵的最优近似 15.32 15.33 矩阵的最优近似 证明 令 为满足式（15.32）的一个矩阵。由于 下面证明 于是式（15.33）成立 矩阵的最优近似 设X的奇

16、异值分解为 其中 若令矩阵B=QTAP，则A=QBPT。由此得到 矩阵的最优近似 用 分块方法对B分块 其中B11是 k x k 子矩阵，B12是 k x (n-k) 的子矩阵，B21是（m-k) x k 子矩阵，B22 是（m-k) x (n-k)子矩阵。可得 矩阵的最优近似 现证B12=0， B21=0。 用反证法。若B120，令 则 ，且 这与X的定义式 矛盾 因此B12=0， 同样可证B21=0。于是 矩阵的最优近似 再证 ，为此令 则 ，且 由 知， 即 最后看B22。若（m-k) x (n-k)子矩阵B22有奇异值分解 ，则 矩阵的最优近似 证明 的对角线元素为A的奇异值。为此，令

17、 其中Ik是k阶单位矩阵，U2，V2的分块与B的分块一致注意到B及B22 的奇异值分解，即得 由此可知 的对角线元素为A的奇异值，故有 可证 矩阵的最优近似 在秩不超过k的 m x n 矩阵的集合中，存在矩阵A的弗罗贝尼乌斯 范数意义下的最优近似矩阵X 是达到最优值的一个矩阵 紧奇异值分解是在弗罗贝尼乌斯范数意义下的无损压缩 截断奇异值分解是有损压缩 截断奇异值分解得到的矩阵的秩为k，通常远小于原始矩阵的秩r， 所以是由低秩矩阵实现了对原始矩阵的压缩。 矩阵的外积展开式 矩阵A的奇异值分解 也可以由外积形式表示 若将A的奇异值分解看成矩阵 和VT的乘积，将 按列向 量分块，将VT按行向量分块，即得 矩阵的外积展开式 则 即 A的外积展开式也可写为 A的外积展开式 矩阵的外积展开式 由矩阵A的外积展开式知，若A的秩为n，则 设矩阵 则Ak的秩为k，并且Ak是秩为k矩阵在弗罗贝尼乌斯范数意义A的最 优近似矩阵 矩阵Ak就是A的截断奇异值分解 由于通常奇异值 递减很快，所以k取很小值时，Ak也可以对A 有很好的近似。 例 给出矩阵A 的秩为3，求A的秩为2的最优近似 例 从前列已知 于是得到 ，以此矩阵为A的最优近似