正交线性图嵌入（OLGE）算法详解与MATLAB实现

在机器学习和数据降维领域，图嵌入（Graph Embedding）方法一直备受关注。这些方法通过构建样本之间的相似性图，来捕捉数据的局部几何结构，从而实现有效的低维表示。其中，线性图嵌入（Linear Graph Embedding, LGE）是一个通用框架，许多经典算法如PCA、LDA、LPP等都可以视为其特例。

今天我们要聊的正交线性图嵌入（Orthogonal Linear Graph Embedding, OLGE），是对LGE的改进版本。它在保持局部结构的同时，强制投影向量之间相互正交，这带来了更好的数值稳定性和更强的局部保持能力，尤其在人脸识别、文档索引等任务中表现突出。

图嵌入的基本思想

假设我们有高维数据矩阵data，每行是一个样本。图嵌入方法通常构建两个图：

• 相似图（Affinity Graph）W：W(i,j) 表示样本i和j的相似度，通常越大表示越相似（例如基于高斯核的近邻权重）。

• 约束图（Constraint Graph）D：有时用于惩罚相似样本被拉远，默认可以是单位矩阵。

标准LGE的目标是找到投影方向a，最大化：

[

a^T X^T W X a / a^T X^T D X a

]

其中X是data。这是一个广义特征值问题。

但普通LGE的投影向量不一定正交，导致在迭代求多个方向时，可能丢失一些局部信息。