Efficient Evaluation of Target Tracking Using Entropic Optimal Transport
Typ
Examensarbete för masterexamen
Master's Thesis
Master's Thesis
Program
Engineering mathematics and computational science (MPENM), MSc
Publicerad
2024
Författare
Nevelius Wernholm, Viktor
Wärnsäter, Alfred
Modellbyggare
Tidskriftstitel
ISSN
Volymtitel
Utgivare
Sammanfattning
Multiple target tracking deals with the task of estimating targets which appear,
disappear, and move within a scene, given data from noisy measurements. To
solve this task, a wide range of algorithms can be employed. In order to assess
the performance of such algorithms, the so-called GOSPA metric for trajectories
can be applied. This metric is formulated as an optimization problem, which has
proven computationally demanding for large problem instances. In this thesis, we
reformulate this metric in two different ways to obtain optimization problems with
optimal transport structure. Following a recent breakthrough in computational
optimal transport, we introduce entropic regularization into these formulations. For
the regularized problems, we derive and present two numerical algorithms for finding
approximate solutions. We test the performance of each algorithm on simulated
data with regards to accuracy and computational efficiency. The numerical results
suggest that the regularization can be made small enough to allow for an adequate
approximation of the GOSPA metric for trajectories while simultaneously allowing
a satisfactory convergence rate. Lastly, we compare the running time of our most
efficient algorithm with that of a conventional linear programming solver. If a small
approximation error is allowed, we find that our algorithm scales better both when
the number of trajectories in the data increases, and when the number of considered
time steps in the data increases.
Beskrivning
Ämne/nyckelord
multiple target tracking, GOSPA metric, convex optimization, duality, optimal transport, tensor optimization problem, network flow problem, entropic regularization, coordinate ascent, Sinkhorn iterations