python - 线性 N 次等式问题的最小二乘法

Question

假设我想找到2条任意高维直线的“交点”。这两条线实际上不会相交，但我仍然想找到最相交的点(即尽可能靠近所有线的点)。

假设这些线有方向向量A、B和初始点C、D，我可以通过简单地设置一个线性最小二乘问题来找到最相交点:转换线相交方程

Ax + C = By + D

最小二乘形式

[A, -B] @ [[x, y]] = D - C 

矩阵时间向量的 @ 标准，然后我可以使用例如np.linalg.lstsq 来解决。

但是如何找到 3 条或更多条任意线的“最相交点”？如果我遵循同样的规则，我现在有

Ax + D = By + E = Cz + F

我能想到的唯一方法是将其分解为三个等式:

Ax + D = By + E
Ax + D = Cz + F
By + E = Cz + F

并将它们转换为最小二乘形式

[A, -B,  0]                 [E - D]
[A,  0, -C] @ [[x, y, z]] = [F - D]
[0,  B, -C]                 [F - E]

问题是最小二乘问题的规模随行数呈二次方增长。我想知道是否有更有效的方法来解决 n 向等最小二乘线性问题？

我在考虑 By + E = Cz + F 上面提供其他两项的必要性。但是由于这个问题没有确切的解决方案(即它们实际上并不相交)，我相信这样做会在某些变量上产生更多的“权重”？

感谢您的帮助!

编辑

我刚刚使用以下代码测试了在 n 向等式(没有其他配对)中将第一项与所有其他项配对

def lineIntersect(k, b):
    "k, b: N-by-D matrices describing N D-dimensional lines: k[i] * x + b[i]"

    # Convert the problem to least-square form `Ax = B`
    # A is temporarily defined 3-dimensional for convenience
    A = np.zeros((len(k)-1, k.shape[1], len(k)), k.dtype)
    A[:,:,0] = k[0]
    A[range(len(k)-1),:,range(1,len(k))] = -k[1:]

    # Convert to 2-dimensional matrix by flattening first two dimensions
    A = A.reshape(-1, len(k))

    # B should be 1-dimensional vector
    B = (b[1:] - b[0]).ravel()

    x = np.linalg.lstsq(A, B, None)[0]

    return (x[:,None] * k + b).mean(0)

下面的结果表明这样做不正确，因为 n 向等式中的第一项“加权不同”。

第一个输出是常规结果与不同输入顺序(行顺序无关紧要)的结果之间的差异，其中第一项没有改变。

第二个输出与第一个词没有变化相同。

k = np.random.rand(10, 100)
b = np.random.rand(10, 100)
print(np.linalg.norm(lineIntersect(k, b) - lineIntersect(np.r_[k[:1],k[:0:-1]], np.r_[b[:1],b[:0:-1]])))
print(np.linalg.norm(lineIntersect(k, b) - lineIntersect(k[::-1], b[::-1])))

结果

7.889616961715915e-16
0.10702479853076755

Answer 1

“几乎交点”的另一个标准是点 x 使得 x 到直线的距离的平方和尽可能小。就像您的标准一样，如果这些线确实相交，那么几乎相交的点将是实际的相交点。然而，我认为距离平方标准之和可以直接计算出所讨论的点:

假设我们用一个点和一个沿线的单位向量表示一条线。因此，如果一条线由 p,t 表示，则线上的点的形式为

p + l*t for scalar l

点 x 到直线 p,t 的距离平方是

(x-p)'*(x-p) - square( t'*(x-p))

如果我们有 N 条线 p[i],t[i] 那么到点 x 的距离的平方和是

   Sum { (x-p[i])'*(x-p[i]) - square( t[i]'*(x[i]-p[i]))}

展开这个我得到上面的内容

x'*S*x - 2*x'*V + K

在哪里

S = N*I - Sum{ t[i]*t[i]'}
V = Sum{ p[i] - (t[i]'*p[i])*t[i] }

并且K不依赖于x

除非所有的线都是平行的，否则 S 将是(严格)正定的，因此是可逆的，在这种情况下，我们的距离平方和是

(x-inv(S)*V)'*S*(x-inv(S)*V) + K - V'*inv(S)*V

因此最小化x是

inv(S)*V

所以练习是:归一化你的“方向向量”(并用与缩放方向相同的因子缩放每个点)，如上所述形成 S 和 V，求解

S*x = V for x