On the Convergence of Belief Propagation for Multipath Data Association in Target Tracking
2026-07-09 • Information Theory
Information Theory
AI summaryⓘ
The authors study belief propagation (BP), a method used to link measurements to targets in tracking problems. They focus on a more complex scenario called multipath data association (MPDA), where one target can create multiple measurements through different paths. The authors prove that BP converges reliably to a single solution in this case, which was not shown before. Their tests also show that BP balances accuracy and efficiency better than some existing tracking methods.
Belief PropagationData AssociationTarget TrackingMultipath Data AssociationConvergence ProofMultiple Hypothesis TrackingMeasurement PathsFixed PointGraphical Models
Authors
Kuilong Yang, Zengfu Wang, Hua Lan, Jing Fu
Abstract
Belief propagation (BP) is widely used for data association (DA) in target tracking. Existing convergence analyses of BP for DA address only the two-way correspondence between targets and measurements, where each target generates at most one measurement per scan. Multipath DA (MPDA) allows a single target to produce multiple measurements via distinct propagation paths, creating a three-way correspondence among targets, paths, and measurements, for which a complete convergence proof has not yet been provided. We provide such a proof for the BP updates in MPDA, establishing convergence to a unique fixed point. Simulations illustrate the convergence behavior of BP in MPDA and demonstrate a favorable accuracy--efficiency trade-off relative to both single-scan and two-scan variants of the multiple-detection multiple-hypothesis tracker.