然后是图拉普拉斯的最优化问题的构造

图拉普拉斯是要找到高维向量的一个低维流形，该流形能够保持数据的分布特征，具体的说就是让高维空间相近的点（也就是高维向量，这里看作点比较直观）在低维空间也相近，在高维空间相隔远的点在低维空间也离得远。

在这篇Paper，保持数据特征的具体实现方法就是Locality Preserving Projection(LPP)，它将问题简化， 只考虑与每个点最邻近的点 （k nearest neighbors，所以整个数据就变成了 图的形式 了，只考虑每个点的邻边），让它们在低维空间保持近邻的分布，别的点就不管了。

如下图的公式所示，高维空间两个点xi和xj映射到一维空间后结果为yi和yj，LPP希望找到一个w向量 (yi=w' * xi) ，使得以下目标函数最小

然后就是一通数学推导

这个L=D-S就是我们要的图拉普拉斯矩阵。这个推导只要注意一下Dii的下标就可以了，不算很复杂。

最后这个优化问题可以化作求特征值的问题：

后面这篇文章还分析了LPP与LDA和PCA的关系，以及用在人脸识别的性能。这里就不详细说了，我写这个博客只是想来填补图拉普拉斯矩阵这个空白的。

参考文献:

He, Xiaofei, et al. "Face recognition using Laplacianfaces." Pattern Analysis and Machine Intelligence, IEEE Transactions on 27.3 (2005): 328-340.

https://live.bilibili.com/11928465 对于几乎所有 机器学习 算法，无论是有监督学习、无监督学习，还是强化学习，最后一般都归结为求解 最优化 问题... 图 像算法八 —— 多种边缘检测算法（Sobel算子、Isotropic Sobel算子、Roberts算子、Prewitt算子、Laplacian算子、Canny算子）介绍及比较 如引用请务必注明此文出自：http://www.cnblogs.com/xbinworld 继续写一点经典的降维算法，前面介绍了PCA,LDA，LLE，这里讲一讲Laplacian Eigenmaps。 其实不是说每一个算法都比前面的好，而是每一个算法都是从不同角度去看问题，因此解决问题的思路是不一样的。这些降维算法的思想都很简单，却在有些方面很有效。这些方法事实上是后面一些新的算法的思... 正交PCA LPP 代码实现 文章目录正交PCA LPP 代码实现0.引言1.原理1.1 PCA目标函数1.2 LPP 目标函数1.3 CVPCA LPP 原理2.方案验证3.结论 ​ 传统基于主成分分析 (Principal component analysis, PCA) 的数据降维方法在提取有效特征信息时只考虑全局结构保持而未考虑样本间的局部近邻结构保持问题, 本文提出一种改进全局结构保持算法的特征提取与降维方法，改进的特征提取与降维方法将 流形学习 中局部结构保持 ( Local ity pre servi n 4.算法步骤 算法全称《 Local ity pre servi ng projection s》出自何小飞教授论文X.He,P.Niyogi, Local ity pre servi ng projection s,in:Proceedi ng sofConference on AdvancesinNeuralInformationProcessi ng Systems(NIP... gDLPCA 文章目录思想PCAgLPCAgDLPCA优化求解gDLPCA算法 参考论文：Graph-dual Laplacian principal component analysis 作者：Jinro ng He · Yi ng zhou Bi · Bin Liu · Zhigao Ze ng 近年来，研究表明，高维数据不仅存在于数据空间的低维流形上，特征也存在于特征空间的流形上。然而PC... 具体步骤如下所示： 1.确定 LPP 的目标函数：min⁡12∑i,j(yi−yj)2sij \min \frac{1}2\sum_{i, j}(y_{i}-y_{j})^{2} s_{i j} min21​i,j∑​(yi​−yj​)2sij​ 其中yiy_iyi​表示的是降维后的任意数据点iii，yjy_jyj​表示的是降维后的任意数据点不包含iii。 其中sijs 拉普拉斯 变形是 图 形学处理mesh的常用方法，它假定mesh的顶点，在变化前后，顶点的 拉普拉斯 距离应该是一致的。L=D−A=D(I−D−1A)D是每个顶点的度，A是邻接矩阵。假设有变形前的顶点为V，有L*V，将其拆解，可以发现就是求每个顶点i的顶点位置减去相邻的顶点位置*(1/di​)。LV1​=Vi​−j∈Ni​∑​di​1​Vj​j是顶点i的邻接顶点索引。因此，拉谱拉斯矩阵中保存了顶点的局部信息。