Find a point that minimizes the sum of distances to n lines (not square distances!).

Question

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?

Answer 1

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$.