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

Question

假设我要求任意2条高维直线的"intersection point"。两条线实际上不会相交，但我仍然想找到最相交的点（即尽可能靠近所有线的点）。

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

Ax + C = By + D

最小二乘形式

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

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

但是我怎样才能找到3个或更多任意行的"most intersect point"呢？如果我遵循同样的规则，我现在有

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 上面提供其他两个术语的必要性。但是由于这个问题没有确切的解决方案（即它们实际上并不相交），我相信这样做会在某些变量上创建更多 "weight"?

感谢您的帮助！

编辑

我刚刚测试了使用以下代码

在 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 向等式中的第一项是 "weighted differently"。

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

第二个输出与第一个词相同。

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

不是解决方案，一些想法：

如果 nD space 中的线有参数方程（单位 Dir 向量）

 L(t) = Base + Dir * t

那么从点 P 到这条线的平方距离是

W = P - Base
Dist^2 = (W - (W.dot.Dir) * Dir)^2

如果可以将Min(Sum(Dist[i]^2))写成适合LSQ方法的形式（对每个点坐标进行偏导），那么结果系统可能会求解(x1..xn)坐标向量。

(情况类似于通常LSQ的多点单线反转)

Answer 2

这个问题可能更适合数学堆栈交换。另外，这里有人有格式化数学的好方法吗？抱歉，它很难阅读，我已经尽力使用 unicode。

编辑：我误解了 @ZisIsNotZis 行 Ax+C 的意思，所以请忽略下一段。

I'm not convinced that your method is stated correctly. Would you mind posting your code and a small example of the output (maybe in 2d with 3 or 4 lines so we can plot it)? When you're trying to find the intersection of two lines shouldn't you do Ax+C = Bx+D? If you do Ax+C=By+D you can pick some x on the first line and some y on the second line and satisfy both equations exactly. Because here x and y should be the same size as A and B which is the dimension of the space rather than scalars.

有很多方法可以理解找到一个尽可能靠近所有线的点的问题。我觉得最自然的就是每条线的欧式距离平方和最小化。

假设我们在 R^n 中有一条线：c^Tz + d = 0（其中 c 是单位长度）和另一个点 x。那么从x到直线的最短向量是：(I-cc^T)(x-d)所以从x到直线的距离的平方是║(I-cc^T)(x-d)║^2。我们可以通过最小化这个距离找到离直线最近的点。请注意，这是 min_x ║b-Ax║_2.

形式的标准最小二乘问题

现在，假设我们有 c_iz+d_i 为 i=1,...,m 给出的行。从点 x 到第 i 条线的平方距离 d_i^2 是 d_i^2 = ║(I-cc^T)(x-d)║_2^2。我们现在要解决min_x \sum_{i=1}^{m} d_i^2.

的问题

在矩阵形式中我们有：

      ║ ⎡ (I-c_1 c_1^T)(x-d_1) ⎤ ║
      ║ | (I-c_2 c_2^T)(x-d_2) | ║
min_x ║ |      ...             | ║
      ║ ⎣ (I-c_n c_n^T)(x-d_n) ⎦ ║_2

这又是 min_x ║b - Ax║_2 的形式，所以有很好的求解器可用。

每个块的大小为 n（space 的维度）并且有 m 个块（行数）。所以系统是mn byn。特别是，它在行数上是线性的，在 space 的维度上是二次方的。

它的另一个优点是，如果您添加一条线，您只需将另一个块添加到最小二乘系统。这也提供了在添加行时迭代更新解决方案的可能性。

我不确定是否有针对此类最小二乘系统的特殊求解器。请注意，每个块都是标识减去一阶矩阵，因此这可能会提供一些可用于加快速度的额外结构。也就是说，我认为使用现有的求解器几乎总是比自己编写更好，除非您有相当多的数值分析背景或有非常专业的 class 系统来求解。

Answer 3

你说你有两条 "high-dimensional" 行。这意味着表示行的矩阵的列数比行数多得多。

如果是这种情况并且您可以有效地找到低秩分解使得 A=LRᵀ，那么您可以重写最小二乘问题的解决方案 min ||Ax-y||₂ as x=(Rᵀ RLᵀ L)⁻¹ Lᵀ y.

如果 m 是线的数量，n 是线的维度，那么这减少了最小二乘时间复杂度O(mn²+nʷ) 到 O(nr²+mr²) 其中 r=min(m,n).

接下来的问题就是找到这样的分解。

Answer 4

'almost intersection point' 的另一个标准是点 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

所以练习是：规范化你的 'direction vectors'（并用与缩放方向相同的因子缩放每个点），如上形成 S 和 V，求解

S*x = V for x

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

Least square on linear N-way-equal problem

python

algorithm

numpy

linear-programming

least-squares