我有一个给定的有限度量空间，它是一个(k x k)的距离矩阵（对称的）， 我希望有一种算法可以将其(近似)等距地嵌入到欧几里得空间 R^(k-1) 中。虽然通过解方程组来精确嵌入不总是可能的，但我正在寻找一种具有一些(非常小的)可控误差的解决方案。
我目前使用输出维度设置为 (k-1) 的多维缩放 (MDS)。我发现通常情况下，MDS 可能是针对你试图将周围的嵌入维数缩小到某个小于 (k-1) 的值(通常是2或3)，而在我的限制情况下可能会有更好的算法。
问题: 有没有好的/快速的算法可以实现大小为k的度量空间到欧几里得空间R^(k-1) 中的等距嵌入?
一些参数和指针:
(1) 我的k相对较小。 比如说3 < k < 25
(2) 实际上我并不在乎是否嵌入到 R^(k-1)。如果这能简化事情/使事情更快，任何 R^N 只要是等距的都可以，我很高兴如果有更快的算法或者误差更小的算法，如果我增加到R^k或R^(2k+1)。
(3) 如果您可以指向一个Python实现，我会更开心。
(4) 任何比 MDS 更好的方法都可以。
好的，如承诺的一样，这里是一个简单的解决方案：
符号说明：设 d_{i,j}=d_{j,i} 表示点 i 和 j 之间的平方距离。设 N 表示点的数量。设 p_i 表示点 i，p_{i,k} 表示点的第 k 个坐标。
希望我现在能正确地推导出算法。稍后会有一些解释，以便您可以检查推导过程（我讨厌出现许多指数时的感觉）。
该算法使用动态规划来得出正确的解决方案。
Initialization:
p_{i,k} := 0 for all i and k
Calculation:
for i = 2 to N do
sum = 0
for j = 2 to i - 1 do
accu = d_{i,j} - d_{i,1} - p_{j,j-1}^2
for k = 1 to j-1 do
accu = accu + 2 p_{i,k}*p_{j,k} - p_{j,k}^2
done
p_{i,j} = accu / ( 2 p_{j,j-1} )
sum = sum + p_{i,j}^2
done
p_{i,i-1} = sqrt( d_{i,0} - sum )
done
如果我没有犯任何严重的索引错误（我通常会犯），这应该能解决问题。
这背后的想法：
我们将第一个点任意设置为原点，以使我们的生活更轻松。对于点 p_i，我们从不在 k > i-1 时设置坐标 k。也就是说，对于第二个点，我们只设置第一个坐标，对于第三个点，我们只设置第一个和第二个坐标等等。
现在假设我们已经有了所有点 p_{k'} 的坐标，其中 k'<i，我们想要计算 p_{i} 的坐标，以满足所有的 d_{i,k'}（我们还不关心 k>k' 的点的任何约束）。如果我们写下方程组，我们有：
d_{i,j} = \sum_{k=1}^N (p_{i,k} - p_{j,k} )^2
因为对于 k>k'，p_{i,k} 和 p_{j,k} 都等于零，所以我们可以将其简化为：
d_{i,j} = \sum_{k=1}^k' (p_{i,k} - p_{j,k})^2
请注意，根据循环不变式，当k>j-1时，所有的p_{j,k}都将为零。因此，我们将这个方程分成两部分：
d_{i,j} = \sum_{k=1}^{j-1} (p_{i,k} - p_{j,k})^2 + \sum_{k=j}^{k'} p_{i,j}^2
对于第一个方程，我们得到：
d_{i,1} = \sum_{k=1}^{j-1} (p_{i,k} - p_{j,k})^2 + \sum_{k=j}^{k'} p_i{i,1}^2
这个需要稍后进行特殊处理。
现在，如果我们解决正常方程中的所有二项式，我们得到：
d_{i,j} = \sum_{k=1}^{j-1} p_{i,k}^2 - 2 p_{i,k} p_{j,k} + p_{j,k}^2 + \sum_{k=j}^{k'} p_{i,j}^2
将第一个方程式从中减去，你会得到：
d_{i,j} - d_{i,1} = \sum_{k=1}^{j-1} p_{j,k}^2 - 2 p_{i,k} p_{j,k}
对于所有的 j > 1。
如果你看一下这个式子，你会发现所有的 p_i 坐标的平方都消失了，我们只需要已知的平方。这是一组线性方程，可以使用线性代数的方法轻松解决。实际上，这组方程还有一个特殊之处：这些方程已经处于三角形式，所以你只需要进行最后一步解决方案的传递。对于最后一步，我们只剩下一个二次方程，我们可以通过取一个平方根来解决它。
希望你能理解我的推理。现在有点晚了，我的头有点晕乎乎的。
编辑：是的，有一些索引错误。已经修复。我会在有时间的时候尝试用Python实现它以进行测试。