对于给定一对测地线距离矩阵的流形，哪种算法可以用来生成流形的欧几里德嵌入？

Question

我有一个正方形矩阵D（当前表示为一个形状的numpy数组（572572）），似乎与一个大致圆柱形物体表面上点之间的成对距离相对应。一、 值D[i,j]对应于沿着空心圆柱表面的任何路径的最小长度。我如何构造一个三维（或n维）嵌入到欧几里德空间中，以保持那些测地距离？在

当前尝试次数

像locally linear embedding和isomap这样的算法能够得到成对测地距离矩阵并输出一个嵌入，这样成对的欧几里得距离与原始测地线相同。虽然这通常不是同一个任务，但是在输出恰好在某个维度上近似一个超立方体的情况下，由于嵌入本身是流形，因此欧几里德距离对应于测地距离，因此期望的转换实际上发生了（考虑swiss roll）。在

对于更复杂的物体，比如圆柱体，情况就不一样了。通过将测地距离视为欧几里德距离，所需圆柱上的反足点被映射到彼此相距较远的位置，相应的全局优化问题通常会导致分支结构，分支末端对应于最大距离的反足点，放大圆柱体随机采样中的小扰动。一般来说，这些算法的幼稚应用似乎不能解决手头的问题。在

另一种颇有成效（虽然昂贵）的方法是一种野蛮的蒙特卡罗方法。我用不同的参数从管状物体中随机抽取样本，直到找到一组参数，生成与我相似的测地距离矩阵，直到一个置换（通过求解将距离矩阵转换为挖掘的线性系统，并测试结果是否接近置换矩阵来处理这一问题的效率不会太低）。然后，通过找到与上述近置换矩阵最近的置换矩阵，从我的572个点到保持成对距离的对象的一个近似最优映射。在

这产生了似是而非的结果，但它以数据的形状为前提，而且成本高得惊人。我已经执行了一些更明显的优化，比如使用小随机样本而不是整个数据集，以及使用基于梯度的参数估计技术，但是更通用的技术会更好。在

注意事项

这个问题当然没有唯一的解决办法。即使假设流形可以从有限的均匀采样在3空间中明确地识别出来，仅仅挤压一个圆柱体就可以得到具有相同测地线和不同欧几里德距离的形状（因此有不同的嵌入）。这并不比LLE和Isomap产生不同的解决方案更让我烦恼，我会接受任何合理的答案。在

关于从有限样本中唯一地识别流形，为了参数起见，我可以使用来自scikit-learn包中的Isomap类中的dist_matrix_属性，而不使用任何特殊参数来查找测地线。它执行了一个不必要的MDS步骤，但成本并不高，而且可以开箱即用。然后我们希望嵌入一个最小化原始测地距离矩阵和dist_matrix_属性之间的frobenius距离的嵌入。在

Answer 1

本文的第四章是博士论文

“关于固定视点图像序列中的运动参数化”， Manfred Georg，华盛顿大学，2010年

可用：https://openscholarship.wustl.edu/cgi/viewcontent.cgi?article=1127&context=etd

讨论了其中的一些问题，并给出了一些算法，这些算法依赖于流形是否真的是一个圆柱体（或圆锥体或其他东西），以及圆柱体的相对宽度和长度。在

根据您的最终目标，类似t-SNE的替代方案可能更适合；它们完全放弃了全局测地线距离约束，因此对于圆柱体这样的形状可以更加灵活，因为这些形状无法嵌入欧几里德空间并保留测地线。在

Answer 2

虽然我最初排除了局部线性嵌入和其他类似的技术，但这似乎是仓促的。由于流形实际上是局部线性的，一个充分充分采样、足够好的流形具有这样的性质：它的小测地距离与其对应的欧几里德距离近似相同。在

有鉴于此，任何将最近的测地线邻居视为最近的欧几里德邻居并通过测地距离近似欧几里德距离的任何重构都将近似地保持全局测地距离，直至累积误差项。这意味着所有只使用局部距离的标准算法都能够提供近似正确的嵌入。这些包括但不限于

• 局部线性嵌入
• 等值线图
• 光谱嵌入

一些经典的嵌入算法在这个应用中无法正确工作，因为它们试图保持所有的距离，并且大的测地线可能是欧几里德距离的不良表示。例如，多维缩放在没有修改的情况下是不适合的。在

注意在我的初步分析中，LLE似乎产生不良结果的原因是，我的一个假设被充分充分充分采样的流形所违背。我把它应用到简单的形状和已知的期望行为，但我错误地使用了太少的点，以确保在我的分析快速反馈循环。更好的采样流形的行为完全是他们应该的。在