奇异值分解与主成分

1、数值实验03：奇异值分解与主成分分析选作问题（研究性的）6、 假设数据源是一系列的图像，每幅图像都是一个矩阵。分别用经典的主成分分析方法和奇异值分解方法计算特征脸。注意数据的中心化与归一化处理的影响。（1）奇异值分解：是一个能够适用于任意矩阵的一种分解方法：Am*n = Um*måm*nVn*nTU为M*M 方阵（ U里面的正交向量称为左奇异向量），å 是一个M*N的矩阵（除了对角线的元素都是 0，对角线上的元素称为奇异值）， VT是一个N*N 的方（V 里面正交的向量称为右奇异向量）。我们将一个矩阵 A的转置乘以 A，并对 ATA 求特征值（ATA）vi=ivi则v就为右

2、奇异向量，且奇异值si = i，左奇异值ui=Avii s就为奇异值，u就为奇异向量。奇异值s 跟特征值类似，在矩阵中也是从大到小排列，而且s的减少特别的快，在很多情况下，前10%甚至1%的奇异值的和就占了全部的奇异值之和的99%以上了。也就是说，我们也可以用前r大的奇异值来近似描述矩阵，部分奇异值分解：Am´n » Um ´r å r´rVTr´n （r是一个远小于 m、n的数）给定一幅 M*N大小的图像，将它表示成 M*N*1 维向量，向量中元素为像素点的 灰度，按行存储，则如下公式分别表示第 i 张图片和 n 张图片的平均值：令

3、 M*N*n 矩阵 X 为：即中心化，将坐标原点移动到平均值位置。设Q = XXT ,则Q是一个MN * MN 矩阵：Q 被称为协方差矩阵。 那么X中每一个元素xj可以表达成：其中ei 是非零特征值对应的特征向量，对于 M*N 图像， e1,e2,.,en 是M*N*1 维相互正交的向量。尺度gji 是xj在空间中的坐标。为了降维，可以对特征值设定阈值或按照其他准则，寻找协方差矩阵Q中前 k个特征向量。Q为 M*N*M*N,通常很庞大。考虑矩阵P = XTXQ 的大小为 M*N*M*N,而P的大小为 n*n，N 为训练样本图像数量，通常 n<<M*N 设e是矩阵 P 的特征值l对应

4、的特征向量，则有：Pe = leXTXe = leXXTXe = lXeQ(Xe) = l( Xe)所以 X*e 是矩阵Q 的特征值l对应的特征向量。这就是用求特征值分解的方法。 对Q进行奇异值分解 QMN * MN = UMN * MNåMN * MNVMN * MNU就是QQT的特征向量， V就是QTQ 的特征向量， å中奇异值的平方就是QQT 和QTQ的特征值。（2）主成分分析（PCA）的原理就是将一个高维向量x,通过一个特殊的特征向量矩阵U，投影到一个低维的向量空间中，表征为一个低维向量y，并且仅仅损失了一些次要信息。也就是说，通过低维表征的向量和特征向量矩阵，可以

5、基本重构出所对应的原始高维向量。 在人脸识别中，特征向量矩阵U称为特征脸空间，因此其中的特征向量ui进行量化后可以看出人脸轮廓，在下面的实验中可以看出。 设有n个人脸训练样本，每个样本由其像素灰度值组成一个向量xi，则样本图像的像素点数即为xi 的维数，由向量构成的训练样本集为𝑥1,𝑥2,𝑥𝑛。 该样本集的平均向量为: 平均向量又叫平均脸。样本集的协方差矩阵为： 求出协方差矩阵的特征向量ui和对应的特征值i ，这些特征向量组成的矩阵U就是人脸空间的正交基底，用它们的线性组合可以重构出样本中任意的人脸图像。并且图像信息集中在特征值大

6、的特征向量中，即使丢弃特征值小的向量也不会影响图像质量。将协方差矩阵的特征值按从大到小顺序：。由大于d的i对应的特征向量构成主成分，主成分构成的变换矩阵为： 这样每一幅人脸图像都可以投影到构成的特征脸子空间中。 MATLAB实践：选取16 张人脸图像作为数据源，大小为80×80（这里的人脸图像要求大小相同，人眼部位尽可能对齐），把图像存储为80×80,16的矩阵A，每列表示一张图像，每行代表同一个位置的像素，因此一共有80×80个维度。中心化时各自减去每个维度的均值，由于图像数据的量纲一样，所以不需要归一化。16 张人脸为： (a) 对X用经典的主成分分析法计算特

