An interactive note · Multi-target tracking · Data association

One association problem, two philosophies.

Every scan, a tracker faces the same combinatorial question: which measurement belongs to which target? Exact marginalization requires a sum over valid global association events and is generally combinatorial. This page puts two important routes side by side on one live scenario: belief propagation, an inference algorithm that approximates association marginals using messages instead of enumerating events; and the Poisson multi-Bernoulli mixture, a posterior family whose detected-target part retains a weighted mixture of compatible global hypotheses. The numerical figures recompute when you drag Fig. 1; the across-scan diagram is schematic.

BP is an algorithm; PMBM is a posterior family. They are not mutually exclusive alternatives. Here the numerical comparison is association BP versus exhaustive summation of the same one-scan assignment posterior, with a separate explanation of how that posterior occurs inside PMBM. The benchmark has three certainly existing point targets, constant detection probability, positive Poisson clutter intensity, and no undetected-target PPP. It is not a complete PMBM filter or an empirical comparison of tracking accuracy over time. See §3 for uncertain existence, newly detected targets, and the correct PMBM weights.

§1The shared problem: three tracks in a tangle, four measurements

Three targets have predicted positions ẑ_i with innovation covariances S_i (gates drawn at the 99 % χ² contour) — and their gates overlap three ways. A sensor returns four measurements with detection probability P_D and Poisson clutter intensity λ_c. BP and exhaustive enumeration consume exactly the same existing-track assignment weights ℓ, so exhaustive enumeration is an exact reference for this benchmark; BP remains approximate on a loopy graph.

Scenario — the three-way tangle

Sensor model

Detection probability 0.90

Clutter density λ_c 5.0×10⁻⁵

Restrict pairs to the 99% gate

Drag the × marks and the track centers. Everything on this page follows.

Fig. 1 — The scan to be explained: three gates knotted around z₁–z₃, with z₄ initially outside every gate. Dashed ellipses are validation gates (99 % χ², 2 dof); thin gray links mark the gated target–measurement pairs, i.e. the pairs retained when gating is enabled. The gate is a likelihood truncation approximation, not a probability that an association is correct.

ℓ_ij = P_D·N(z_j; ẑ_i, S_i)/λ_c for gated pairs · ℓ_i∅ = 1−P_D (missed detection) · an unassigned measurement carries normalized baseline weight 1. No target-birth model is used in this benchmark.

Fig. 2 — Existing-track association weights for the normalized benchmark. BP runs messages over this table; exhaustive enumeration multiplies its entries into global assignment weights. A dot means the pair fell outside the gate.

§2Route one — belief propagation on the association graph

Introduce a target-oriented variable a_i (which measurement did target i generate, or ∅) and a measurement-oriented variable b_j (which target generated measurement j, or unassigned to an existing track). Redundant on purpose: the pairwise factors Ψ_ij(a_i,b_j) only enforce that the two bookkeepings agree. For this specific Williams–Lau association construction, finite nonnegative weights and strictly positive missed/unassigned weights give a convergence guarantee. The guarantee is not a theorem about arbitrary loopy BP. Our dense implementation costs O(n·m) per sweep and O(T·n·m) for T sweeps. Its fixed point gives approximate marginal probabilities without listing global assignments. Convergence and accuracy are different questions [1].

μ_i→j track→measurement · ν_j→i measurement→track · gated out: ℓ = 0 ⇒ μ ≡ 0

hover any edge for its ℓ, μ, ν and the marginal it feeds

q(a_i = ·) — BP beliefs; they move only when a ν half-step lands

Convergence diagnostic — max |log ν(new) − log ν(old)| per sweep

q(b_j = ·) — measurement beliefs update after μ; ∅ means unassigned (clutter in this benchmark). Track and measurement beliefs agree on each edge only at a fixed point.

Single-track state beliefs b(x_i) — Gaussian mixtures, one Kalman-updated component per gated measurement plus the prior for ∅, weighted by the live marginals above (each ellipse is a component’s 95% contour, not a 95% contour of the whole mixture; opacity ∝ weight; prior P_i = S_i − R with R = 60·I)

