M5-T2 — Least-Squares Formulation

Learning objectives

After this lesson, you should be able to:

• Write a linear fitting problem as minimise ‖A x − b‖² and identify A, x and b from data.
• Define residuals and explain why their squares are summed.
• Show that the cost is a convex quadratic in x whose minimum is unique when the columns of A are independent.
• Compare squared, absolute and robust costs, including the effect of an outlier.

Introduction and motivation

Every calibration, line fit and estimator in robotics begins by choosing a cost: a single number that says how badly a candidate answer explains the data. The squared-error cost is the default because it makes the problem solvable in closed form with matrix algebra, it corresponds to the most likely answer when the noise is Gaussian, and it is smooth enough to optimise. Its main weakness, sensitivity to outliers, is the reason robust variants exist.

The intuition

Suppose you want a line through scattered points. For any candidate line, each point has a residual: the vertical gap between what the line predicts and what was measured. Some are positive, some negative; adding them would let errors cancel. Squaring makes every gap count as a positive number and punishes large gaps more than small ones. The cost is the sum of the squared gaps, and the best line is the one with the lowest cost.

Geometric and physical interpretation

Geometric view. In the space of unknowns, the cost ‖Ax − b‖² is a bowl-shaped surface (a paraboloid) whose level curves are ellipses. The least-squares solution is the bottom of the bowl. Physical view. Each residual is the discrepancy between what the model says a sensor should read and what it actually read. The cost adds up the energy of those discrepancies, in the way that the elastic energy of springs attached to the data points adds up, so the best fit is the equilibrium of the springs.

The mathematics

A

the m × n design matrix: row i describes how the unknowns predict measurement i.

x

the n unknowns (slope and intercept, plane parameters, calibration constants).

b

the m measurements.

r

the residual vector r = A x − b (prediction minus data).

The problem

minimise over x:     f(x) = ‖A x − b‖² = Σ ( ai · x − bi )²        x̂ = argmin f(x)

What it means. Choose the unknowns to minimise the sum of squared residuals. Row i of A multiplied by x is the prediction of measurement i, so f counts the squared mismatch over all measurements.

Setting up A, x and b

line y = m x + c:     A = [ x1 1 ; x2 1 ; ... ; xm 1 ],   x = (m, c),   b = (y1, ..., ym)

What it means. Each measurement is one row: [x_i, 1] times (m, c) predicts y_i. Any model that is linear in its unknown parameters gets a design matrix this way, even if it is nonlinear in the input (a polynomial, for instance).

Expanding the cost

f(x) = xᵀ (AᵀA) x − 2 bᵀA x + bᵀb

What it means. AᵀA is symmetric and positive semidefinite; it is positive definite (a bowl) exactly when the columns of A are independent. So f has a single lowest point, and the lesson on quadratic forms tells you what its level curves look like.

Least squares: x̂ minimises the sum of squared residuals ‖Ax − b‖². The cost is a bowl with a single minimum when the columns of A are independent.

Step-by-step derivation: the cost is a bowl, and the average as the one-unknown case

Expanding the cost. Using ‖v‖² = vᵀv:

1. f(x) = (Ax − b)ᵀ(Ax − b).
2. Expand with (Ax − b)ᵀ = xᵀAᵀ − bᵀ: f = xᵀAᵀAx − xᵀAᵀb − bᵀAx + bᵀb.
3. The two middle terms are scalars and are transposes of each other, so they are equal: f = xᵀ(AᵀA)x − 2bᵀAx + bᵀb.

The bowl. For any non-zero x, xᵀ(AᵀA)x = (Ax)ᵀ(Ax) = ‖Ax‖² ≥ 0, so AᵀA is positive semidefinite. It is positive definite exactly when Ax = 0 forces x = 0, i.e. when the columns of A are independent. Then f is a strictly convex quadratic, and a strictly convex quadratic has exactly one stationary point, which is its global minimum.

Why squares. Three reasons: (1) calculus: squares are smooth, so setting the derivative to zero gives linear equations (the normal equations), solvable in one step; (2) geometry: sums of squares are squared lengths, so the best fit is an orthogonal projection (next lesson); (3) statistics: if the measurement errors are independent Gaussian with equal variance, the x that maximises the likelihood of the data is exactly the minimiser of the sum of squares.

The price. Squaring magnifies large errors. For readings 9.8, 10.1, 10.3 and an outlier 15.0 the mean (the least-squares answer) is 11.3 m, dragged 1.1 m away from the three consistent readings, while the median, which minimises the sum of absolute errors, stays at 10.2 m. This is why robust costs (Huber, absolute value) exist, and why outlier rejection precedes a least-squares fit in practice.

A worked example: setting up and evaluating the cost

