On the Convergence of Belief Propagation for Multipath Data Association in Target Tracking

Technical Summary: On the Convergence of Belief Propagation for Multipath Data Association in Target Tracking

Problem Statement
Multipath Data Association (MPDA) is a critical challenge in multipath detection systems (MDS), such as skywave over-the-horizon radar (OTHR), passive radars, and urban radar networks. In these systems, a single point target may generate multiple measurements via distinct propagation paths. This creates a complex three-way correspondence among targets, propagation paths, and measurements. While traditional data association (DA) methods like Probabilistic Data Association (PDA) or Multiple Hypothesis Tracking (MHT) can be applied, they often suffer from combinatorial explosion or information loss due to probabilistic approximations.

Belief Propagation (BP) offers a scalable inference framework for MPDA. However, while convergence proofs exist for standard two-way DA (where each target generates at most one measurement per scan), a complete convergence proof for the specific BP updates used in MPDA had not been established. Previous attempts to adapt two-way DA proofs by treating (target, path) pairs as pseudo-targets lacked a rigorous demonstration of the existence of a positively invariant compact subset required for the Banach fixed-point theorem.

Methodology
The authors address this gap by providing a rigorous convergence proof for the sum-product BP algorithm applied to the MPDA formulation found in the Joint Detection and Tracking based on Variational Bayes (JDT-VB) framework.

1. Problem Formulation: The MPDA problem is modeled using a factor graph where variable nodes represent association events (linking targets, paths, and measurements) and factor nodes enforce constraints (each target-path pair generates at most one measurement; each measurement originates from at most one target-path pair or is clutter).
2. Message Passing: The algorithm iteratively updates constraint messages ($\mu_T$ and $\mu_M$) while treating evidence messages ($\mu_E$) as fixed inputs for the inner loop. The updates follow specific rational functions derived from the sum-product rule.
3. Convergence Analysis:
   • Metric Space: The authors define a logarithmic distance metric on the message space $(0, +\infty)^t$.
   • Contraction Mapping: By algebraically reformulating the message update equations into a canonical fractional form, the authors demonstrate that the update functions are strict contractions on compact subsets of the message space.
   • Invariant Subset: A key contribution is the explicit construction of a positively invariant compact subset. The authors prove that regardless of the strictly positive initialization, the message sequence enters this subset within a finite number of iterations (specifically, after the second iteration).
   • Fixed Point: Applying the Banach fixed-point theorem on this invariant subset, the paper proves that the BP updates converge to a unique fixed point.

Key Contributions

• Rigorous Convergence Proof: The paper provides the first complete convergence proof for BP in the context of MPDA, establishing that the algorithm converges to a unique fixed point for any strictly positive initialization.
• Explicit Invariant Subset Construction: Unlike previous works that assumed the existence of such a subset, this paper explicitly constructs the bounds for the compact subset that the messages enter and remain within, satisfying the conditions for the contraction mapping theorem.
• Distinction from Extended Object Tracking (EOT): The authors clarify that their convergence results for MPDA do not directly apply to Extended Object Tracking (EOT). They demonstrate that EOT and MPDA operate on fundamentally different feasible association-event spaces due to the nature of path labeling (physical distinct paths in MPDA vs. exchangeable virtual paths in EOT), preventing a direct reduction of EOT to the MPDA model.

Experimental Results
The authors conducted numerical experiments in an OTHR target tracking scenario to validate the theoretical findings:

• Accuracy: In a single-scan inference problem with small target counts, the converged BP beliefs showed high accuracy, with negligible approximation error compared to exact marginal probabilities when association ambiguity was moderate.
• Convergence Behavior: In a dense-target scenario ($X_k=100$ targets, 4 paths), the algorithm consistently converged within a moderate number of iterations (average < 30, max < 80) across 500 Monte Carlo runs.
• Performance Trade-off: When compared to Multiple-Detection MHT (MD-MHT) variants:
  • BP achieved lower tracking error (measured by Optimal Subpattern Assignment distance) than both single-scan and two-scan MD-MHT variants.
  • BP demonstrated a favorable accuracy-efficiency trade-off, offering higher accuracy than the faster single-scan MD-MHT and better accuracy than the more computationally expensive two-scan MD-MHT, with execution times intermediate between the two.
• Scalability: The algorithm's performance scaled reasonably with the number of targets and propagation paths, with execution time and iteration counts increasing as problem complexity grew.

Significance
The paper claims that establishing the convergence of BP for MPDA is essential for the reliable deployment of this inference framework in real-world multipath tracking systems. By proving that the algorithm converges to a unique fixed point, the work removes a theoretical uncertainty regarding the stability of BP in these complex three-way association problems. Furthermore, the demonstrated favorable trade-off between tracking accuracy and computational efficiency suggests that BP is a viable alternative to traditional MHT methods for multipath scenarios, offering a scalable solution without the combinatorial explosion inherent in hypothesis-based approaches.