Least square approximation for straight line fit (normal form)

Question

I am doing a straight line best fit for certain data set. I am using the normal form of straight line. Suppose I have a set of points (x_1,y_1), (x_2,y_2), ... , (x_n,y_n). Suppose the normal form of a straight line is x*cos(theta) + y*sin(theta) = r.

So in my case I have the following set of equations:

x_1 cos(theta) + y_1 sin(theta) = r

x_2 cos(theta) + y_2 sin(theta) = r

...

x_n cos(theta) + y_n sin(theta) = r

I want to solve the equation for theta and r in least square fashion & trying to write the equations in the form of Ax=b. But in this case I can't separate the unknowns in vector x to solve the equations. Any suggestion?

Answer 1

As you can easily see there are more equations than unknowns so in general there is no way to find an exact solution. For a least square solution you start by writing the least square expression, here that would be the sum of the squared distances of the points from the line. If you want the complete theory you better ask at http://math.stackexchenge.com. However, I will you provide a recipe how to proceed:

You calculate the arithmetic mean of your x and y values:

x0 = Sum(x_k, k=1..n) / n
y0 = Sum(y_k, k=1..n) / n

Then you translate the coordinates:

x -> x-x0
y -> y-y0

The arithmetic mean of the new coordinates would be 0, and the optimal lines goes through (0,0), so the new r would be 0 now, and only the direction of the line must still be determined.

Then you calculate the correlation matrix

Sum(x*x)  Sum(x*y)
Sum(x*y)  Sum(y*y)

Then you calculate the eigenvectors of that matrix. It's a 2x2 matrix so you shouldn't have any problems here. Let's call the two eigenvectors v1=(x1, y1) and v2=(x2, y2). The eigenvector with the smaller eigenvalue points perpendicular to the line, the other points parallel to your line. This means you can interpret them as x1=sin(theta) and y1=cos(theta).

EDIT Finally, you have to calculate r for the original coordinates as

r=x0*x1 + y0*y1