One unknown. For the readings 9.8, 10.1, 10.3, A = [1, 1, 1]ᵀ. At the candidate x = 10 the residuals are (−0.2, 0.1, 0.3) and f = 0.04 + 0.01 + 0.09 = 0.14. At the mean x = 10.0667, the residuals are (−0.2667, 0.0333, 0.2333) and f = 0.1267, smaller, as it must be.

A line. The points (1, 1), (2, 2), (3, 2) give A = [[1, 1], [2, 1], [3, 1]] and b = (1, 2, 2). For the line y = x (m = 1, c = 0) the residuals are (0, 0, 1) and f = 1. For y = 0.5x + 0.667 the residuals are (0.167, −0.333, 0.167) (prediction minus data) and f = 0.0278 + 0.1111 + 0.0278 = 0.1667: the better line has the lower cost.

The quadratic form. AᵀA = [[14, 6], [6, 3]] has determinant 14·3 − 36 = 6 > 0 and trace 17: positive definite, so the cost is a bowl in (m, c).

An outlier. Adding the reading 15.0 moves the mean to (9.8 + 10.1 + 10.3 + 15.0)/4 = 11.3, a shift of 1.23 m from the earlier answer of 10.07 m.

Robotics application

Calibration as a fit. A range sensor with scale error and offset follows z = s d + o; measuring true distances 1 to 5 m gives z = 1.12, 2.05, 3.10, 4.18, 5.10 m. The least-squares fit gives s = 1.009 and o = 0.083 m, with residuals of a few centimetres: the sensor reads about 0.9% long with an 8 cm offset.

Plane and line fitting. Fitting the ground plane to a LiDAR scan minimises the sum of squared point-to-plane distances (Module 6 uses the SVD for the best version of this). The SLAM track's ICP lesson minimises the sum of squared point-to-point distances in the same spirit.

Odometry and filtering. A Kalman filter update minimises a weighted sum of squared prediction and measurement errors; Module 9 shows this equivalence.

Dealing with outliers. Perception pipelines remove outliers (RANSAC) before the least-squares step, or replace the square by a robust loss; see robust optimisation.

Engineering implications and limitations

Practical rules

• Look at the residuals, not only the answer. A least-squares fit always returns something. Plot or summarise the residuals: they should look like noise (no trend), and be about as large as the sensor noise.
• Remove gross outliers first. One bad measurement can dominate the squared cost. Use a consensus method or a robust loss when outliers are possible.
• Choose units and scaling deliberately. The cost adds squares of residuals; mixing metres and radians in one residual vector makes the fit favour whichever has larger numbers. Scale each residual by its expected noise (weighted least squares, later).
• Check the rank. If the columns of A are dependent, the bowl has a flat valley and the answer is not unique. Check the smallest singular value, not only the rank.
• Fit the model your data supports. More parameters always lower the cost on the training data; a lower cost with more parameters can still be a worse model. Compare on separate data.

Limits

Squared error is optimal under independent Gaussian noise of equal size. Heavy-tailed noise, outliers, noise that grows with distance, and errors in the inputs as well as the outputs all violate that assumption, and each has its own remedy (robust loss, weights, total least squares).

Common misconceptions

Engineering takeaways

1. Least squares chooses x to minimise the sum of squared residuals f(x) = ‖Ax − b‖².
2. The design matrix A has one row per measurement; for a line each row is [x_i, 1].
3. f(x) = xᵀAᵀAx − 2bᵀAx + bᵀb is a convex bowl; it has a unique minimum when the columns of A are independent.
4. Squares are used because they are smooth, geometric (projection) and optimal for Gaussian noise; they are sensitive to outliers.
5. Always inspect the residuals: they measure the quality of the fit and expose outliers and model errors.

References and further reading

Primary papers and authoritative documentation.

• Boyd and Vandenberghe, Introduction to Applied Linear Algebra (VMLS): the chapters on least squares; the site did not load when we last checked
• MIT 18.06SC Linear Algebra (OCW): lecture on least squares approximations
• UCSD ECE276A: Sensing and Estimation in Robotics: maximum likelihood estimation with Gaussian noise equals least squares
• Mathematics for Machine Learning: the chapter on linear regression

Knowledge check

Three conceptual questions. Write an answer, then reveal the explanation. Your answers stay in your browser.

What’s next

Next you will see that the least-squares answer has a beautiful geometric meaning: it is the projection of the data onto the set of predictions the model can make, and the residual is perpendicular to that set.

Related content

Nothing below is required to finish this lesson.

• Before
  M5-T1: Overdetermined and Underdetermined Systems

  Tell apart systems with more equations than unknowns and with fewer, and say what a sensible answer means in each case.

• Lab
  M5-L1: LiDAR Plane Fitting

  Fit the ground plane to a noisy LiDAR scan, find out why a naive fit fails on a wall, and fix it with a stable method.