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?

  • $\begingroup$ (I deleted my previous comment because I had a misunderstanding) $\endgroup$ – Gottfried Helms Mar 20 '11 at 22:16

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).

  • $\begingroup$ I deleted my previous comment because I had a misunderstanding $\endgroup$ – Gottfried Helms Mar 20 '11 at 22:17

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.