M9-T5 — Mahalanobis Distance

Learning objectives

After this lesson, you should be able to:

• Define the squared Mahalanobis distance d² = vᵀΣ⁻¹v and compute it for 2D examples.
• Explain how it differs from Euclidean distance and why it equals Euclidean distance after whitening.
• Gate measurements with chi-square thresholds and choose the correct degrees of freedom.
• Use it for data association between measurements and landmarks, and recognise its failure modes.

Introduction and motivation

A LiDAR feature is 0.45 m from the predicted position of landmark 7 and 0.35 m from landmark 8. Which one is it? If the prediction is uncertain along the line of sight and very sure across it, the nearer one may be much less likely. Mapping systems that choose by Euclidean distance mismatch features, corrupt the map and fail at loop closure. Using Mahalanobis distance (the innovation gate of every Kalman filter) is the standard fix.

The intuition

Euclidean distance measures how far away something is in metres. Mahalanobis distance measures how far away it is in standard deviations of the uncertainty in that direction. A point 2 m away along the long axis of a long cloud is unremarkable; the same 2 m along the short axis is shocking. Equivalently, squash the cloud into a round one (whitening, next lesson) and use ordinary distance.

Geometric and physical interpretation

Geometric view. The set of points at Mahalanobis distance k from μ is the ellipse (x − μ)ᵀΣ⁻¹(x − μ) = k² with axes along the eigenvectors of Σ and semi-axes k√λᵢ. Points on the same ellipse are equally likely under the Gaussian. Physical view. For a robot with an elongated position ellipse, a landmark observed 1 m off along the corridor is entirely plausible, whereas one 1 m off across it signals a wrong match, a moved landmark or an over-confident filter.

The mathematics

v = x − μ

the deviation from the mean (for a filter, the innovation v = z − ẑ).

Σ (or S)

the covariance of v (for innovations, S = HP⁻Hᵀ + R).

d² = vᵀΣ⁻¹v

the squared Mahalanobis distance; d is the distance.

γ

the gate: a chi-square quantile for the dimension of v.

Definition

d²(x) = (x − μ)ᵀ Σ⁻¹ (x − μ)        d = √(d²)

What it means. The deviation weighted by the inverse covariance. Large covariance in a direction means large deviations are cheap there; small covariance makes them expensive. For Σ = σ²I it reduces to the Euclidean distance divided by σ.

Gating

accept if d² ≤ γ,   γ = χ²ₘ,α   (m = dim v):   m = 1: 3.84,  2: 5.99,  3: 7.81  at 95 %;   2: 9.21 at 99 %

What it means. For a Gaussian innovation, d² follows a chi-square distribution with m degrees of freedom, so thresholds come from its quantiles. Using the wrong dimension gives a gate that is too tight or too loose.

Relation to whitening

d² = ‖ L⁻¹ (x − μ) ‖²   with Σ = L Lᵀ

What it means. Solve a triangular system with the Cholesky factor, then take the ordinary squared norm. This is how d² is computed in practice; Σ is never inverted explicitly.

d² = vᵀΣ⁻¹v counts deviations in standard deviations along the right directions. Gate with chi-square quantiles of the correct degrees of freedom (2D 95 %: 5.99). Compute it with a Cholesky solve.

Step-by-step derivation: whitening, the chi-square law and the Euclidean failure

1. Cholesky form. Write Σ = LLᵀ. Then Σ⁻¹ = L⁻ᵀL⁻¹ and vᵀΣ⁻¹v = (L⁻¹v)ᵀ(L⁻¹v) = ‖L⁻¹v‖². The vector w = L⁻¹v is the whitened deviation.
2. Whitened components are unit-variance and uncorrelated. Cov(w) = L⁻¹ΣL⁻ᵀ = L⁻¹LLᵀL⁻ᵀ = I. Each component of w is a standard normal if v is Gaussian.
3. Chi-square law. d² = Σᵢ wᵢ² is a sum of m squared independent standard normals, hence chi-square with m degrees of freedom: mean m, and the quantiles tabulated above (2D: 5.99 at 95 %).
4. Why Euclidean fails. The Euclidean squared distance is vᵀv = Σ λᵢ wᵢ² in the eigenbasis: it weights the whitened components by the variances, so deviations along high-variance directions look big and are exaggerated, while deviations along low-variance (precise) directions look small and are underweighted: precisely the opposite of how surprising they are.
5. Gating the innovation. A Kalman filter computes the innovation v = z − ẑ with covariance S = HP⁻Hᵀ + R. If the filter is consistent, vᵀS⁻¹v ~ χ²ₘ; values above the gate indicate an outlier or a wrong association.
6. Data association. For a measurement z and candidate landmarks j with predictions ẑⱼ and covariances Sⱼ, choose the j with the smallest d²ⱼ among those inside the gate (nearest neighbour). Compare via the full log-likelihood d² + ln det S to avoid favouring landmarks with large S.
7. Consistency check (NIS). The average of d² over time should be near m. A value much larger means the filter is over-confident; much smaller, too pessimistic. This normalised innovation squared (NIS) test is a standard tuning tool.

The likelihood link. The Gaussian density depends on x only through d², so ranking by smallest d² (with equal covariances) is ranking by largest likelihood. With different covariances the determinant term must be included.

Not a metric on the world. Mahalanobis distance depends on Σ: change the covariance and the same two points are at a different distance. It measures plausibility, not geometry.

A worked example: a correlated cloud and a data association