μ_i→j = ℓ_ijℓ_i∅ + Σ_k≠j ℓ_ik ν_k→i(1) target i tells measurement j how claimed it already is elsewhere

ν_j→i = 11 + Σ_l≠i μ_l→j(2) measurement j tells target i how contested it is

q(a_i=j) ∝ ℓ_ij ν_j→i, q(a_i=∅) ∝ ℓ_i∅(3) read the marginals off the fixed point

q(b_j=i) = μ_i→j / (1 + Σ_l μ_l→j), q(b_j=∅) = 1 / (1 + Σ_l μ_l→j)(3b) measurement-side normalization

Here q denotes a BP belief; p denotes an exact probability when the distinction matters. The consistency factor is Ψ_ij = 1{(a_i=j) ⇔ (b_j=i)}. Thus p(a,b|Z) ∝ ∏_iℓ_i,aᵢ ∏_ijΨ_ij. The scalar messages are ratios, not probabilities: μ may exceed one.

t = 0 is the uncoupled start: ν ≡ 1, so each track just normalizes its own row of Fig. 2. One time step is one application of (1) followed by (2) — exactly the two half-steps of the player above. The iterations exist purely to negotiate the one-to-one constraint.

Fig. 3 — Left: the complete bipartite Williams–Lau factor graph — every (aᵢ, bⱼ) pair carries a consistency factor Ψ (mid-edge diamond); faint dashed edges are gated out (ℓᵢⱼ = 0, so μ ≡ 0 and the pair is inert). Every live edge wears its two current messages: μᵢ→ⱼ in the track’s color, νⱼ→ᵢ in slate — the bold set is the one that just updated. One time step = two presses of Half-step ▸: first all μ fire left→right, then all ν answer right→left, measurement beliefs update after μ; track beliefs, edge thicknesses, and Δ update after ν. Hover any edge for its numbers.

§3Route two — PMBM: keep the hypotheses, prune the tail

Under independent point-target detections, Poisson clutter, independent survival/motion, and Poisson birth, the PMBM family is conjugate: a Poisson process represents never-detected targets and a multi-Bernoulli mixture represents detected ones. Each global hypothesis selects mutually compatible local histories. Bernoulli components are conditionally independent within that hypothesis, but the mixture generally couples them. “Detected” includes potentially existing targets, not only certain objects [4]. The table below visualizes that hypothesis bookkeeping for the page’s normalized assignment model; a full PMBM update additionally computes a measurement-specific Bernoulli existence and state density from the undetected-target Poisson intensity.

f(X) = Σ_{X^u ⊎ X^d = X} f^ppp(X^u) Σ_h w_h f^MB_h(X^d)(4a) undetected Poisson ⊎ multi-Bernoulli mixture

f^MB_h(X^d) = Σ_{X₁ ⊎ ··· ⊎ X_{n_h} = X^d} Π_i=1^n_h f^bern_h,i(X_i)(4b) sum over disjoint component-set decompositions

The component sets may be empty; each Bernoulli density is zero on sets with more than one element. The hypothesis weights are nonnegative and sum to one. Both disjoint-set sums are part of the unlabelled PMBM density.

w_A ∝ Π_(i,j)∈A ℓ_ij · Π_{i missed} ℓ_i∅ · Π_{j unassigned} 1(5) exact weight in this normalized assignment benchmark

For a PPP, f^ppp(U)=exp(−Λ)∏_x∈Uλ^u(x), with Λ=∫λ^u(x)dx. A Bernoulli has f(∅)=1−r, f({x})=r p(x), and zero density for larger sets.

Exact inference for this benchmark carries every valid A. Practical PMBM implementations instead generate selected high-weight children using assignment or sampling methods, then prune or apply optional reductions such as recycling (which changes the representation). The problem here is small enough to enumerate every gated assignment, providing the exact reference for §4 — but not the full PMBM state update.

The actual PMBM association update — one predicted parent hypothesis

Let r_i be existence probability, p_i(x) the normalized single-target density, λ^u(x) the predicted undetected-target PPP intensity, c(z) the clutter intensity, and g(z|x) the measurement likelihood. The superscript “−” denotes the predicted parent. Detection probability may depend on x. The following equations are before gating:

