M5-T7 — Regularized Least Squares

Learning objectives

After this lesson, you should be able to:

• Define ridge (Tikhonov) regularisation: minimise ‖Ax − b‖² + λ‖x‖² and derive (AᵀA + λI) x = Aᵀb.
• Show that AᵀA + λI is always invertible for λ > 0 and describe the limits λ → 0 and λ → ∞.
• Explain the bias-stability trade-off with a concrete example.
• Recognise Levenberg-Marquardt damping and damped least-squares inverse kinematics as regularisation.

Introduction and motivation

Sometimes the data nearly fail to determine the unknowns. Two calibration parameters whose effects are almost identical, or a manipulator at a nearly singular pose: the exact answer exists but changes wildly with tiny changes in the data. Insisting on it means amplifying noise into huge, meaningless parameters. A principled alternative is to ask for a slightly different problem: fit the data well and keep the answer modest. That is regularisation, and it is how robot software survives ill-conditioned problems.

The intuition

Add a second term to the cost: ‖Ax − b‖² + λ‖x‖². The first term wants a good fit; the second wants small unknowns. The number λ says how much you care about the second. For λ = 0 you recover ordinary least squares. As λ grows, the answer shrinks toward zero.

Geometric and physical interpretation

Geometric view. The ordinary cost is a bowl; in an ill-conditioned problem it is a long, nearly flat valley whose bottom is hard to locate (a tiny tilt moves the lowest point a long way). Adding λ‖x‖² adds a round bowl centred at the origin, which makes the valley curved in every direction and pins the minimum. Physical view. A penalty on the size of the parameters is a prior belief that they are modest: a spring pulling each parameter toward zero. The data must pull harder than the spring to move a parameter, so parameters the data barely inform stay near zero instead of drifting to absurd values.

The mathematics

λ

the regularisation parameter (λ ≥ 0).

x̂_λ

the regularised solution.

σ_i

singular values of A (Module 6).

The regularised problem

minimise  ‖A x − b‖² + λ ‖x‖²        ⇒        ( AᵀA + λ I ) x̂λ = Aᵀ b

What it means. The penalty adds λ to every diagonal entry of AᵀA. The matrix AᵀA + λI is always positive definite for λ > 0, so a unique answer exists even when the columns of A are dependent.

The limits

λ → 0:  x̂λ → the least-squares (minimum-norm) solution          λ → ∞:  x̂λ → 0

What it means. Small λ trusts the data; large λ trusts the prior preference for small x. The useful range is in between, chosen from the noise level.

Stability and bias

in the SVD basis:   component i of x̂λ = ( σi / (σi² + λ) ) · (ui · b)          instead of   (1/σi)(ui · b)

What it means. For large singular values the factor is nearly 1/σ (the data are trusted); for tiny ones it is about σ/λ, which is small, so noise in poorly determined directions is suppressed instead of amplified by 1/σ.

Regularisation: minimise ‖Ax − b‖² + λ‖x‖², solve (AᵀA + λI)x = Aᵀb. Always solvable, stable, at the price of a bias that grows with λ.

Step-by-step derivation: the regularised normal equations and the filter factors

The equations. The cost is f(x) = ‖Ax − b‖² + λ‖x‖² = xᵀ(AᵀA + λI)x − 2bᵀAx + bᵀb.

1. Gradient: ∇f = 2(AᵀA + λI)x − 2Aᵀb.
2. Set to zero: (AᵀA + λI)x̂ = Aᵀb.
3. Invertibility. For any x ≠ 0, xᵀ(AᵀA + λI)x = ‖Ax‖² + λ‖x‖² ≥ λ‖x‖² > 0. So the matrix is positive definite, hence invertible, for every λ > 0 even when A is rank-deficient.

A stacked view. Regularised least squares is ordinary least squares on the augmented system [A; √λ I] x ≈ [b; 0]: extra rows saying “x should be about zero”. This is how it is implemented with QR (no need to form AᵀA).

The filter factors. Use the SVD A = UΣVᵀ (Module 6). Then AᵀA + λI = V(Σ² + λI)Vᵀ and Aᵀb = VΣUᵀb, so x̂λ = V(Σ² + λI)⁻¹ΣUᵀb, whose i-th component along vi is σi/(σi² + λ) · (ui·b). Ordinary least squares has 1/σi instead. Where σi ≫ √λ they agree; where σi ≪ √λ the regularised factor ≈ σi/λ is tiny, whereas 1/σi would be huge.

The cost: bias. The regularised answer is not the data-optimal one; it is pulled toward zero by an amount that grows with λ. In the example below, the penalty moves the noise-free answer from (1, 1) to (0.998, 0.998): a small, known bias in exchange for removing a 1000-fold amplification of noise.