• Diagonal covariance. Σ = diag(4, 0.25). The point (2, 0) has d² = 4/4 + 0 = 1, so d = 1; the point (0, 1) has d² = 0 + 1/0.25 = 4, so d = 2. Euclidean distances are 2 and 1: the ordering is reversed.
• Correlated covariance. Σ = [[1, 0.8], [0.8, 1]], Σ⁻¹ = (1/0.36)[[1, −0.8], [−0.8, 1]]. For (1, 1) (along the correlation): d² = (1 − 1.6 + 1)/0.36 = 1.11. For (1, −1) (against it): d² = (1 + 1.6 + 1)/0.36 = 10.0. Both are at Euclidean distance √2, but the second exceeds the 95 % gate of 5.99 and is an outlier.
• Data association. Predicted measurement ẑ = (5.0, 2.0), innovation covariance S = [[0.25, 0.05], [0.05, 0.09]], S⁻¹ = [[4.5, −2.5], [−2.5, 12.5]]. Candidate A at (5.00, 2.35): Euclidean 0.35, d² = 0.35²·12.5 = 1.53. Candidate B at (5.45, 2.00): Euclidean 0.45, d² = 0.45²·4.5 = 0.91.
• Decision. Euclidean distance picks A; Mahalanobis picks B (0.91 < 1.53) because the prediction is much more precise in y (σ_y = 0.3) than in x (σ_x = 0.5). Both are inside the 95 % gate of 5.99, so the decision is by smallest d².
• Cholesky evaluation. For B, L = [[0.5, 0], [0.1, 0.283]], solving L w = (0.45, 0) gives w = (0.9, −0.318) and ‖w‖² = 0.81 + 0.101 = 0.911 ✓ the same value without forming S⁻¹.
• NIS. A 2D filter whose innovations average d² = 9 over 100 steps (the expected value is 2) is badly over-confident: its covariance is about 4.5 times too small.

Robotics application

SLAM data association. Landmark and loop-closure matching use Mahalanobis gating, often with joint compatibility tests; see landmark-based mapping, EKF-SLAM and feature extraction.

UAV fault detection. Sensor-fault detectors monitor the normalised innovation squared against chi-square limits to flag GNSS jumps or IMU faults; see fault detection, isolation and recovery and the error-state Kalman filter.

LiDAR registration. Robust ICP variants reject correspondences with large residuals in units of their covariance; see robust optimisation and ICP fundamentals.

Mobile robots and navigation. Obstacle tracking gates detections against predicted tracks; see frames, poses and footprints for the planning side that consumes those tracks.

Engineering implications and limitations

Practical rules

• Pick the gate from the dimension. 2D position innovations use 5.99 (95 %) or 9.21 (99 %); 3D use 7.81 or 11.34; do not use “3σ = 9”, which belongs to a different dimension and confidence.
• Compute with a triangular solve. Factor S = LLᵀ once and solve; never form S⁻¹ explicitly, and test positive definiteness at the same time.
• Include the determinant when comparing hypotheses. Use d² + ln det S so that a landmark with a very large S does not win trivially.
• Monitor NIS online. Average d² over a window should approach the dimension m; use it to tune Q and R.
• Gate in the right frame and units. Mixed angle and distance residuals need wrapped angles and consistent units inside v.
• Beware over-confidence. A filter with too-small covariance rejects good measurements (every d² looks big) and spirals into divergence; inflate noise or use a robust loss.

Limits

The chi-square gate presumes a Gaussian innovation; heavy-tailed noise and nonlinear measurements break it. Mahalanobis gating alone cannot resolve ambiguous scenes (repeated structure); use joint compatibility, appearance or multi-hypothesis tracking.

Common misconceptions

Engineering takeaways

1. d² = (x − μ)ᵀΣ⁻¹(x − μ) measures deviation in standard deviations along the proper directions; it reduces to ‖x − μ‖²/σ² for Σ = σ²I.
2. For a Gaussian, d² ~ χ²ₘ; 2D gates are 5.99 (95 %) and 9.21 (99 %), 3D 7.81 (95 %).
3. d² = ‖L⁻¹v‖² with Σ = LLᵀ: it is the Euclidean distance after whitening; compute with a triangular solve.
4. Data association picks the smallest d² (with ln det S) inside the gate, and the average NIS of a consistent filter equals the measurement dimension.
5. Euclidean distance can rank candidates in the wrong order when the covariance is anisotropic.

References and further reading

Primary papers and authoritative documentation.

• Barfoot, State Estimation for Robotics (author-hosted first edition, free to read): chapter 4, the Mahalanobis distance and consistency of the estimator
• UCSD ECE276A: Sensing and Estimation in Robotics: data association and innovation gating
• Mathematics for Machine Learning: chapter 6, Gaussian distributions: the quadratic form
• Boyd and Vandenberghe, Introduction to Applied Linear Algebra (VMLS): norms and the weighted least-squares view of distance; the site did not load when we last checked

Knowledge check

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

What’s next

We have seen that dividing by L, the Cholesky factor, turns a correlated cloud into a round unit one. That operation, whitening, deserves its own lesson, because it is how weighted least squares, pose-graph optimisation and many filters are implemented.

Related content

Nothing below is required to finish this lesson.

• Before
  M9-T4: Covariance Propagation

  Propagate uncertainty through a linear map and through a linearised nonlinear function.

• Lab
  M9-L1: Robot Localization with Uncertainty

  Localise a robot with range measurements: update a position estimate and its covariance, and find why an overconfident filter fails.