ρ_i0 = 1 − r_i + r_i ∫(1−p_D(x))p_i(x)dx

ρ_ij = r_i ∫p_D(x)g(z_j|x)p_i(x)dx

e_j = ∫p_D(x)g(z_j|x)λ^u(x)dx, q_j = c(z_j) + e_j

w_h,A⁺ ∝ w_h⁻ ∏_iρ_i,aᵢ ∏_{j unassigned}q_j

After factoring out the common ∏_jq_j, use ℓ_i0=ρ_i0 and ℓ_ij=ρ_ij/q_j in exactly the same assignment solver. The q_j here is evidence, not the BP belief q(a). Our displayed ℓ_i0=1−P_D and clutter-only denominator require r_i=1 and e_j=0. With multiple predicted parents, their weights and local histories must also be retained and updated.

r_j,new = e_j/q_j, p_j,new(x) = p_D(x)g(z_j|x)λ^u(x)/e_j

This existence is conditional on z_j being unassigned to existing tracks. Its marginal existence is P(unassigned z_j|Z)·e_j/q_j. The density is needed only when e_j>0. “New” means newly detected; it need not mean physically born in the current scan. Clutter and a new target are the two existence outcomes of one Bernoulli, not necessarily two separately enumerated global events.

r_i,miss⁺ = r_i∫(1−p_D(x))p_i(x)dx / ρ_i0, λ^u,+(x) = (1−p_D(x))λ^u(x)

A detected existing-target branch has existence one. Its state density is proportional to p_D(x)g(z_j|x)p_i(x); a missed branch’s state density is proportional to (1−p_D(x))p_i(x). Zero-evidence branches are omitted. These are conditional state updates; a complete filter also needs prediction, history management, and a specified estimator [4].

Keep the k best global hypotheses 5

Fig. 4 — The highest-ranked assignment hypotheses in the normalized benchmark, ranked by eq. 5 (remaining rows are summarized if necessary). Each row assigns a measurement to at most one existing track or leaves it unassigned. ∅ means the measurement is unassigned, hence clutter in this benchmark. Slide k to see both discarded mass and the renormalized top-k marginals. Exact marginals continue to use all events. The first row is the toy model’s highest-weight association event, not by itself a complete PMBM multi-object estimate.

p(a_i = ·) — exact marginals, obtained by summing all hypotheses above

Renormalized top-k marginals — a different approximation from BP

Fig. 5 — Summing every row gives the exact existing-track association marginals for this normalized model — the quantity §2 approximates without constructing the list.

§4Head-to-head on the same scan

Same ℓ, same normalized assignment question, two answers. BP is exact when the relevant factor graph is acyclic; in loopy graphs it is approximate. Dragging changes both graph structure and weights, so more overlap can increase the discrepancy, but error is not a monotone function of “loopiness.” The live table reports what actually happens for each configuration.

BP final-iterate marginals

Exact assignment marginals

|difference|, percentage points

Fig. 6 — The numerical price of approximate marginalization in this scan. BP is exact on an acyclic association factor graph; on a loopy graph its Bethe fixed point may differ from exhaustive enumeration, with the size and direction determined by the actual weights.

Fig. 7 — Schematic, not a multi-scan experiment. Retained PMBM hypotheses can preserve competing explanations; pruning loses discarded histories. A track-oriented marginal filter may instead carry a product of single-track beliefs forward. That projection discards inter-track dependence even when each belief stays multimodal. Gaussian moment matching is a further, separate approximation. Neither operation is inherent to BP. The dense association subproblem costs O(T·n·m), not constant time; trajectory formulations are needed when identity/history is the explicit inference object.

The bridge: they meet in the middle

Marginal multi-Bernoulli/Poisson filters such as TOMB/P approximate a PMBM-style mixture by a single multi-Bernoulli for detected targets, while retaining the undetected-target PPP, using marginal association probabilities; BP is one efficient way to approximate those marginals. That is a specific bridge between the frameworks. It does not mean that every BP/SPA tracker is simply a PMBM filter with its hypotheses removed. TOMB/P (track-oriented) and MOMB/P (measurement-oriented) use different groupings and can have different coalescence behavior [2].

§5Cheat sheet

	Association BP inside a marginal tracker	PMBM