A worked example: an ill-conditioned pair of parameters

Let A = [[1, 1], [1, 1.001]], whose columns are nearly parallel (κ = 4002). The noise-free data b = (2, 2.001) correspond to x = (1, 1).

1. Exact solve with a tiny data change. With b′ = (2, 2.002) (a change of 0.001 in one entry) the equations x₁ + x₂ = 2, x₁ + 1.001x₂ = 2.002 give 0.001x₂ = 0.002, so x = (0, 2): the answer moved by 1 for a data change of 0.001, an amplification of about 1000. With b″ = (2, 2.003) it becomes (−1, 3).
2. Ridge with λ = 0.01. Solve (AᵀA + 0.01 I)x = Aᵀb′: x = (0.997, 0.998) for the noisy b′, and (0.998, 0.998) for the clean b. The noise barely matters.
3. Price. For the clean data the ridge answer is (0.998, 0.998) rather than (1, 1): a bias of about 0.002.
4. A line fit. On the points (1, 1), (2, 2), (3, 2), penalising only the slope with λ = 0, 1, 10 gives slopes 0.5, 0.333, 0.083 and intercepts 0.667, 1.0, 1.5: the line flattens as the penalty grows.

Robotics application

Damped inverse kinematics. Near a singular pose the Jacobian J has a tiny singular value, and its (pseudo)inverse gives enormous joint speeds. The damped least-squares inverse Jᵀ(JJᵀ + λ²I)⁻¹ is exactly ridge regularisation, bounding the speeds at the cost of a small tracking error; Module 8 develops it (see the Buss survey in the reference list there).

Levenberg-Marquardt. The workhorse of nonlinear least squares in SLAM and calibration adds λI (or λ diag(JᵀJ)) to the Gauss-Newton equations: with large λ it takes cautious gradient-like steps, with small λ near-Gauss-Newton steps. The nonlinear least squares lesson describes the trust-region behaviour.

Calibration with redundant parameters. When two calibration constants have nearly identical effects on the data, ridge keeps them from taking huge opposite values that merely cancel.

Priors in estimation. A penalty is a Gaussian prior with variance σ²/λ on each parameter: a Kalman filter's initial covariance plays the same role, a link to Module 9.

Engineering implications and limitations

Practical rules

• Choose λ from the noise, not by hand-waving. A rule of thumb is λ comparable to σ_noise² relative to the data scale; cross-validation or the discrepancy principle (choose λ so the residual matches the noise level) are standard.
• Standardise the unknowns first. A single λ penalises all unknowns equally; parameters in different units (metres vs radians) need scaling, or a diagonal penalty matrix.
• Do not penalise what you want to be large. Do not regularise the intercept or a parameter that should be non-zero; use a penalty matrix that omits it.
• Implement with the stacked system and QR instead of forming AᵀA + λI, to retain accuracy.
• Report the bias. A regularised result should come with the λ used; comparing fits across different λ values is not comparing like with like.

Limits

Regularisation hides, rather than repairs, a lack of information. If the data truly do not determine a parameter, the regularised answer just returns the prior (near zero). It is the right tool when you know that, and the wrong one if you hoped it would create information.

Common misconceptions

Engineering takeaways

1. Ridge regularisation minimises ‖Ax − b‖² + λ‖x‖² and solves (AᵀA + λI)x = Aᵀb.
2. AᵀA + λI is positive definite for λ > 0, so a unique, stable answer exists even for dependent columns.
3. In the SVD basis the factor 1/σ_i becomes σ_i/(σ_i² + λ): poorly determined directions are damped, not amplified.
4. The price is a bias toward zero that grows with λ; choose λ from the noise level.
5. Levenberg-Marquardt damping and damped least-squares inverse kinematics are regularisation.

References and further reading

Primary papers and authoritative documentation.

• Boyd and Vandenberghe, Introduction to Applied Linear Algebra (VMLS): the chapter on regularised data fitting; the site did not load when we last checked
• Mathematics for Machine Learning: the chapter on linear regression: maximum a posteriori and regularisation
• Buss, Introduction to Inverse Kinematics with Jacobian Transpose, Pseudoinverse and Damped Least Squares: damped least squares for inverse kinematics near singularities; the site did not load when we last checked
• MIT 18.06SC Linear Algebra (OCW): lectures on the SVD and least squares

Knowledge check

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

What’s next

The last lesson of the module gathers the numerical lessons into a single idea, the condition number, which predicts how much a problem magnifies errors, and separates a bad problem from a bad algorithm.

Related content

Nothing below is required to finish this lesson.

• Before
  M5-T6: Weighted Least Squares

  Weight measurements by their reliability and connect the weights to sensor covariances.