Abstract: To solve out-of-sample problem of Laplacian Eigenmaps, a method preserving local structure is proposed which is based on the assumption that there is a linear relationship between the new sample and its neighbors. Then sparse-coding is used to obtain the linear reconstruction coefficients between the new sample and its neighbors. Finally, the low-dimensional representation of the new sample is computed through the linear relationship. The classification of the low-
dimensional representation is made by 1-NN classifier. Compared with sparse-coding reconstruction method based on global relationship, the method based on local information achieves higher accuracy using less time showing its superiority. Furthermore, the proposed method can be easily extended to the out-of-sample problem of other non-linear dimensionality reduction methods.

Key words: out-of-sample extension, sparse-coding, local structure

摘要： 针对拉普拉斯特征映射的新增样本点延拓问题，提出一种基于邻域信息的新增样本点延拓方法：假设新增样本点与邻域保持线性关系，使用稀疏编码方法求解线性系数，再由这些系数在低维空间重构得到新增样本点的低维表示。使用1-NN分类算法对新增样本点的低维表示进行分类，实验结果表明，与基于全局信息的稀疏编码重构方法相比，基于邻域信息的稀疏编码重构算法使用更少的时间取得更高的分类准确率，说明该方法的有效性。此外，该方法可以推广至其他非线性降维方法的新增样本点问题。

关键词: 新增样本点延拓, 稀疏编码, 局部结构