Find the points closest to two lines using least squares method

Question

Given are two lines $g(t)=a+bt$ and $h(s)=c+ds$ with $a,b,c,d \in \mathbb R^3$. I need to find the points where the two lines are closest using the least squares method. However I am unable to find a solution for this problem.

Intuitively those points are where $g(t)-h(s)$ is as small as possible, but I don't know how to translate this into my understanding of a least squares problem. In my understanding what the least squares method does is it fits a line as close as possible to a set of given points. However given two lines this set of points seems to be infinite and therefore I don't know what that line should be. I think where I am stuck is that my understanding of the least squares method is too specific and limited to fitting straight lines.

Answer 1

As you say, you're looking for a point where $g(t) - h(s)$ is as small as possible. Let's unpack what that means.

If the two lines actually crossed, we would be looking for a point where $$bt - ds + (a-c) = 0$$ This can be written in the equivalent form as the matrix equation $$\begin{bmatrix} b & -d \end{bmatrix} \begin{bmatrix} t \\ s \end{bmatrix} = c - a$$ If we introduce the notation $A = \begin{bmatrix} b & -d \end{bmatrix}$, $\vec{x} = \begin{bmatrix} t \\ s \end{bmatrix}$, $\vec{b_0} = \begin{bmatrix} c - a \end{bmatrix}$, you want to solve $$A \vec{x} = \vec{b_0}$$ But this equation doesn't have any solutions, because the lines don't actually cross. Another way of expressing this fact is that $\vec{b_0}$ is not in $\operatorname{im} A$.

This is where least-squares suddenly kicks in. Since $\vec{b_0}$ is not in $\operatorname{im} A$, we find the point $\vec{b^*}$ that is in $\operatorname{im} A$ and is as close to $\vec{b_0}$ as possible. This point can be found by projection onto $\operatorname{im} A$:

$$\vec{b^*} = \operatorname{proj}_{\operatorname{im} A} \vec{b_0}$$

Then we want to solve the least-squares equation $$A \vec{x^*} = \operatorname{proj}_{\operatorname{im} A}\vec{b_0}$$

Can you take it from here?

Answer 2

$$f(s,t)=(g(t)-h(s))^2$$ $$\begin{cases} \frac{\partial f(s,t)}{\partial t}=2g'(t)(g(t)-h(s))=0\\ \frac{\partial f(s,t)}{\partial s}=-2h'(s)(g(t)-h(s))=0 \end{cases}$$ $$\begin{cases} b(a-c+tb-sd)=0\\ d(a-c+tb-sd)=0 \end{cases}$$ $$\begin{pmatrix} b^2&-bd\\bd&-d^2 \end{pmatrix} \begin{pmatrix} t\\s \end{pmatrix}= \begin{pmatrix} b(c-a)\\d(c-a) \end{pmatrix}$$ The linear system has one solution when $\det \begin{pmatrix} b^2&-bd\\bd&-d^2 \end{pmatrix}=-(b^2d^2-(bd)^2)\ne 0$, i.e. when $b\not\parallel d$.
When $d=xb$ for some $x\in\mathbb{R}$ then the system becomes $$b^2\begin{pmatrix} 1&-x\\x&-x^2 \end{pmatrix} \begin{pmatrix} t\\s \end{pmatrix}= \begin{pmatrix} b(c-a)\\xb(c-a) \end{pmatrix}$$ We see that the system is consistent and has solutions $$t=\frac{b(c-a)}{b^2}+xs$$ for a free variable $s$. Pluging values for $s,\,t$ back into $f$ we obtain the desired result.

Answer 3

Let $M=\pmatrix{b&-d}$. Then $$ \|(a+bt)-(c+ds)\|^2=\left\|M\pmatrix{t\\ s}-(c-a)\right\|^2. $$ Therefore, the least-norm least-square solution to the minimisation problem is given by \begin{aligned} \pmatrix{t\\ s} &=M^+(c-a)\\ &=\begin{cases} (M^TM)^{-1}M^T(c-a)&\text{if }\operatorname{rank}(M)=2,\\ \frac{1}{\operatorname{tr}(M^TM)}M^T(c-a)&\text{if }\operatorname{rank}(M)=1,\\ 0&\text{if }M=0.\\ \end{cases} \end{aligned}