2
$\begingroup$

How do I do a least squares fit of the line equation $a x + b y = 1$, so that the points are as close to the line as possible? (Not just vertically close)

If I use the matrices

$X = \left[\begin{matrix} x_{1} & y_{1} \\ x_{2} & y_{2} \\ \vdots & \vdots \\ x_{n} & y_{n} \end{matrix}\right]$

$Y = \left[\begin{matrix} 1 \\ 1 \\ \vdots \\ 1 \end{matrix} \right] $

and calculate

$\left[\begin{matrix} a \\ b \end{matrix}\right] = {\left(X^{\text{T}} \cdot X\right)}^{-1} \cdot X^{\text{T}} \cdot Y,$

I will minimize the expression $\sum_{i} {\left(x_{i} a + y_{i} b - 1\right)}^{2}.$ This will not give the desired result. It will minimize the distance between $a x + b y$ and $1$.

What I really want to minimize is the expression $\sum_{i} {\left(\frac{x_{i} a + y_{i} b - 1}{\sqrt{a^{2}+b^{2}}}\right)}^{2}.$ That is, the distance to the line.

Is this easily achievable with matrix equations? Or is there some other approach that would make it easier?

  • 0
    (I deleted my previous comment because I had a misunderstanding)2011-03-20

1 Answers 1

4

You can write $a=\cos\phi/r$ and $b=\sin\phi/r$. Then the expression you want to minimize reduces to

$\sum_{i} \left(x_{i} \cos\phi + y_{i} \sin\phi - r\right)^2\;.$

The equation you get from differentiating with respect to $r$ is trivial; you can solve it for $r$ and substitute the result into the expression you get from differentiating with respect to $\phi$ to get a single equation involving only $\phi$ that you can solve with trigonometric functions.

P.S.: Solving the equation for $\phi$ becomes easier if you shift all your points by the center of mass. Then the equation for $r$ yields $r=0$ (which makes sense if you rewrite the line equation as $x\cos\phi + y\sin\phi = r$ to avoid the division by $r$), and the equation for $\phi$ can be written in terms of $\cos2\phi$ and $\sin2\phi$ only:

$\sum_i(x_i\cos\phi+y_i\sin\phi)(-x_i\sin\phi+y_i\cos\phi)=0\;,$ $\sum_i\left(x_iy_i\cos2\phi+\frac{y_i^2-x_i^2}{2}\sin2\phi\right)=0\;,$ $\tan2\phi=\frac{2\sum_i x_i y_i}{\sum_i(x_i^2-y_i^2)}\;.$

(Of course in the end you have to shift the line you obtain back by the center of mass.)

Another way to think about this is to note that the best-fit line has to go through the center of mass. To see this, you can rotate the coordinate system such that the line is parallel to, say, the vertical axis; then the optimal horizontal position of the line is at the average $x$ coordinate, so it passes through the center of mass. But if you know the line passes through the center of mass, then you really only have one parameter to optimize, the angle $\phi$, and the best way to find it is to transform to coordinates where the center of mass is at the origin so the line passes through the origin.

P.P.S.: Of course you get two different lines this way; one minimizes the sum of squares and the other maximizes it (subject to the condition that the line goes through the center of mass).

  • 0
    *I deleted my previous comment because I had a misunderstanding*2011-03-20