2
$\begingroup$

We have n lines, each one of them is represented by a point $p_i$ which is the projection of the origin on the line and a unit vector $v_i$ which is the direction of the line.

Finding the point that minimizes the sum of squared distances is pretty easy, we can just use the fact that the point that minimizes the sum of squared distances to n points (the center of mass) is the average of them (easy to prove using partial derivatives), from that we can infer that if we project the optimal point x on all of the lines it must be the average of those points (otherwise there would have been a point that minimizes the sum more than x), and then we can use simple linear algebra to create a formula for x:

$$x = \left(\sum_{i = 1}^{n}{(I - v_iv_i^t)}\right)^{-1} \sum_{i = 1}^{n}{p_i}$$

And like explained in this answer: Sum of rejection matrices is invertible the matrix above is invertible iff not all the lines are parallel, and if they are parallel we can just take the intersection of the lines with any plane that is diagonal to the lines and take the center of mass / average of those points.

But what if we want to minimize the sum of distances instead of squared distances? And is there any linear or polynomial time algorithm that would bring us a constant approximation for the sum if not an optimal one?

$\endgroup$
1
$\begingroup$

HINT:

Say you have $f_1$, $\ldots$, $f_m$ affine functions on $\mathbb{R}^n$ and you want to minimize $$\sum_{i=1}^m |f_i(x)|$$ This is equivalent to the linear programming problem:

minimize $\sum_{i=1}^m t_i$ in $(t_1, \ldots, t_m, x)$, where $t_i \ge f_i(x)$, $t_i \ge - f_i(x)$, $i=1,\ldots, m$.

Obs: For general convex optimization problems, see for instance the courses by Prof. Stephen Boyd.

$\bf{Added:}$

The solution above only covers the case of lines in the plane.

Say now we have the problem

minimize $\sum ||A_i x + b_i||_2$

where $x \mapsto A_i x + b_i$ are affine functions from $\mathbb{R}^n$ to $\mathbb{R}^{n_i}$, $i=1, \ldots, m$.

This is reduced to the second order cone programming

minimize $\sum_{i=1}^m t_i$

where $||A_i x + b_i || \le t_i$, $i=1, \ldots, m$.

$\endgroup$
  • $\begingroup$ $f_i$ is not an affine function because it returns a vector not a number (the vector from the point x to line $i$), if you want to define $f_i$ as the size of the vector instead then it's also not affine because it has square root. Unless there is a different way to define $f_i$ that I don't see? $\endgroup$ – Tomer Wolberg Apr 5 '20 at 17:25
  • 1
    $\begingroup$ @Tomer Wolberg: You are totally right, thank you! The answer only covered the planar case. For the general case, we can use second order cone programming, I added some details. $\endgroup$ – orangeskid Apr 5 '20 at 23:02
  • $\begingroup$ I looked at it again and I'm not sure how this is reduced to SOCP. Doesn't SOCP minimizes $f^t x$? What is $f^t$ here? $\endgroup$ – Tomer Wolberg May 13 '20 at 18:56
  • 1
    $\begingroup$ @Tomer Wolberg: The variables are $(x, t_1, \ldots, t_m)$. There are constraints on the variables. And the $f$ should be $(0, 1, \ldots, 1)$ ( so in the objective function only the $t_i$'s appear). So the so called $x$ is in fact $(x,t)$. You could call that bold $x$. The name is not that important. $\endgroup$ – orangeskid May 13 '20 at 23:49
  • $\begingroup$ I think there might be a problem with this solution. If we have 5 points (not lines) in 2D space and we want to find the point that minimizes the distance to those points, we can just create 5 3D lines that pass through those points and are perpendicular to the 2D plane, then if we find the point that minimizes the sum of distances to the lines (with your algorithm) and project it back to the 2D plane we get the point that minimizes the sum of distances to the points, however there's a proof that there is no analytic solution for this problem. But I can't find any mistake in your solution. $\endgroup$ – Tomer Wolberg May 20 '20 at 14:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.