7、征脸,取前15个对应主成分特征脸：通常情况下MN>>P的,而矩阵非零特征值的个数为minMN-1,P-1,所以在实现中使用维数少的P*P矩阵来代替理论上的协方差矩阵（MN*MN），减少计算。接着我们根据PCA算法的理论对得到的特征值进行排序，并舍弃一部分特征值（所占能量少，即特征值小的部分）在实现中我们设定的阈值为1，保留特征值大于1的，小于1的将被舍弃。由此我们再求得协方差矩阵的特征向量，并且此特征向量就是所谓的“特征脸”。 平均脸 特征脸 特征脸 特征脸 平均脸 特征脸 特征脸 特征脸 特征脸 特征脸 特征脸 特征脸 特征脸 特征脸 特征脸 特征脸(b) 对X用奇异值方法计算特

8、征脸，取前15个对应主成分特征脸:采用svd分解来得到特征值和特征向量。平均脸 特征脸 特征脸 特征脸特征脸 特征脸 特征脸 特征脸特征脸 特征脸 特征脸 特征脸特征脸 特征脸 特征脸 特征脸由于SVD 与PCA 得到的特征向量可能符号相反，所以特征脸不同。7、 奇异值分解与主成分分析是线性的降维方法。研究非线性的方法如LLE，并应用于适当选择的数据进行计算。分析和研究LLE与PCA的差别。答: （1）LLE分析：LLE（局部线性嵌入）方法是流形学习的一种算法。流形学习，它是用非线性方法去发现高维数据潜在的低维流形，然后在低维流形坐标上展示出这种流形结构。总之，流形学习是把一组高维空间中的数据

9、在低维空间中重新展示，最终达到降维的目的。假设是原始高维空间的N个样本点，通过流行学习，发现嵌入在高维空间中的低维流形，。LLE是一种局部优化算法，其基本思想是：认为在局部意义下，数据的结构是线性的，因此在局部区域内数据点可以用其近邻点的线性组合来近似表示，即，这样在数据点和其近邻点之间就构造了一个重构权，由此重构权组成的权向量恰好保持了高维数据的局部线性结构，在低维空间中也保持这种局部的线性结构，即在低维空间中有。因为局部区域内是近似地由和线性表示出来的，因此会有误差存在，此误差尽管不能消除，但可以使其达到最小，故引入误差函数：其限制条件为：1）若不在的邻域内，则；2）若在的邻域内，则，且满

10、足。（2）LLE算法的实现在MATLAB实现中，我们将LLE的实现用下述函数表示：其中X为我们的数据集，它是一个D*N的矩阵，D为采样点的维度，N为采样点的个数；K为近邻点的个数，d是我们想要降到的维度，最终输出为降维后新的d*N矩阵。步骤一：利用欧式距离 求得每个数据点的K个紧邻点步骤二：根据第一步求取的紧邻点对数据线性重构并计算重构权值矩阵。将误差函数化简为：利用拉格朗日乘子法在的约束条件下，求的最小值，即：对上式求导并令其为0，则可推出：其中，为k维全1列向量。MATLAB对重构权值矩阵的实现如下：步骤三：求低维嵌入Y由于重构权向量所描述的流形的局部几何结构在降维后也是保持不变的。因此，

11、利用上步求得的在低维空间内重构，使下面局部重建损失函数最小：为了限定低维数据均匀分布和避免产生退化解，对Y加了两个约束条件： 利用拉格朗日乘子，并结合约束条件得： 上式对Y求导得：，所以，则有，M最小的d个（2d+1）非零特征值所对应特征向量为，则即为所求的低维嵌入（最小特征值为0时不能反映原始数据的特征，所以必须舍弃）（3）比较PCA与LLE的区别:（a）从降维方法来看：降维方法通常分为线性降维和非线性降维。线性降维是假设高维数据位于全局线性的结构中，使得降维后的低维数据能保持数据点的线性关系，PCA是常用的线性降维方法；但当数据是非线性时，线性降维方法将破坏原始数据间的拓扑结构，无法探索数

12、据间的内部规律，因此出现了揭示数据间非线性性质的非线性降维方法，流形学习是非线性降维方法的一个重要分支。总之，PCA的特点是全局线性；LLE特点是局部线性、全局非线性。（b）从适用性来看：对于非线性的高维数据，LLE算法能展现其流形分布，而PCA可能会发生明显扭曲而失效。PCA可能会使流形中相隔很远的点映射到低维空间后变得相近，这样便很难揭示其流形分布；而LLE能保持原始数据拓扑结构不变。由于PCA的目的是寻找最小均方意义下最能够代表原始数据的投影方法（寻找最优方向），所以PCA对椭球状分布的样本集有很好的效果，学习所得的主方向就是椭球的主轴方向。而LLE适用于分布均匀并稠密的数据集的降维，而当数据集的分布稀疏时，数据点的关联性较弱，选择的k近邻容易造成信息选取方向的缺失，线性重构误差大。（c）从算法实现来看：PCA将方差的大小作为保持原始高维数据信息量多少标准，通过求解中心化和归一化后的数据集协方差矩阵的特征值和特征向量，设置一定的阈值，留下特征值大于阈值的那部分特征向量来实现降维；而LL