Recursive Bayesian Filtering

Every estimator on this site is a special case of one idea: recursively maintain a belief over a hidden state given noisy measurements. This page walks the ladder from the linear-Gaussian Kalman filter up through the EKF, UKF, and finally the fully general particle filter — each relaxing an assumption of the one before, at rising computational cost.

Symbols used on this page are defined in the Nomenclature → estimation & filtering.

The Bayesian recursion

All four filters implement the same two-step recursion on the posterior $p(\mathbf x_k\mid \mathbf z_{1:k})$:

$$ \underbrace{p(\mathbf x_k\mid\mathbf z_{1:k-1}) = \!\int\! p(\mathbf x_k\mid\mathbf x_{k-1})\,p(\mathbf x_{k-1}\mid\mathbf z_{1:k-1})\,d\mathbf x_{k-1}}_{\text{predict}} $$ $$ \underbrace{p(\mathbf x_k\mid\mathbf z_{1:k}) \propto p(\mathbf z_k\mid\mathbf x_k)\,p(\mathbf x_k\mid\mathbf z_{1:k-1})}_{\text{update (Bayes)}} $$

The filters differ only in how they represent and propagate that belief:

Filter	Belief	Handles nonlinearity by	Cost
KF	Gaussian	(system is linear — exact)	lowest
EKF	Gaussian	1st-order Taylor (Jacobians)	low
UKF	Gaussian	deterministic sigma points (no Jacobians)	moderate
Particle	arbitrary (weighted samples)	Monte-Carlo sampling	highest

The Kalman filter (linear-Gaussian)

When the dynamics and measurements are linear and all noise is Gaussian, the posterior stays exactly Gaussian and the KF is the optimal (minimum-variance) estimator. Model:

$$ \mathbf x_k = F\mathbf x_{k-1} + \mathbf w,\quad \mathbf w\sim\mathcal N(0,Q);\qquad \mathbf z_k = H\mathbf x_k + \mathbf v,\quad \mathbf v\sim\mathcal N(0,R). $$

Predict $$\hat{\mathbf x}^- = F\hat{\mathbf x},\qquad P^- = FPF^\top + Q$$

Update $$K = P^-H^\top(HP^-H^\top+R)^{-1}$$ $$\hat{\mathbf x}=\hat{\mathbf x}^- + K(\mathbf z - H\hat{\mathbf x}^-),\quad P=(I-KH)P^-$$

The tracker in Perception is exactly this — a constant-velocity KF. The interactive KF-vs-noise demo lives on that page; below (in §EKF) the same predict/update machinery is shown on a nonlinear problem.

Seeing the update as three Gaussians

Everything the Kalman update does is visible in one dimension. Take a scalar state with a direct measurement ($F=H=1$), so the whole filter is three numbers and three bell curves:

$$ \underbrace{p(x_{k+1}\mid z_{1:k})=\mathcal N(\mu^-,\,P^-)}_{\text{a priori (prediction)}},\qquad \underbrace{p(z_{k+1}\mid x)=\mathcal N(x,\,R)}_{\text{measurement likelihood}},\qquad \underbrace{p(x_{k+1}\mid z_{1:k+1})=\mathcal N(\mu^+,\,P^+)}_{\text{a posteriori}} $$

The posterior is the normalized product of the other two, which for Gaussians is another Gaussian whose precision is the sum of precisions — so the posterior is always narrower than either input, and its mean is a precision-weighted average:

$$ \frac{1}{P^+}=\frac{1}{P^-}+\frac{1}{R},\qquad \mu^+=\frac{R\,\mu^- + P^-\,z}{P^-+R}=\mu^-+K\,(z-\mu^-),\qquad K=\frac{P^-}{P^-+R} $$

Read the gain as a trust ratio. $K\to1$ when $R\ll P^-$ (measurement far sharper than the prediction → jump to the measurement); $K\to0$ when $R\gg P^-$ (noisy measurement → keep the prediction). That is the whole filter.

Try this — the outlier failure. Set $\sigma_r$ small (say 0.2) and drag the measurement out to $z=10$. The green likelihood is a narrow spike far from the prediction, so $K\approx1$ and the red posterior abandons the prediction and lands on the bad measurement — confidently wrong, with a small reported variance. A single spoofed or mis-associated measurement can do this to a real filter.

Defence 1 — measurement underweighting

