线性图嵌入（LGE）算法详解与MATLAB高效实现

线性图嵌入（LGE）算法详解与MATLAB高效实现

在流形学习和子空间学习领域，基于图的降维方法（如 LPP、NPE、LSDA 等）通过构造样本间的相似图和约束图，捕捉数据的局部几何结构，从而实现有效的低维嵌入。线性图嵌入（Linear Graph Embedding, LGE）正是这些方法的统一线性框架，它将各种图嵌入算法抽象为一个广义特征值问题：

[ a^* = \arg\max_a \frac{a^T X^T W X a}{a^T X^T D X a} ]

其中：

• (X) 为数据矩阵（每行为一个样本）

• (W) 为相似图（Affinity graph），表示样本间应保持的相似关系

• (D) 为约束图（Constraint graph），表示应抑制的方向（默认单位矩阵 I）

不同的 (W) 和 (D) 构造方式对应不同的经典算法，例如 LPP、LSDA、NPE 等。LGE 的优势在于提供了一个通用、高效的求解器，能够处理高维数据和小样本奇异性问题。

本文详细解析一个工程化的 LGE MATLAB 实现，它支持 PCA 预降维、正则化、Cholesky 加速以及智能特征值求解策略，适用于各种基于图的线性降维任务。

核心优化目标与求解思路

LGE 的目标是寻找投影方向 (a)，使投影后相似样本（由 (W) 定义）尽可能靠近，而约束方向（由 (D) 定义）尽可能分离。

当分母矩阵 (X^T D X) 奇异（常见于高维小样本）时