4

I'm not a mathematician so I hope I ask this question properly; I apologize for anyone who is annoyed with how I ask it (I will try my best to be precise).

Say I have a point cloud in $\Re^3$. I wish to fit a line through to this point cloud. However - and this is the kicker - I wish to force the line through a specified point in the point cloud; that is, I wish to find a vector through a point I specify which minimizes the distance squared from all the points in the cloud to the line spanned by the vector. Does this make sense?

If I were explaining this to a non-mathematician (like me), I would say I want to "anchor" a line on one of the points and then best fit the line from there.

I understand the notion of ordinary least squares, but this particular spin on the problem doesn't make sense to me.

Thanks in advance, Ben

Ben
  • 143

3 Answers3

3

This notion makes sense. You still have two degrees of freedom for the line, which can be two angles we will call elevation $(E)$ and azimuth $(A)$. It is easiest if you move the origin to the anchor point by subtracting the coordinates of the anchor points from each of the points in the cloud. Then your line has parameterization $t(\sin E \cos A, \sin E \sin A, \cos E)$ if you measure $E$ up from the $xy$ plane and $A$ counterclockwise from the $X$ axis. Now you can find the distances from each other point in the cloud to the line using this formula where the vector I gave is $\bf n$, square them, and add them up. Now use a 2D function minimizer on $A,E$. Depending on the points, there may be local minima to fool you.

Ross Millikan
  • 374,822
  • Thanks! I will try this out and post the results here for the sake of posterity. – Ben Apr 23 '13 at 22:52
  • Like ordinary least squares, there are no "local" minima distinct from the global minimum (though in degenerate cases the location of the global minimum may not be unique). Differentiating the sum of squares "errors" with respective to the unknown parameters gives a (homogeneous) linear system to solve. – hardmath Apr 26 '13 at 00:27
1

Ross Millikan's solution will work. To get the exact answer, probably faster, you can modify a solution for finding the 3D line of best fit (without an anchor point). The way that works is you compute the covariance matrix of the point cloud and the line of best fit is the line through the centroid in the direction of the eigenvector associated with the largest eigenvalue.

To modify this solution for the current problem, you can do the same thing, only when you're computing the covariance matrix, you subtract the anchor point from each point in the point cloud, rather than subtracting the centroid.

Josh Brown Kramer
  • 141
0

The least squares fit of a line/plane/etc. with an additional constraint of passing through a specified point is usually reduced to the case where that point is the origin (subtract the specified point from all data and fit a linear homogenous function). In this connection such model fitting is called "regression through the origin" (RTO) to quickly distinguish it from ordinary least squares (OLS).

Some references and discussions are given in Answers to this previous Question.

Note that the number of parameters for a line and a plane surface in 3D are equal, but there is a difference in what the nearest distance to the line or the plane is. Passing through the origin makes the fitted model a subspace, so the nearest distance is given by (subtracting) the orthogonal projection of each data point onto the subspace.

Like ordinary least squares one gets a system of linear equations to solve for the unknown parameters, but the system is homogeneous. One is therefore solving for a nontrivial solution to a problem like $Au = 0$, and since there are only three unknowns speed of solution is not an issue.

Community
  • 1
hardmath
  • 37,015