Rather than trusting the stated $R$, inflate the predicted innovations variance by a factor $(1+\beta)$ before forming the gain (Lear's method, recommended in the NASA best practices):

$$ W=H P^- H^\top (1+\beta)+R,\qquad K=P^-H^\top W^{-1} $$

This deliberately takes a smaller step, keeping the posterior nearer the a priori. It is the right tool when the covariance is large and the measurement model is nonlinear (so the linearized update over-corrects), and during initial convergence. Raise $\beta$ in the sim and watch $K$ — and the posterior's migration toward $z$ — shrink.

Defence 2 — residual editing (innovation gating)

Underweighting still accepts the measurement. Editing decides whether to use it at all, by testing the normalized residual against its own predicted spread:

$$ \nu=z-H\hat{\mathbf x}^-,\qquad \gamma^2=\frac{\nu^2}{HP^-H^\top+R}=\nu^\top W^{-1}\nu \;\sim\;\chi^2_{m} \qquad\text{reject if }\gamma>N $$

With $N=3$ you discard anything beyond $3\sigma$ of where the filter expected the measurement to land, so $K$ is forced to zero and the posterior equals the a priori. Two subtleties make this an engineering decision rather than a formula:

The gate scales itself. Because the threshold is on $\nu/\sigma_\nu$ and $\sigma_\nu$ grows with $P^-$, the gate automatically widens for an uncertain track and tightens for a confident one — exactly what you want, and why gating on a raw distance in metres is a mistake.
A too-tight gate is self-fulfilling. If the filter is optimistic (its $P^-$ is too small), good measurements look like outliers, get rejected, and $P^-$ is never corrected — the filter happily diverges while reporting a tiny covariance. Always log rejections: a wall of rejects means the filter is wrong, not the data.

The pairing. Editing handles bad data (spoofs, glitches, mis-associations); underweighting handles good data the linearization cannot digest yet. Production filters use both, plus a healthy $Q$ so the prediction never becomes unreasonably sharp — the sim lets you drive each failure mode on its own.

What Q actually buys you

The most common way to break a working filter is to starve it of process noise. With $Q$ too small the covariance shrinks, the gain collapses, and the filter stops listening to measurements — it becomes smug. Any unmodelled acceleration then walks the truth straight out of the reported 3σ band while the filter insists it is doing fine:

Visualizing a covariance — and bounding it

A filter's answer is a mean and a covariance, but $P$ is a matrix and requirements are usually scalars ("hold position to 5 m"). Turning one into the other is where a lot of quiet errors live. Start with what $P$ is: the quadratic form it defines has level sets that are ellipsoids,

$$ \mathcal E_c=\{\mathbf x:\ \mathbf x^\top P^{-1}\mathbf x\le c^2\},\qquad P=V\Lambda V^\top,\qquad \mathcal E_1=\sqrt P\,\{\lVert\mathbf u\rVert\le1\} $$

so the eigenvectors $V$ give the principal directions and the square-root eigenvalues $\sigma_i=\sqrt{\lambda_i}$ give the semi-axis lengths. The diagonal entries $\sigma_x,\sigma_y$ are just the shadows of the ellipse on the axes — which is precisely why treating them as a box is not a bound.

The 2-D picture

Build $P$ from two standard deviations and a correlation and watch the ellipse respond. The correlation $\rho$ does not change the shadows at all — it rotates the ellipse, moving probability mass outside the axis-aligned box while $\sigma_x,\sigma_y$ stay fixed:

$$ P=\begin{bmatrix}\sigma_r^2 & \rho\,\sigma_r\sigma_v\\ \rho\,\sigma_r\sigma_v & \sigma_v^2\end{bmatrix} $$

Which candidate "bounds" are actually valid? Order them by the quantity they bound:

Candidate	Radius	Valid bound on the 1σ ellipse?
σ_max sphere	$\sqrt{\lambda_{max}}=\lVert P\rVert_2^{1/2}$	Yes — smallest sphere containing it; the honest scalar summary
σ_min sphere	$\sqrt{\lambda_{min}}$	No — it is inscribed (a lower bound / best-case direction)
Per-axis box	$\pm\sigma_x,\pm\sigma_y$	Only if ρ = 0. With correlation the ellipse pokes out of the box corners' sides
RSS circle	$\sqrt{\sigma_x^2+\sigma_y^2}=\sqrt{\operatorname{tr}P}$	Yes — but loose, since $\operatorname{tr}P=\sum\lambda_i\ge\lambda_{max}$

The trap. Reporting $\sigma_x$ and $\sigma_y$ and calling the rectangle a "1σ box" understates the error in the correlated direction. If you need one number, use $\sqrt{\lambda_{max}}$; if you need a probability statement, scale by the $\chi^2$ quantile — in 2-D the 1σ ellipse contains only 39% of the mass (not 68%), and you need $c^2=\chi^2_{2,0.95}=5.99$, i.e. $c\approx2.45$, for 95%.

Dimension	Mass inside c = 1	c for 95%	c for 99%
1-D	68.3%	1.96	2.58
2-D	39.4%	2.45	3.03
3-D	19.9%	2.80	3.37

The 3-D picture

Three sigmas and three correlations give a general ellipsoid. The lesson is the same but sharper: the $\sigma_{max}$ sphere is the tight scalar bound, the per-axis box is valid only for a diagonal $P$, and almost 80% of the probability lies outside the 1σ ellipsoid:

$$ P=\begin{bmatrix} \sigma_x^2 & \rho_{xy}\sigma_x\sigma_y & \rho_{xz}\sigma_x\sigma_z\\ \rho_{xy}\sigma_x\sigma_y & \sigma_y^2 & \rho_{yz}\sigma_y\sigma_z\\ \rho_{xz}\sigma_x\sigma_z & \rho_{yz}\sigma_y\sigma_z & \sigma_z^2\end{bmatrix} $$

Both apps are JavaScript ports of the MATLAB App-Designer tools covariance_bounds.mlapp and covariance_bounds_3D.mlapp (originals bundled with this site); the ellipse/ellipsoid is generated the same way (√P applied to a unit circle/sphere), with the eigen-decomposition done in-browser — closed form in 2-D, Jacobi rotations in 3-D. The 1-D Kalman app above is a port of app2.mlapp, extended with the underweighting and residual-editing controls.

Why this matters for a real filter. Requirement verification, gating and consider-covariance all need a scalar from a matrix — and the right scalar depends on the question. Use $\sqrt{\lambda_{max}}$ for a worst-case direction, a projected variance $\sigma_a^2=\mathbf a^\top P\,\mathbf a$ for a specific direction or derived quantity (this is how the semi-major-axis and flight-path-angle metrics in the NASA practices are built), and a $\chi^2$-scaled ellipsoid for anything probabilistic. For attitude, the same ellipsoid lives in the tangent space of $SO(3)$ — see the covariance-on-the-sphere visualization.

Extended Kalman filter

When $f$ or $h$ is nonlinear, the EKF linearizes them about the current estimate via Jacobians $F=\partial f/\partial\mathbf x$, $H=\partial h/\partial\mathbf x$, then runs the linear KF equations on the linearized model. It is the workhorse of GNC, but a single linearization point biases the estimate when the function is strongly curved, and it can diverge with a bad initialization.

Full treatment with a nonlinear range/bearing example is on the dedicated EKF page:

Unscented Kalman filter

The UKF replaces linearization with the unscented transform: rather than approximate the function, it approximates the distribution. It picks $2n+1$ deterministic sigma points that match the mean and covariance, propagates each through the exact nonlinear map, and recovers a Gaussian from the transformed points:

$$ \mathcal X_0 = \hat{\mathbf x},\quad \mathcal X_i = \hat{\mathbf x} \pm \left(\sqrt{(n+\lambda)P}\right)_i,\qquad \hat{\mathbf y} = \sum_i W_i\, f(\mathcal X_i). $$

This captures the mean and covariance to second order for any nonlinearity (vs first order for the EKF), needs no Jacobians, and is often more accurate and robust. The sim below pushes a Gaussian through a curved map: the EKF (dashed) keeps the mean at zero, while the true cloud and UKF mean shift — the linearization bias the UKF avoids:

Particle filters

When the posterior is not Gaussian — multi-modal, heavy-tailed, or living on a weird manifold — even the UKF's single-Gaussian belief fails. A particle filter (Sequential Monte Carlo) represents the posterior by a set of weighted samples $\{\mathbf x^{(i)}, w^{(i)}\}$ and updates them:

Predict: propagate each particle through the motion model (+ process noise).
Weight: $w^{(i)} \propto p(\mathbf z_k\mid\mathbf x^{(i)})$ — the measurement likelihood.
Resample: draw a new set proportional to the weights, concentrating particles where the posterior is high (fixes weight degeneracy).

$$ p(\mathbf x_k\mid\mathbf z_{1:k}) \approx \sum_{i=1}^{N} w^{(i)}\,\delta\!\big(\mathbf x_k - \mathbf x_k^{(i)}\big). $$

It converges to the true posterior as $N\to\infty$ and handles arbitrary distributions — at $O(N)$ cost per step and with resampling/degeneracy pitfalls. Watch the cloud track the target and collapse onto the measurements; raise process noise to spread it, raise particle count for a smoother estimate:

Which filter?

Linear-Gaussian → KF (optimal, cheap).
Mildly nonlinear, unimodal → EKF (fast, standard; watch divergence).
Strongly nonlinear, still unimodal, Jacobians painful → UKF (2nd-order, derivative-free).
Multi-modal / non-Gaussian (e.g. terrain-nav ambiguity, data association) → particle filter.
State on a manifold (attitude) → a multiplicative variant that keeps the mean on the manifold and the covariance in the tangent plane — see Attitude's MEKF.

The unifying view. All four are the same predict/update Bayesian recursion; they differ only in the fidelity of the belief representation. Pay compute for fidelity only where the nonlinearity or multi-modality demands it.

Related: EKF deep dive · Attitude MEKF · IMU (the process model) · the tracker (a linear KF).