最小化n维点集的欧几里得距离 [英] minimize euclidean distance from sets of points in n-dimensions

问题描述

让我们看一下nd空间中的m个点-(这里是3维空间中4个点的解决方案:

Let's look at m points in n-d space- (A solution for 4 points in 3-d space is here: minimize distance from sets of points)

a= (x1, y1, z1, ..)

b= (x2, y2 ,z2, ..)

c= (x3, y3, z3, ..)
.
.

p= (x , y , z, ..)

Find point q = c1* a + c2* b + c3* c + ..

where c1 + c2 + c3 + .. = 1
and  c1, c2, c3, .. >= 0
s.t.
euclidean distance pq is minimized.

可以使用哪些算法?想法或伪代码就足够了. (在这里，优化性能是一个大问题.具有所有顶点和变化系数的蒙特卡洛方法也将提供解决方案.)

What algorithms can be used ? Idea or pseudocode is enough. (Optimizing performance is a big issue here. Monte Carlo method with all vertices and changing coefficients would also give a solution.)

推荐答案

我们可以通过从所有其他点中减去p来假设p = 0.然后的问题之一就是最小化一组有限点(即多面体)的凸包上的范数.

We can assume p = 0 by subtracting p from all the other points. Then the question is one of minimizing the norm over a convex hull of a finite set of points, i.e., a polytope.

关于此问题有几篇论文. Sekitani Kazuyuki Sekitani和Yoshitsugu Yamamoto的一种递归算法用于找到一个多面体中的最小范数点和一对最接近点对中的递归算法"看起来是一个很好的方法，并且对该问题的现有解决方案进行了简短的调查.它位于付费专区的后面，但是如果您可以访问大学图书馆，则可以下载副本.

There are a few papers on this problem. It looks like "A recursive algorithm for finding the minimum norm point in a polytope and a pair of closest points in two polytopes" by Kazuyuki Sekitani and Yoshitsugu Yamamoto is a good one, with a short survey of prior solutions to the problem. It is behind a paywall but if you have access to a university library you may be able to download a copy.

一旦您超过了表示法，他们给出的算法就非常简单. P是点的有限集. C(P)是其凸包. Nr(C(P))是最小范数的唯一点，这就是您想要找到的.

The algorithm they give is fairly simple, once you get past the notation. P is the finite set of points. C(P) is its convex hull. Nr(C(P)) is the unique point of minimum norm, which is what you want to find.

第0步:从有限点P的凸包C(P)中选择一个点x_0.他们建议选择x_0作为P中具有最小范数的点.令k = 1.

Step 0: Choose a point x_0 from the convex hull C(P) of your finite set of points P. They recommend choosing x_0 to be the point in P with minimum norm. Let k=1.

现在循环:

步骤1:设a_k =最小值{x ^ t_ {k-1} p | p在P}中.这里x ^ t_ {k-1}是x_ {k-1}的转置(因此最小化的函数只是点积，因为p超出了有限集P).如果| x_ {k-1} | ^ 2< = a_k，则答案为x_ {k-1}，请停止.

Step 1: Let a_k = min {x^t_{k-1} p | p is in P}. Here x^t_{k-1} is the transpose of x_{k-1} (so the function being minimized is just a dot product as p ranges over your finite set P). If |x_{k-1}|^2 <= a_k, then the answer is x_{k-1}, stop.

步骤2:P_k = {p |在P中的p和x ^ t_ {k-1} = a_k}. P_k是在步骤1中使表达式最小化的P的子集.对该集合P_k递归调用算法，并将结果设为y_k = Nr(C(P_k)).

Step 2: P_k = {p | p in P and x^t_{k-1} = a_k}. P_k is the subset of P that minimizes the expression in Step 1. Call the algorithm recursively on this set P_k, and let the result be y_k = Nr(C(P_k)).

步骤3:b_k =分钟{y ^ t_k p | p \ P_k}中的p，是y_k与补集P \ P_k中的点的乘积的最小值.如果| y_k | ^ 2< = b_k，则y_k是答案，请停止.

Step 3: b_k = min{y^t_k p | p in P\P_k}, the minimum of the dot product of y_k with points in the complement set P\P_k. If |y_k|^2 <= b_k then y_k is the answer, stop.

步骤4:s_k = max {s |对于P \ P_k中的每个p，[(1-s)x_ {k-1} + sy_k] ^ t y_k< = [[1-s)x_ {k-1} + sy_k] ^ t p.令x_k =(1-s_k)x_ {k-1} + s_k y_k，令k = k + 1，然后返回步骤1.

Step 4: s_k = max{s| [(1-s)x_{k-1} + sy_k]^t y_k <= [(1-s)x_{k-1} + sy_k]^t p for every p in P\P_k}. Let x_k = (1-s_k) x_{k-1} + s_k y_k, let k=k+1, and go back to Step 1.

第4步中有一个针对s_k的明确公式:

There is an explicit formula for s_k in Step 4:

s_k =分钟{[x ^ t_ {k-1}(p-y_k)]/[(y_k-x_ {k-1})^ t(y_k-p)] | p \ P_k中的p和(y_k-x_ {k-1})^ t(y_k-p)> 0}

s_k = min{ [x^t_{k-1} (p-y_k)]/[(y_k-x_{k-1})^t (y_k-p)] | p in P\P_k and (y_k - x_{k-1})^t (y_k-p) > 0 }

有论文证明s_k具有必要的属性，该算法在有限次操作后终止，并且结果确实是最优的.

There is a proof in the paper that s_k has the necessary properties, that the algorithm terminates after a finite number of operations, and that the result is indeed optimal.

请注意，您应该在比较中增加一些公差，否则舍入错误可能会导致算法失败.关于数值稳定性的讨论很多，有关详细信息，请参见本文.

Note that you should add some tolerance into your comparisons, otherwise rounding errors may cause the algorithm to fail. There is a lot of discussion about numerical stability, see the paper for details.

他们没有对算法的计算复杂性进行完整的分析，但确实证明了在二维情况下(m是P中的点数)它最多为O(m ^ 2)，并且他们进行了数值实验，给人的印象是时间在时间​​上是线性的，是m的函数，并且尺寸是固定的.我对此说法表示怀疑.在没有详细分析的情况下，建议您尝试使用典型数据进行一些实验，以了解该算法对您的效果如何.

They do not give a complete analysis of the computational complexity of the algorithm, but they do prove it is at most O(m^2) in the two-dimensional case (m is the number of points in P), and they have done numerical experiments which give the impression that it is sublinear in time as a function of m, with dimension fixed. I'm skeptical of that claim. In the absence of a detailed analysis, I suggest you try some experiments with typical data to see how well the algorithm performs for you.

这篇关于最小化n维点集的欧几里得距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！