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.

  • 1
    $\begingroup$ As an approximation I think of replacing $\min(a,b)$ with $ab/(a+b)$ but can not reach to a point. $\endgroup$ – xonobo Sep 19 '15 at 10:44

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.

  • $\begingroup$ I don't expect an analytical solution as you point out the partitioning and fitting problems are need to be solved together. Sum of distances may help in suppressing the outliers but sum of distance squares is also ok. $\endgroup$ – xonobo Sep 19 '15 at 10:28
  • 1
    $\begingroup$ @xonobo: I see. I think if you do sum of distances and not squared distances, you'd need to subtract the median instead of the average, but the median point may be different along different directions, so this might introduce further need for iterative correction, where you could subtract the median along some direction, then fit the lines, and then check whether the median along the direction of the fitted lines is the same; else iterate. (Again, you could take your weights into account in forming the median.) $\endgroup$ – joriki Sep 19 '15 at 10:34

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.

  • $\begingroup$ This can turn out very bad in a situation where you have two clusters far apart with each cluster corresponding to one of the lines; the fit will give you the line connecting the clusters irrespective of the actual orientation of the lines. $\endgroup$ – joriki Sep 19 '15 at 9:42
  • $\begingroup$ Consider a case that 10 points are on line y=0 and 5 points are on y=1. There is a clear/trivial solution for this case but your method would give some tilted parallel lines I guess. $\endgroup$ – xonobo Sep 19 '15 at 10:36

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.