We use cookies to improve your experience with our site.
林通, 刘垚, 王勃, 王立威, 查红彬. 基于局部正交性保持对齐的非线性降维方法[J]. 计算机科学技术学报, 2016, 31(3): 512-524. DOI: 10.1007/s11390-016-1644-4
引用本文: 林通, 刘垚, 王勃, 王立威, 查红彬. 基于局部正交性保持对齐的非线性降维方法[J]. 计算机科学技术学报, 2016, 31(3): 512-524. DOI: 10.1007/s11390-016-1644-4
Tong Lin, Yao Liu, Bo Wang, Li-Wei Wang, Hong-Bin Zha. Nonlinear Dimensionality Reduction by Local Orthogonality Preserving Alignment[J]. Journal of Computer Science and Technology, 2016, 31(3): 512-524. DOI: 10.1007/s11390-016-1644-4
Citation: Tong Lin, Yao Liu, Bo Wang, Li-Wei Wang, Hong-Bin Zha. Nonlinear Dimensionality Reduction by Local Orthogonality Preserving Alignment[J]. Journal of Computer Science and Technology, 2016, 31(3): 512-524. DOI: 10.1007/s11390-016-1644-4

基于局部正交性保持对齐的非线性降维方法

Nonlinear Dimensionality Reduction by Local Orthogonality Preserving Alignment

  • 摘要: 我们提出一种新的流形学习算法, 称为局部正交性保持对齐(LOPA)。该算法受局部切空间对齐(LTSA)方法的启发;LTSA方法采用仿射变换, 试图将多个局部邻域对齐到一个全局坐标系中。但是, LTSA不能保持距离和角度等原始几何量。尽管LTSA作者提出一个保持正交性的迭代对齐过程, 但是缺乏相应的数据初始化以及具体的实验结果。Procrustes子空间对齐(PSA)方法利用模拟退火来估计每一个独立的旋转变换, 最终实现了正交性保持。但是PSA的优化过程很复杂, 并且多个孤立计算的局部旋转可能产生整体的相互冲突。为了解决这些困难, 我们首先使用LTSA方法中的伪逆技巧, 将每个局部正交变换表示为统一的全局坐标。然后将正交约束进行松弛, 变成半正定规划(SDP)问题。最后采用两步迭代过程, 进一步降低正交约束中的误差。大量实验证实, LOPA算法能忠实保持原始数据集的距离、角度、内积、邻域等几何信息。实验比较发现, LOPA算法的低维嵌入表现优于PSA, 并与当前最好的算法如MVU和MVE结果相当, 但是LOPA的运行时间远远快于PSA、MVU和MVE。

     

    Abstract: We present a new manifold learning algorithm called Local Orthogonality Preserving Alignment (LOPA). Our algorithm is inspired by the Local Tangent Space Alignment (LTSA) method that aims to align multiple local neighborhoods into a global coordinate system using affine transformations. However, LTSA often fails to preserve original geometric quantities such as distances and angles. Although an iterative alignment procedure for preserving orthogonality was suggested by the authors of LTSA, neither the corresponding initialization nor the experiments were given. Procrustes Subspaces Alignment (PSA) implements the orthogonality preserving idea by estimating each rotation transformation separately with simulated annealing. However, the optimization in PSA is complicated and multiple separated local rotations may produce globally contradictive results. To address these difficulties, we first use the pseudo-inverse trick of LTSA to represent each local orthogonal transformation with the unified global coordinates. Second the orthogonality constraints are relaxed to be an instance of semi-definite programming (SDP). Finally a two-step iterative procedure is employed to further reduce the errors in orthogonal constraints. Extensive experiments show that LOPA can faithfully preserve distances, angles, inner products, and neighborhoods of the original datasets. In comparison, the embedding performance of LOPA is better than that of PSA and comparable to that of state-of-the-art algorithms like MVU and MVE, while the runtime of LOPA is significantly faster than that of PSA, MVU and MVE.

     

/

返回文章
返回