Line fitting: vertical vs total least squares, interactive demo

Least squares

Least squares picks the model that minimizes the sum of squared differences between the data and the model. The objective is clearly specified and the optimum has a closed form, which makes it the standard first tool for fitting. It has two weaknesses: it is sensitive to outliers, because a squared error lets one bad point dominate, and it can only return a single fit even when the data contain several lines.

Vertical least squares

Given points $(x_i, y_i)$ , find $m$ and $b$ of the line $y = mx + b$ that minimize the squared vertical distances:

E = \sum_{i=1}^{n} \big(y_i - (m x_i + b)\big)^2 = \left\| \begin{bmatrix} x_1 & 1 \\ \vdots & \vdots \\ x_n & 1 \end{bmatrix} \begin{bmatrix} m \\ b \end{bmatrix} - \begin{bmatrix} y_1 \\ \vdots \\ y_n \end{bmatrix} \right\|^2 = \|Ap - y\|^2

Setting the derivative to zero gives the normal equations and their closed-form solution:

A^\top A\, p = A^\top y \;\Rightarrow\; p = (A^\top A)^{-1} A^\top y

It is cheap and exact, but it measures errors along $y$ only. The result depends on how the points lie in the coordinate frame: it is not rotation-invariant. And it fails completely for a vertical line: $m \to \infty$ , and with all $x_i$ equal, $A^\top A$ is singular.

Total least squares

Write the line as $ax + by + c = 0$ with $a^2 + b^2 = 1$ . Then $|a x_i + b y_i + c|$ is the perpendicular distance of a point to the line, and total least squares minimizes

E = \sum_{i=1}^{n} (a x_i + b y_i + c)^2

The optimal line passes through the centroid $(\bar x, \bar y)$ , so $c = -a\bar x - b\bar y$ . Substituting it leaves only the normal $p = (a, b)$ :

E = \sum_{i=1}^{n} \big(a (x_i - \bar x) + b (y_i - \bar y)\big)^2 = \left\| \begin{bmatrix} x_1 - \bar x & y_1 - \bar y \\ \vdots & \vdots \\ x_n - \bar x & y_n - \bar y \end{bmatrix} \begin{bmatrix} a \\ b \end{bmatrix} \right\|^2 = \|Ap\|^2 = p^\top A^\top A\, p

Minimizing $p^\top A^\top A\, p$ subject to $p^\top p = 1$ gives the eigenvector of the smallest eigenvalue $\lambda_2$ of the 2 × 2 matrix $A^\top A$ , which is the same as the right singular vector of the smallest singular value of $A$ (see the SVD). The minimal error is $E = \lambda_2$ . The other eigenvector, of $\lambda_1$ , points along the line. Nothing here prefers the $x$ or $y$ axis, so rotating the points rotates the fitted line with them, and vertical lines are no special case.

Recap: two common optimization problems

Minimize $\|Ax - b\|^2$ , the least-squares solution of $Ax = b$ : $x = (A^\top A)^{-1} A^\top b$ , in MATLAB x = A \ b.
Minimize $x^\top A^\top A\, x$ subject to $x^\top x = 1$ , the non-trivial least-squares solution of $Ax = 0$ : the eigenvector of $A^\top A$ with the smallest eigenvalue.

Both come back when estimating a homography and when calibrating a camera, where they are called Method 1 and Method 2.

Try this

With the noisy line, compare the dashed residuals: the orange ones are vertical, the teal ones meet the line at a right angle. The two lines are almost the same here.
Choose Steep line: the vertical residuals get long, and the orange line comes out flatter than the points (about 75° instead of 78°), while the teal one follows them.
Choose Vertical line: vertical least squares returns a line tilted by only about 19°, far from the points. Set the noise to 0: all $x_i$ are equal, $A^\top A$ is singular and there is no solution at all, while total least squares finds $x = 1.5$ .
Go back to the noisy line and drag rotate: the teal line turns with the points and its $E$ stays exactly the same. The orange $E$ grows, and around 60° to 65° the orange line breaks away from the points.
Choose One outlier: its bar dwarfs the others and both lines tilt towards it. A point three times as far away counts nine times as much.
Choose Two clusters: the points would be better described by two short lines, but least squares only returns one, running between the clusters.
Delete points until only two are left: both fits pass through them exactly and $E = 0$ .