摘要： 局部线性嵌入(LLE)算法可以发现隐藏在高维空间中的局部线性低维流形，实现数据降维，而LLE算法对数据噪声比较敏感，在较强噪声下算法稳定性很差。为此，提出一种基于稀疏约束的改进算法，在计算重构误差的表达式后添加L1范数的惩罚性约束，促使最优重构权值矩阵更具有稀疏性。通过正则化处理，把添加稀疏约束的重构误差最优化目标函数变换成一般二次规划问题，引入内点迭代法快速搜索最优解。仿真实验结果表明，在不同噪声影响下，稀疏约束的改进LLE算法的降维效果明显好于经典LLE算法，具有更强的噪声抵抗能力。

关键词: 稀疏约束, 局部线性嵌入, 流形学习, 鲁棒性, L1范数, 内点迭代法

Abstract: Locally Linear Embedding(LLE) algorithm can achieve data dimensionality reduction by finding the local linear low-dimensional manifold hidden in the high-dimensional space. The LLE algorithm is sensitive to noise, moreover, the stability of the algorithm is very poor when exposed to strong noise. This paper proposes a sparse constraint improvement method, by adding L1 norm punitive constraint to the reconstruction error function, the optimal reconstruction weight matrix is sparser. Transform the reconstruction error function which adds the sparse constraint into a general quadratic programming problem by regularization, and uses interior-point iteration method to search the optimal solution quickly. Simulation experimental results of the typical high-dimensional data set dimensionality reduction show that the dimensionality reduction results of the LLE algorithm in sparse constraint is significantly better than the classic LLE algorithm under the influence of different noise, and has a stronger ability in resisting noise.

Key words: sparse constraint, Locally Linear Embedding(LLE), manifold learning, robustness, L1-norm, interior-point iteration method

中图分类号: 

• TP311