Linear Least Squares and the Pseudoinverse

Least squares picks the line that makes the total of the squared errors as small as possible. It is the workhorse of robotics, from sensor calibration to SLAM.

Polynomial degree Show the squared residuals

Drag any point.

The problem

Stack the unknown coefficients in $\mathbf{x}$ and write one row of $A$ per data point, so that $A\mathbf{x} \approx \mathbf{b}$. For a line $y = m t + c$, row $i$ is $[\,t_i \;\; 1\,]$. Least squares minimizes the sum of squared residuals:

$$\min_{\mathbf{x}}\ \lVert A\mathbf{x} - \mathbf{b}\rVert^2 \quad\Longrightarrow\quad A^\top A\,\mathbf{x} = A^\top \mathbf{b} \quad\Longrightarrow\quad \mathbf{x} = \underbrace{(A^\top A)^{-1}A^\top}_{A^{+}}\,\mathbf{b}$$

$A^{+}$ is the pseudoinverse. The middle equation is called the normal equations.

What to notice

The shaded squares are the squared errors, and the fit makes their total area as small as it can. Add an outlier and watch one huge square drag the whole line toward it. Squaring makes big errors count a lot, which is why robot systems often add outlier rejection such as RANSAC.

Raise the degree and the curve bends to pass closer to every point, but it starts to wiggle between them. That is overfitting, and it is the same trap that machine learning has to avoid.