object kept	Approximate association marginals q(a_i=j); any downstream state representation is a separate design choice	Weighted mixture of global hypotheses; a Bernoulli per potential target per hypothesis, plus a Poisson for the undetected
core computation	Iterated messages (1)–(2) on the bipartite graph until fixed point	Compatible child generation (e.g. ranked assignment or sampling), PMBM evidence/state updates, and optional hypothesis reduction
cost / scan	`O(T·n·m)` for this dense association solver; T depends on weights and tolerance. Sparse implementations can exploit active edges. State updates cost extra.	Depends on retained parents, gated subproblems, children requested, state integration, and the assignment/sampling implementation; no universal cubic per-scan cost.
what’s approximate	The marginals themselves (Bethe fixed point; exact on acyclic factor graphs, potentially biased with loops)	The PMBM family is conjugate for the assumed model; implementations also approximate single-target integrals and use gating, hypothesis selection/pruning, merging, and numerical state representations
ambiguity over time	Track-oriented factorization discards dependence; moment matching may additionally merge modes. These are tracker choices, not a requirement of BP.	Retained global histories preserve competing explanations; trajectory variants can represent identity and history explicitly
new detections	Depends on the tracker; scalable SPA methods can introduce measurement-oriented potential objects	Undetected-target PPP; each measurement can create a Bernoulli whose evidence depends on the PPP intensity and likelihood
reach for it when	n, m are large; hard real-time budgets; dense scenes where enumeration is hopeless anyway	Ambiguity is the point: crossing / closely spaced targets, identity matters, offline or accuracy-first pipelines
lineage	Related to JPDA marginalization; convergence is specific to this association graph and assumptions	Related to MHT-style association histories, with an explicit RFS existence and undetected-object model

Table 1 — The one-screen version. Neither column dominates: retaining hypotheses is valuable when ambiguity and identity matter; BP is attractive when scale and latency dominate.

§References

J. L. Williams and R. Lau, “Approximate evaluation of marginal association probabilities with belief propagation,” IEEE Trans. Aerosp. Electron. Syst., 50(4), 2014 — the message schedule and convergence proof behind §2.

J. L. Williams, “Marginal multi-Bernoulli filters: RFS derivation of MHT, JIPDA, and association-based MeMBer,” IEEE Trans. Aerosp. Electron. Syst., 51(3), 2015 — TOMB/P and MOMB/P, the bridge of §4.

F. Meyer et al., “Message passing algorithms for scalable multitarget tracking,” Proc. IEEE, 106(2), 2018 — a broader BP/SPA tracking framework.

Á. F. García-Fernández et al., “Poisson multi-Bernoulli mixture filter: direct derivation and implementation,” IEEE Trans. Aerosp. Electron. Syst., 54(4), 2018 — the standard point-target PMBM recursion.

Benchmark assumptions: one scan; three independent, certainly existing targets; one measurement at most per target and one owner at most per measurement; constant P_D; homogeneous Poisson clutter; no PPP of undetected targets. Observation model z=x+v with R=60I and Gaussian priors P_i=S_i−R. Coordinates are arbitrary 2D units, covariances have squared units, and clutter intensity has inverse-area units. Clutter intensity is not the expected clutter count; over area V that count is λ_cV.

Gating is optional. With gating on, pairs outside χ²₂(0.99)=9.210340… are set to zero and the remaining assignment distribution is renormalized. “Exact” means exact for that restricted distribution, not for the original untruncated sensor likelihood. The demo retains ℓ_i0=1−P_D. A genuinely censored-detection model instead needs a consistently normalized in-gate likelihood and a no-in-gate-detection probability such as 1−P_DP_G. Simply drawing a 99% gate does not perform that model correction.

The solver checks both log-message change and agreement of the two edge-belief views, to tolerance 10⁻¹⁰, with a 10,000-sweep safety cap. A cap is reported as a cap, not convergence. These stopping diagnostics do not bound BP’s error relative to exhaustive enumeration. The exact problem has at most Σ_k=0³C(3,k)C(4,k)k! = 73 assignments.

Shared, dependency-free JavaScript solver for the article and slides · all computation stays in your browser · references are linked above.