Fitting two parallel lines to a set of points

Question

In two dimension I have a set of points X = $\{x_1,..., x_N\}$. I want to fit two parallel lines to these points like $l_1$ and $l_2$ $$l_1 = p_1 + \lambda n^\perp$$ $$l_2 = p_2 + \lambda n^\perp$$ $$n^Tn=1$$

How can I solve such a problem analytically or approximately for a given importance weighting $w_i$'s.

$$\arg \max_{n,p_1,p_2} \sum_{i=1}^{N}w_i\min \left( \lVert(p_1-x_i)^Tn\rVert, \lVert(p_2-x_i)^Tn\rVert \right) $$

Note: The distances of points to lines are written in Euclidean norm for ease but it is not a constraint.

Answer 1

How about this?

Fitting one line is easy: shift the coordinates so that the average is the origin; treating the new coordinates as complex numbers, the desired line passes through the square roots of the sum of their squares.

You could then partition the sample points according to their signed distance from that line, and shift the first line by the average offset of each subgroup.

Answer 2

The difficult part in this sort of fit is assigning the points to the two lines – such assigments can often (and I suspect also in this case) not be made analytically. You need to either apply some heuristic to classify the points (e.g. by clustering), or try out the $2^{N-1}$ partitions. You might also be able to start with some guessed partition, do the fit and then use the fit to improve the partition.

In any case, for a given partition, for each subset compute the average and subtract it from all points in that subset. Then you can fit a single line through the shifted points (as described in Anton's answer: treat the coordinates as components of complex numbers and use the square roots of the sum of their squares), and then shift it back by the two averages to get the two parallel lines.

P.S.: I just realized you want to minimize the sum of distances and not squared distances. That's rather unusual and more difficult. The principles with respect to partitioning are the same, but you can't use Anton's nice fitting method, since it's derived from the minimization of the sum of squares. In any case, your weights can be included as weights in the sums as usual.