有限度量嵌入:好的算法？

Question

我有一个有限度量空间给定为(对称)k乘k距离矩阵.我想要一种算法(近似)在欧几里德空间R ^(k-1)中等距地嵌入它.虽然通过求解距离给出的方程组并不总是可以完成,但我正在寻找一种嵌入了一些(非常小的)可控误差的解决方案.

我目前使用多维缩放(MDS),输出维度设置为(k-1).在我看来,通常MDS可能会针对您尝试将环境嵌入维度减少到小于(k-1)(通常为2或3)的情况进行优化,并且可能有更好的算法用于我的限制案件.

问题:使用欧氏距离在R ^ {k-1}中实现大小为k的度量空间的好/快算法是什么？

一些参数和指针:

(1)我的k相对较小.说3 <k <25

(2)我实际上并不关心我是否嵌入了R ^ {k-1}.如果它简化了事物/使事情变得更快,任何R ^ N也会很好,只要它是等距的.如果我有一个更快的算法,或者如果我增加到R ^ k或R ^(2k + 1),我会很高兴.

(3)如果你可以指向python实现,我会更高兴.

(4)任何比MDS更好的东西都能奏效.

Answer 1

好的，正如这里所承诺的一个简单的解决方案：

符号：d_{i,j}=d_{j,i}表示点和之间的平方距离。让为点数。让表示该点和该点的第​​一个坐标。ijNp_iip_{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设置坐标。即对于第二个点，我们仅设置第一个坐标，对于第三个点，我们仅设置第一个和第二个坐标等。kk > i-1

现在假设我们有所有点 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

因为 和p_{i,k}都p_{j,k}等于零，所以k>k'我们可以将其简化为：

d_{i,j} = \sum_{k=1}^k' (p_{i,k} - p_{j,k} )^2

另请注意，根据循环不变式，p_{j,k}当 时，所有值都为零k>j-1。所以我们拆分这个方程：

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 来实现它来测试它。