Statement
In Gaussian mixture reduction for tracking and filtering applications, Runnalls’ greedy pairwise merging algorithm — which iteratively merges the pair of components minimizing a closed-form upper bound on the increase in KL divergence between the original and the reduced mixture — performs essentially as well as much more expensive algorithms (GMRC, brute-force ISE-optimal initialization + Quasi-Newton refinement) on the actual filtering metric of interest (lost tracks, RMSE), even though those expensive methods are measurably better on the raw ISE between the original and reduced mixtures. The corollary is that the additional machinery in GMRC (KL-based k-means refinement, ISE Quasi-Newton step over means and Cholesky factors) buys real ISE improvements that do not propagate to downstream estimation accuracy in standard tracking settings, and is therefore not worth its >10,000x wall-time cost in the inner loop of a tracker.
Evidence summary
The supporting evidence is from a single paper, Crouse et al. (2011), with two experimental setups:
- Random mixtures, 4-dimensional, N=10 → L=5, 500 Monte Carlo runs. GMRC wins on ISE (0.0482 vs Runnalls 0.0834 vs COWA 0.1165 vs brute force 0.0359). GMRC takes 53.45 s/run vs Runnalls 0.005 s/run. So on the raw ISE objective the expensive methods do measurably better, by ~42%.
- Salmond-style 2D tracker, L=3, 1000 Monte Carlo runs over 50 steps. Runnalls and GMRC are statistically tied (3.15% vs 3.25% lost tracks, RMSE 7.98 vs 8.26). COWA collapses (25.35% lost tracks). The improvement that GMRC’s k-means + Quasi-Newton refinement bought on raw ISE simply does not show up in tracker performance.
The combination of the two experiments is what makes the claim non-trivial: it is not that Runnalls is just-as-good on a metric nobody cares about, it is that Runnalls is just-as-good on the downstream tracker metric despite losing on the upstream ISE metric, indicating that the residual ISE that Runnalls leaves on the table is not in directions that the filter cares about.
Conditions and scope
The claim, as supported by the current evidence, is narrow:
- Tracker type: Salmond-style multi-hypothesis tracker (Salmond 1990, refined 2009).
- Number of retained hypotheses: L = 3.
- State dimension: 2 (Cartesian position, with constant-acceleration motion model).
- Clutter regime: Poisson clutter density 5.6e−5, p_d = 0.7, large measurement noise (60 on the diagonal).
- Mixture geometry: Wishart-distributed covariances (mean ~ I/10), uniform-in-box means, Dirichlet weights — i.e. fairly homogeneous component scales.
The claim does not transfer automatically to:
- Higher-dimensional state spaces (e.g. 6D position+velocity, 9D position+ velocity+acceleration).
- Switching state estimation with much larger regime branching (Markov-jump linear systems with 4+ regimes per step).
- IMM-style filters (which use a different mixing rule).
- Mixtures with very disparate covariance scales (where the KL bound’s tightness may degrade).
- Non-tracking GMR applications (distributed data fusion, message passing on lattice codes, supervised pattern recognition).
For switching Kalman filters and Rao-Blackwellized particle filters over regime histories, the result is plausible but unverified — those filters have similar mixture-collapse structure but different geometry.
Counter-evidence
- None directly in the wiki yet. The Crouse paper itself notes that on the raw ISE benchmark the expensive methods (GMRC, brute force) are measurably better than Runnalls — so the claim is specifically about the downstream metric, not about ISE itself. Anyone using GMR for a non-filter task (density estimation, posterior summarization for reporting, distributed inference) should not infer from this claim that Runnalls is universally sufficient.
- The COWA’s underperformance in this comparison was observed under the constraint γ = ∞ and ε = 0, which disables COWA’s main feature (automatic order determination). A fair comparison of COWA in its intended operating regime might tell a different story.
Linked ideas
(none yet)
Open questions
- Does the parity transfer to switching Kalman filters / Markov-jump linear systems with larger regime branching (> 4 regimes per step)?
- Does it transfer to Rao-Blackwellized particle filters over regime histories, where the “mixture” being collapsed is conditional on a particle’s regime path?
- How does the parity behave as state dimension grows (4D, 6D, 9D)?
- Is there a quantitative criterion (e.g. on the spread of component covariance scales, or on the sharpness of the posterior) that predicts when Runnalls is sufficient and when GMRC genuinely helps downstream?
- Does the negative-weight bug in unconstrained COWA / GMRC (which Crouse et al. fix with a convex QP) explain divergence reports in other authors’ implementations of these methods?