# Fast computation of the TGOSPA metric for multiple target tracking via unbalanced optimal transport

arXiv: https://arxiv.org/abs/2503.09449 · HTML: https://mlsanity.com/paper/2503.09449/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 23 references that are in the map.
- First posted on arXiv 12 Mar 2025.

## Builds on (most cited first, 13 of 13)

- [Convex optimization](https://mlsanity.com/paper/2106.01946/) (2021)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Stabilized Sparse Scaling Algorithms for Entropy Regularized Transport Problems](https://mlsanity.com/paper/1610.06519/) (2016)
- [Generalized optimal sub-pattern assignment metric](https://mlsanity.com/paper/1601.05585/) (2016)
- [On the Complexity of Approximating Multimarginal Optimal Transport](https://mlsanity.com/paper/1910.00152/) (2019)
- [A metric on the space of finite sets of trajectories for evaluation of multi-target tracking algorithms](https://mlsanity.com/paper/1605.01177/) (2016)
- [Polynomial-time algorithms for Multimarginal Optimal Transport problems with structure](https://mlsanity.com/paper/2008.03006/) (2020)
- [On the complexity of the optimal transport problem with graph-structured cost](https://mlsanity.com/paper/2110.00627/) (2021)
- [Unbalanced Multi-Marginal Optimal Transport](https://mlsanity.com/paper/2103.10854/) (2021)
- [A time-weighted metric for sets of trajectories to assess multi-object tracking algorithms](https://mlsanity.com/paper/2110.13444/) (2021)
- [Scalable computation of dynamic flow problems via multi-marginal graph-structured optimal transport](https://mlsanity.com/paper/2106.14485/) (2021)
- [Graph-structured tensor optimization for nonlinear density control and mean field games](https://mlsanity.com/paper/2112.05645/) (2021)
- [TGOSPA Metric Parameters Selection and Evaluation for Visual Multi-object Tracking](https://mlsanity.com/paper/2412.08321/) (2024)

## Built on by (most cited first, 1 of 1)

- [GOSPA and T-GOSPA quasi-metrics for evaluation of multi-object tracking algorithms](https://mlsanity.com/paper/2507.13706/) (2025)

## Abstract (arXiv)

In multiple target tracking, it is important to be able to evaluate the performance of different tracking algorithms. The trajectory generalized optimal sub-pattern assignment metric (TGOSPA) is a recently proposed metric for such evaluations. The TGOSPA metric is computed as the solution to an optimization problem, but for large tracking scenarios, solving this problem becomes computationally demanding. In this paper, we present an approximation algorithm for evaluating the TGOSPA metric, based on casting the TGOSPA problem as an unbalanced multimarginal optimal transport problem. Following recent advances in computational optimal transport, we introduce an entropy regularization and derive an iterative scheme for solving the Lagrangian dual of the regularized problem. Numerical results suggest that our proposed algorithm is more computationally efficient than the alternative of computing the exact metric using a linear programming solver, while still providing an adequate approximation of the metric.