第15章-奇异值分解

第十五章奇异值分解定义与定理定义与定理•：矩阵A的奇异值分解（singularvaluedecomposition,SVD)•：矩阵A的奇异值（singularvalue)•U的列向量：左奇异向量（leftsingularvector)•V的列向量：右奇异向量（rightsingularvector)•注意奇异值分解不要求矩阵A是方阵，事实上矩阵的奇异值分解可以看作是方阵的对角化的推广。例•给定一个5x4矩阵A例•它的奇异值分解由三个矩阵的乘积给出例•矩阵是对角矩阵，对角线外的元素都是0，对角线上的元素非负，按降序排列。•矩阵U和V是正交矩阵，它们与各自的转置矩阵相乘是单位矩阵，即例•矩阵的奇异值分解不是唯一的。在此例中如果选择U为•而和V不变，那么也是A的一个奇异值分解奇异值分解基本定理•若A为一mxn实矩阵，，则A的奇异值分解存在•其中U是m阶正交矩阵，V是n阶正交矩阵，是mxn矩形对角矩阵，其对角线元素非负，且按降序排列。奇异值分解基本定理•证明•证明是构造性的，对给定的矩阵A，构造出其奇异值分解的各个矩阵。•为了方便，不妨假设m≥n，如果mn证明仍然成立。奇异值分解基本定理•(1）确定V和•首先构造n阶正交实矩阵V和mxn矩形对角实矩阵•矩阵A是mxn实矩阵，则矩阵ATA是n阶实对称矩阵。•因而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,…,vr为ATA的正特征值对应的特征向量，vr+1,…,vn为0特征值对应的特征向量，则•这就是矩阵A的奇异值分解中的n阶正交矩阵V。15.6奇异值分解基本定理•令•则是一个r阶对角矩阵，其对角线元素为按降序排列的正的，于是mxn矩形对角矩阵可以表为•这就是矩阵A的奇异值分解中的mxn矩形对角矩阵15.7奇异值分解基本定理•在式（15.6）中，V2的列向量是ATA对应于特征值为0的特征向量，因此•于是，V2的列向量构成了ATA的零空间N(ATA)，而N(ATA)=N(A)。•所以V2的列向量构成A的零空间的一组标准正交基。因此，•由于V是正交矩阵，由式（15.6）可得15.11奇异值分解基本定理•（2）确定U•接着构造m阶正交实矩阵•令•则有15.1215.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）成立奇异值分解基本定理•令为N(AT）的一组标准正交基，并令•则u1,u2,…,um构成了Rm的一组标准正交基。因此，U是m阶正交矩阵。•这就是矩阵A的奇异值分解中的m阶正交矩阵。15.16奇异值分解基本定理•（3）证明•由式（15.6)、式（15.7)、式（15.11)、式（15.14）和式（15.16）得紧奇异值分解与截断奇异值分解•又称为矩阵的完全奇异值分解（fullsingularvaluedecomposition)。•实际常用的是奇异值分解的紧凑形式和截断形式。•紧奇异值分解是与原始矩阵等秩的奇异值分解•截断奇异值分解是比原始矩阵低秩的奇异值分解。紧奇异值分解•设有mxn实矩阵A，其秋为rank(A)=r,r≤min(m,n)，则称为A的紧奇异值分解（compactsingularvaluedecomposition)，即•Ur：mxr矩阵•Vr：nxr矩阵•：r阶对角矩阵•矩阵Ur由完全奇异值分解中的U的前r列、矩阵Vr的前r列、矩阵凡由的前r个对角线元素得到。紧奇异值分解的对角矩阵的秩与原始矩阵A的秩相等。例•矩阵A的秩r=3例•A的紧奇异值分解是截断奇异值分解•在矩阵的奇异值分解中，只取最大的k个奇异值（kr,r为矩阵的秩）对应的部分，就得到矩阵的截断奇异值分解。•实际应用中提到矩阵的奇异值分解时，通常指截断奇异值分解。截断奇异值分解例•矩阵A的秩为3，•若取k=2，则其截断奇异值分解是几何解释•从线性变换的角度理解奇异值分解，mxn矩阵A表示从n维空间Rn到m维空间Rm的一个线性变换，•x和Ax分别是各自空间的向量。•线性变换可以分解为三个简单的变换：•一个坐标系的旋转或反射变换•一个坐标轴的缩放变换•另一个坐标系的旋转或反射变换•奇异值定理保证这种分解一定存在。这就是奇异值分解的几何解释。几何解释•对矩阵A进行奇异值分解，得到•,V和U都是正交矩阵•V的列向量v1,v2,…,vn构成Rn空间的一组标准正交基，表示R中的正交坐标系的旋转或反射变换•U的列向量u1,u2,…,um构成Rm空间的一组标准正交基，表示Rm中的正交坐标系的旋转或反射变换•的对角元素是一组非负实数，表示Rn中的原始正交坐标系坐标轴的倍的缩放变换。几何解释•任意一个向量，经过基于的线性变换，等价于经过坐标系的旋转或反射变换VT，坐标轴的缩放变换，以及坐标系的旋转或反射变换U，得到向量。•原始空间的标准正交基，经过坐标系的旋转变换VT、坐标轴的缩放变换刃、坐标系的旋转变换U，得到和经过线性变换A等价的结果。例•给定一个2阶矩阵•其奇异值分解为例•观察基于矩阵A的奇异值分解将R2的标准正交基•进行线性转换的情况•首先，VT表示一个旋转变换，将标准正交基e1,e2旋转，得到向量VTe1,VTe2:例•其次，表示一个缩放变换，将向量VTe1,VTe2在坐标轴方向缩放倍和倍，得到向量:•最后，U表示一个旋转变换，再将向量旋转，得到向量，也就是向量Ae1，Ae2：主要性质•（1）设矩阵A的奇异值分解为，则一下关系成立：•也就是说，矩阵ATA和AAT的特征分解存在，且可以由矩阵A的奇异值分解的矩阵表示。•V的列向量是ATA的特征向量•U的列向量是AAT的特征向量•的奇异值是ATA和AAT的特征值的平方根。主要性质•（2）在矩阵A的奇异值分解中，奇异值、左奇异向量和右奇异向量之间存在对应关系。•由易知•比较这一等式两端的第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）的一组标准正交基。标准性质•矩阵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的列•从而得到A的奇异值分解奇异值分解的计算•（1）求ATA的特征值和特征向量•计算对称矩阵W=ATA•求解特征方程•得到特征值，并将特征值由大到小排列•将特征值代入特征方程求得对应的特征向量•（2）求n阶正交矩阵V•将特征向量单位化，得到单位特征向量v1,v2,…,vn，构成n阶正交矩阵V:奇异值分解的计算•（3）求mxn对角矩阵•计算A的奇异值•构造mxn矩形对角矩阵，主对角线元素是奇异值，其余元素是零奇异值分解的计算•（4）求m阶正交矩阵U•对A的前r个正奇异值，令•得到•求AT的零空间的一组标准正交基，令•并令•（5）得到奇异值分解例•试求矩阵•的奇异值分解例•（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的奇异值分解弗罗贝尼乌斯范数•奇异值分解也是一种矩阵近似的方法，这个近似是在弗罗贝尼乌斯范数（Frobeniusnorm）意义下的近似。•矩阵的弗罗贝尼乌斯范数是向量的LZ范数的直接推广，对应着机器学习中的平方损失函数。•设矩阵，定义矩阵A的弗罗贝尼乌斯范数为弗罗贝尼乌斯范数•引理15.1弗罗贝尼乌斯范数•证明：•一般地，若Q是m阶正交矩阵，则有•因为•同样，若P是n阶正交矩阵，则有•故•即矩阵的最优近似•奇异值分解是在平方损失弗罗贝尼乌斯范数）意义下对矩阵的最优近似，即数据压缩。矩阵的最优近似15.3215.33矩阵的最优近似•证明•令为满足式（15.32）的一个矩阵。由于•下面证明于是式（15.33）成立矩阵的最优近似•设X的奇异值分解为•其中•若令矩阵B=QTAP，则A=QBPT。由此得到矩阵的最优近似•用分块方法对B分块•其中B11是kxk子矩阵，B12是kx(n-k)的子矩阵，B21是（m-k)xk子矩阵，B22是（m-k)x(n-k)子矩阵。可得矩阵的最优近似•现证B12=0，B21=0。用反证法。若B12≠0，令•则，且•这与X的定义式矛盾•因此B12=0，同样可证B21=0。于是矩阵的最优近似•再证，为此令•则，且•由知，即•最后看B22。若（m-k)x(n-k)子矩阵B22有奇异值分解，则矩阵的最优近似•证明的对角线元素为A的奇异值。为此，令•其中Ik是k阶单位矩阵，U2，V2的分块与B的分块一致注意到B及B22的奇异值分解，即得•由此可知的对角线元素为A的奇异值，故有•可证矩阵的最优近似•在秩不超过k的mxn矩阵的集合中，存在矩阵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的最优近似