1

A metric for sets of trajectories that is
practical and mathematically consistent

arXiv:1601.03094v2 [] 6 Mar 2018

José Bento jose.bento@bc.edu
Jia Jie Zhu zhuuv@bc.edu

Abstract—Metrics on the space of sets of trajectories are
important for scientists in the field of computer vision, machine
learning, robotics, and general artificial intelligence. However,
existing notions of closeness between sets of trajectories are either
mathematically inconsistent or of limited practical use. In this
paper, we outline the limitations in the current mathematicallyconsistent metrics, which are based on OSPA [1]; and the
inconsistencies in the heuristic notions of closeness used in
practice, whose main ideas are common to the CLEAR MOT
measures [2] widely used in computer vision. In two steps, we
then propose a new intuitive metric between sets of trajectories
and address these limitations. First, we explain a solution that
leads to a metric that is hard to compute. Then we modify this
formulation to obtain a metric that is easy to compute while
keeping the useful properties of the previous metric. Our notion
of closeness is the first demonstrating the following three features:
the metric 1) can be quickly computed, 2) incorporates confusion
of trajectories’ identity in an optimal way, and 3) is a metric in
the mathematical sense.

I. I NTRODUCTION
Similarity measures for sets of trajectories are very important. In computer vision, they are used to evaluate the
performance of multi-object tracking algorithms. If GT and
O are the ground-truth and output trajectories of a tracker, a
similarity measure D can be used to distinguish a good tracker
from a bad one, i.e. D(GT, O) = small implies O is a good
tracker. In machine learning, algorithms such as [3], [4] and
[5], can only cluster, classify and do a nearest neighbor search
on sets of trajectories, if we have a similarity measure.
Given their importance, one would expect that existing
widely-used measures would be easy to compute and would
not produce counter-intuitive results. Surprisingly, this is not
the case, leaving a critical problem unsolved.
The main limitation of most similarity measures is that they
are not a mathematical metric. For example, the CLEAR MOT
measures, widely used to evaluate the performance of trackers,
are based on a heuristic and are not a metric. If a measure does
not satisfy, for example, the triangle inequality (cf. Section
III ), then we cannot guarantee that two good trackers (good
according to this measure) produce similar outputs, which is
counter-intuitive. In addition to this inconsistency, the CLEAR
MOT also produce other counter-intuitive results (cf. Section
VI). Furthermore, these results indirectly affect many other
similarity measures that internally use the CLEAR MOT, or
similar heuristics, to precompute an association between two
sets of trajectories (e.g. [6]–[9]).
However, even existing measures that are a metric, and that,
we believe, are all variants of OSPA, can produce unreasonable
results in simple scenarios (cf. Section II). We use OSPA-ST

to refer to OSPA applied to sets of trajectories since it was
not originally defined for this setting.
On the positive side, both the CLEAR MOT and the OSPAbased metrics are easy to define and have a computation time
that scales well with the number and length of trajectories.
These two attributes are part of the reason why the CLEAR
MOT are popular.
In this paper we introduce the first measures that are
simultaneously a mathematical metric, do not replicate the
counter-intuitive results of OSPA-ST or CLEAR MOT and
can also be quickly computed (cf. Section VII).
In the next section, we use an example to introduce the
primary technical challenge in defining a measure for sets
of trajectories and how this is addressed by OSPA-ST, the
CLEAR MOT, and our metrics. We focus on OSPA-ST and
the CLEAR MOT because they give a simple but powerful
overview of the main ideas leading up to our work. We include
a detailed list of related work in Section V.
II. M AIN CHALLENGE : THE ASSOCIATION PROBLEM
B1
A1
0.5

C1
C2

0.5
T1

T2

T3

A2
B2

Fig. 1. Two people, A1 and A2 , move along a line and are followed by two
trackers that generate outputs B1 , B2 , C1 and C2 . For visualization purposes,
trajectories that are close are actually on top of each other.

Figure 1 shows three sets of trajectories A, B and C. Set A
has the ground truth trajectories of two people that start at a
distance 1.0 from each other and, twice, quickly exchange
positions; B and C are the trajectories that two different
tracking algorithms output. We represent time on the x-axis
(left to right) in frames and space on the y-axis (top to bottom).
For convenience, T1 , T2 and T3 are normalized to sum to
1.0. We seek a distance measure D for sets of trajectories to
determine if B (and/or C) is a good tracker.
If A and B only contained one trajectory, say A1 and
B1 , we could define D(A, B) by computing the distance
between A1 and B1 at each frame and returning the average
distance over frames. Since this is not the case, the next
idea is to define D in two steps. Step 1: determine, for each
frame, if we should compute the distance between A1 and
B1 and between A2 and B2 or if we should compute the

2

distance between A1 and B2 and between A2 and B1 . We
refer to step 1 as finding an association between A and B.
If, at a certain frame, we decide to compute the distance
between A1 and B2 and between A2 and B1 , then we say
that, at that frame, we associate A1 with B2 and A2 with
B1 . Later, we formally define associations using permutations
(See Section III). Step 2: given this association, compute the
average distance between associated points.
The main problem in defining D is to establish an association, i.e. step 1 above. Loosely speaking, typical approaches
involve choosing an association that makes the average distance between associated points small. We can divide different
approaches in three cases. The association between A and
B (i) can change freely from frame to frame; (ii) cannot
change; and (iii) can change from frame to frame but we pay
a (smaller/higher) cost for (smaller/bigger) changes. We call
this last cost a switching cost. We name the total (or average)
distance between associated points the distance cost.
In (i), a “good tracker” tracks position accurately even if
it does not track peoples’ identities (ID) correctly. At each
frame, we associate A to B such that the sum of the distance
between associated points is minimal. For Fig 1, we obtain an
average distance between A and B (over frames and objects)
that is D(A, B) = 0 and an average distance between A and
C that is D(A, C) = 0.5. Tracker B is better than C. Notice
that from T1 to T2 track B1 changes the person it is tracking.
We call this as an identity switch.
In (ii), the tracker’s output B1 must either be associated
with A1 for all frames or associated with A2 for all frames.
B2 is associated with the other trajectory in A. Between these
two possibilities, we again choose the one that minimizes the
average distance (over frame and objects). Now D(A, B) =
min{T2 , 1 − T2 } and D(A, C) = 0.5. Tracker C can be as
good as tracker B (for T2 = 1/2), which is counter-intuitive,
because C’s output is never close to the ground-truth.
In (iii), a “good tracker” must trade off some position
accuracy (distance cost) for some ID accuracy (switching
cost). The switching cost penalizes identity switches. It is also
evident that category (iii) includes (i) and (iii) as particular
cases of extreme tradeoffs.
The most widely used measures fall in category (iii). In
computer vision, the prototypical example is MOTP, one of the
CLEAR MOT measures. At each frame, MOTP heuristically
tries to maintain the association between A and B as close
as possible to the association made in the previous frame. It
makes corrections to the association only if the association
created in the previous frame applied to the current frame
produces distances between matched points that are larger than
a certain threshold thrM OT . In the first frame, MOTP uses the
association that minimizes the total distance. (cf. Definition
7 in Appendix A for a formal definition). By changing this
threshold one can have different results. We always have
D(A, C) = 0.5. If thrM OT is small, then D(A, B) = 0,
because we switch association twice. However, if thrM OT
is large, D(A, B) = T2 , because we never change from the
association made in the first frame. Unfortunately, this heuristic leads to MOTP not being a metric and to other counterintuitive results (cf. Section VI). In addition, all metrics (based

on OSPA) fall in category (ii) because their associations are
fix in time. Thus, the applications where they produce intuitive
results are limited. We give another example of how OSPAST can produce counter-intuitive results in an accompanying
document (www.jbento.info/papers/metriccompanion.pdf).
Like the CLEAR MOT, our measures fall in category (iii).
However, ours do not compute the association between A
and B heuristically or sequentially. Rather, we solve a global
optimization problem such that the sum of the distance cost
and the switching cost over all time frames is minimized. Thus
we avoid counter-intuitive results and obtain a metric.
To appreciate the difference between optimizing associations globally or sequentially, notice that, for Figure 1,
MOTP either does not change the association across frames or
changes it twice, from T1 to T2 and from T2 to T3 . Regardless
of T1 , T2 and T3 , MOTP never considers changing association
just once. This happens because MOTP uses a fixed threshold
to decide when to change associations. Hence, it fails to
explore possibly better ways in which to compare A and B.
III. S ETUP AND NOTATION
We denote the collection of all finite sets of finite trajectories
by S. We reserve the letters A, B and C to represent finite
sets of finite trajectories. Ai is the ith trajectory in A. Each
trajectory Ai is a finite set of time-state pairs (t, x) with time
t ∈ N and state x ∈ Rp . We focus on t ∈ N but it is possible
to generalize our results to continuous time. We use Ai (t) to
represent the state of the ith trajectory in A at time t.
When A and B are defined for all time instants and have the
same number of trajectories, we can express D(A, B) using
very simple notation. However, Ai (t) might not be defined for
all values of t. In addition, A and B might have a different
number of trajectories. Thus, for mathematical convenience,
we define a symbol ∗ and the following extension procedure.
m2
1
Given A = {Ai }m
i=1 and B = {Bi }i=1 , we let m =
+ m
+
m1 + m2 and define A = {Ai }i=1 and B + = {Bi+ }m
i=1
as follows. Let T be the largest time index for which either
A or B have trajectories with defined states. If i ≤ m1 , then,
for all t such that Ai (t) is defined, we set A+
i (t) = Ai (t).
Otherwise, A+
(t)
=
∗.
If
m
<
i
≤
m
then
A+
1
i
i (t) = ∗
+
for all t ∈ {1, ..., T }. We call these Ai , ∗-only trajectories.
We define B + in the same way. Now A+ and B + both have
m trajectories and their states are defined in the extended set
Rp ∪ {∗} for all t ∈ {1, ..., T }. We call A+ and B + extended
sets of trajectories. Figure 2-(b) exemplifies this procedure.
For example, A+
1 agrees with A1 for all t except for t = 3 for
which A1 is not defined and A+
1 = ∗.
The meaning of an instant t for which Ai (t) is not defined,
i.e. A+
i (t) = ∗, depends on the application, e.g. it might mean
an occlusion. Other interpretations are possible, e.g., an object
has yet to come into existence. We refrain for adhering to a
particular interpretation of ∗. Our use of ∗ resembles [10],
where a null symbol ∅ is used.
We use D : S × S 7→ R+
0 to represent distance measures
on S. If A, B ∈ S, then D(A, B) measures the distance
between A and B. The main goal of this work is to introduce
mathematical metrics that are also easy to compute and
produce intuitive results. Recall that, for any A, B, C ∈ S,

3

a metric D must satisfy the properties (i) (non-negativity)
D(A, B) ≥ 0, (ii) (coincidence) D(A, B) = 0 iff A = B, (iii)
(symmetry) D(A, B) = D(B, A) and (iv) (sub-additivity)
D(A, C) ≤ D(A, B) + D(B, C).
Our definition of D in the following sections needs two ingredients: an association between extended sets of trajectories
and a distance between extended trajectories’ states.
We formally define an association between two sets of m
elements using permutations. A permutation σ : i 7→ σi is a
bijective map from {1, ..., m} to itself. Π denotes the set of
all permutations. We define the composition of σ, σ 0 ∈ Π as
σ 0 ◦ σ : i 7→ σσ0 i . σ −1 is the inverse map of the bijection σ.
An association σ ∈ Π between A and B for which σi = j
tells us that, to compute D(A, B), we will use distances
+
between the states of A+
i and the states of Bj (See e.g.
Def. 4). In this case, we say that σ associates trajectory A+
i
to trajectory Bj+ . Because computing D(A, B) might involve
computing distances between different pairs of trajectories Ai ,
Bj at different points in time, we extend the terminology
“association” to also mean a sequence of permutations. We
define ΠT = {Σ : Σ = (Σ(1), Σ(2), ..., Σ(T )), Σ(t) ∈
Π ∀t} as the set of all length-T sequences of associations.
Σi (t) is the image of i by the map Σ(t) ∈ Π. We define
Σ−1 , (Σ(1)−1 , ..., Σ(T )−1 ) ∈ ΠT and Σ0 ◦ Σ , (Σ0 (1) ◦
Σ(1), ..., Σ0 (T ) ◦ Σ(T )) ∈ ΠT . An association sequence
Σ ∈ ΠT between A and B for which Σi (t) = j tells us
that, to compute D(A, B), we will use the distance between
+
A+
i (t) and Bj (t) (See e.g. Def. 3). In this case, we say that
+
Σ associates the state A+
i (t) to the state Bj (t) at time t.
+
p
p
We use d : R × R 7→ R0 to indicate a distance
between state elements. We define the extended distance
d+ : Rp ∪ {∗} × Rp ∪ {∗} 7→ R+
0 such that for every
x, y ∈ Rp we have (i) d+ (x, y) = min{2M, d(x, y)}, (ii)
d+ (x, ∗) = d+ (∗, x) = M > 0 and (iii) d+ (∗, ∗) = 0.
Property (iii) guarantees that placeholders by themselves do
not change the distance between A and B. Property (ii) defines
a cost M for comparing two states, one of which is not defined.
For example, a larger M might indicate a higher penalty for
a missed or false track. Property (i) of d+ is a technicality
that makes d+ be a metric. We define DAB (t) ∈ Rm×m with
+
element (ij) equal to d+ (A+
i (t), Bj (t)).
In the context of computer vision tracking, having m2 ∗only trajectories in A+ , i.e. trajectories will all states equal
to ∗, and m1 *-only trajectories in B + , allows two important
types of associations. In computing D(A, B), we might not
want to use any distance between a ground-truth trajectory in
A, say A1 , and any reconstructed trajectories in B. We get this
+
by associating A+
1 to a ∗-only trajectory in B . The points
in A1 are miss detections. A reconstructed trajectory, say B1 ,
might not be related to any ground truth trajectories in A.
We represent this by associating B1+ to a ∗-only trajectory in
A+ . B1 is a spurious trajectory. To create the possibility that
all ground truth trajectories might be missed and all tracker
trajectories might be spurious, we need at least m2 *-only
trajectories in A+ and m1 *-only trajectories in B + .
With a particular application in mind, we might want to distinguish occlusions and no-target or penalize missed and false
tracks differently. In this case, we might introduce multiple

Symbols

Meaning

A, A+
Ai (t), A+
i (t)
∗
S
D
d, d+
M
AB (t)
Dij
Π
σ, σ −1 , σi
Σ, Σ−1
Σi (t)
ΠT
K(Σ)
w, W
Wij (t)
P
PT
k.k, †, tr

Set of trajectories and set of extended trajectories
State of ith trajectory in A, and A+ , at time t
Symbol to mark states outside Euclidean space
Set of all possible trajectories
Distance between trajectory sets
Distance between states and between extended states
Cost between state * and state in Euclidean space
+
Distance d+ between extended states A+
i (t) and Bj (t)
Set of all possible permutations (perms.)
Permutation, its inverse, the image of i by the map σ
Sequence of permutations, sequence of their inverses
The image of i by the map Σ(t) in the sequence Σ
Set of all possible sequences of perms. of length T
Switching cost of permutation sequence Σ
Doubly stochastic matrix (d.s.m.), sequence of d.s.m.
Entry (ij) of the tth d.s.m. of the sequence W
Set of all possible d.s.m.
Set of all possible sequences of d.s.m. of length T
Operators for matrix norm, transpose, trace

different placeholder symbols during the extension procedure,
say ∗ and #, and extend the definition of d+ to penalize
different symbol comparisons differently, e.g. d+ (∗, #) = M1 ,
d+ (∗, x) = M2 , d+ (#, x) = M3 , d+ (∗, ∗) = d+ (#, #) = 0.
Not all interpretations and uses of these symbols make
sense. Let B be the output of a tracker and A the ground
truth. If B + has one ∗-only trajectory, a miss detection, and
A has one ∗-only trajectory, an always occluded object, then
D(A, B) = 0, even tough there is a cardinality error. This
occurs because the meaning of ∗ in A and B is inconsistent.
We could have used a different symbol for miss detections, ∗,
and occluded ground truth, #. Furthermore, it is unreasonable
to let always-hidden objects be part of the ground truth, i.e.
let A have one ∗-only trajectory. Otherwise, a tracker is only
good if it can find the number of objects behind a curtain.
(a)

t 2 {1, 2, 3}

A

A1
1

A2

1

⌃

2 3
2 3

3

B1

B

3 21

A1(2)

B1(1) B1(2)

B1:
B2: B (1)
2

B

B2(3)

B2

d(A1 (2), B1 (2))) + d(A1 (3), B1 (3)))+
d(A2 (1), B1 (1))) + d(A2 (2), B2 (2)))+

Fig. 2.

(b)
A1(3)

2 1

D(A, B) = d(A1 (1), B2 (1)))+

d(A2 (3), B2 (3)))

A
A1:

A+
A+1: *
A+2: *
A+3: *

A1(3)
A1(2)
* *
* *

+
B1(1) B1(2) B
+
B 1:
*
B+2:B (1)*
B
2
2(3)
B+3:
* * *

(a) Role of associations in computing D; (b) Extension procedure.

Figure 2-(a) illustrates how we can use an association Σ
between A and B and distance d+ between state elements
to define a distance D(A, B). In Fig. 2-(a) we have dropped
+
for clarity. In this figure we have Σ = (Σ(1), Σ(2), Σ(3))
where Σ(1) = (2, 1), Σ(2) = (1, 2), Σ(3) = (1, 2).
In this paper we denote the set of doubly stochastic matrices
as P = {w ∈ Rm×m : w† 1 = 1, w1 = 1, w ≥ 0}. We also
define P T = {W : W = (W (1), ..., W (T )), W (t) ∈ P ∀t} as
the set of all length-T sequences of doubly stochastic matrices.
Without specification, k·k denotes the Euclidean norm, k·k1
denotes the 1-norm, † means transpose and tr matrix trace.
The above table gathers the most important notation used.

4

IV. P ROPOSED METRICS
Here we introduce two novel families of metrics. We study
their properties in Section VII.
Consider a map K:ΠT 7→ R+
0 that gives a score, a switching
cost, to sequences of associations and a map d : Rp × Rp 7→
R+
0 that computes distances between trajectories’ states. Recall
+
AB
(t) = d+ (A+
that Dij
i (t), Bj (t)) depends on d’s definition.
Definition 1. The natural distance induced by K and d
between two sets of trajectories is a map Dnat : S × S 7→ R+
0
such that for any A, B ∈ S
Dnat (A, B)= min

Σ∈ΠT

T X
m
n
o
X
K(Σ) +
DiAB
Σi (t) (t) .

(1)

Definition 2. The natural computable distance induced by
k.k and d between two sets of trajectories is a map Dcomp :
S × S 7→ R+
0 such that for any A, B ∈ S
W ∈P T

+

T X
m
X

−1
n TX
t=1

o
AB
Wij (t) Dij
(t) .

kW (t + 1) − W (t)k
(2)

t=1 i,j=1

A few important observations follow. First, notice that both
measures minimize the sum of a distance cost plus a switching
cost. Second, notice that we are defining a family of measures,
not just two measures. Since d, K and k.k are generic, our
definitions can easily incorporate a scaling factor in front of
each term of equations (1) and (2). Therefore, we can control
the relative importance of the switching and distance costs.
Third, P is a convex set and any norm k.k is convex
in P, so computing Dcomp amounts to solving a convex
optimization problem, for which there are easy-to-use and
efficient packages, e.g. CVX [11]. Later we show one choice
of k.k, among several, that reduces (2) to a linear program
(LP). From this LP, we can approximate Dnat by forcing
the variables to be in {0, 1} and then use techniques such as
branch-and-bound, e.g. available in MATLAB and CPLEX.
Both Dcomp and Dnat solve a global optimization problem
to find the best tradeoff between distance cost and switching
cost. As explained in Section II, this is in contrast to most
measures used in practice such as MOTP, as explained below.
1 By

DM OT P (A, B) =

T X
m
X

the Birkhoff–von Neumann theorem we know that P is smallest convex
set that contains all permutations (represented as permutation matrices).

DiAB
ΣMOT

i

(t) (t).

(3)

t=1 i=1

In the definition above, ΣMOT ∈ ΠT is the sequence of
associations that CLEAR MOT builds heuristically (explained
in Section II and formally in Appendix A).
We also know that Dnat and Dcomp are more flexible than
OSPA-ST, where associations cannot change with time. To
see this, compare (1) and (2) with the definition of OSPA-ST
below.
Definition 4. The OSPA-ST metric is defined as

t=1 i=1

A natural choice for d is the Euclidian metric, that
0
is, d(x, x0 ) = kx
PT−−1x k2 . One intuitive choice for K is
Kcount (Σ) = α t=1 I(Σ(t + 1) 6= Σ(t)), α > 0, that
basically counts the number of times we change association.
We give other definitions for K in Section VII.
Generally, computing Dnat is a combinatorially hard problem so we introduce a new metric that uses doubly stochastic
matrices instead of permutations as associations between A
and B 1 . Consider any norm k.k on the space of matrices.

Dcomp (A, B) = min

Definition 3. The CLEAR MOT’s distance measure for evaluating tracking precision is called MOTP and is defined as

DOSP A−ST (A, B) = min
σ∈Π

T X
m
X

DiAB
σi (t).

(4)

t=1 i=1

Our metrics include OSPA-ST as a particular case. Indeed, we recover OSPA-ST metric if we choose K as:
KOSP A−ST (Σ) = 0 if Σ = (σ, σ, ..., σ), for some σ ∈ Π, and
KOSP A−ST (Σ) = ∞ otherwise. In this case, we can compute
Dcomp in polynomial time, just like for OSPA-ST, using e.g.
the Hungarian algorithm [12] (cf. [1]).
The doubly stochastic matrices W (t) of Dcomp , can be
transformed into permutations using a projection procedure
that amounts to solving a LP. However, we cannot obtain doubly stochastic matrices from Dnat . We can use the associations
from Dnat and Dcomp to improve the computation of other
heuristic measures of multi-target tracking performance, e.g.
the number of ID switches or track purity.
Since d+ (∗, ∗) = 0, the ∗-only trajectories add zero distance
cost when associated with each other and so our metrics do
not produce irrelevant switches between ∗-only trajectories.
In addition, although K is a function of Σ but not of A and
B, when a particular application is in mind, we can have K
treat switches between different indices differently. We might,
for instance, impose that confusing the ID of tracks 1 and 20
(e.g. different-team players) should be heavily penalized but
confusing the ID of tracks 1 and 4 (e.g. same-team players)
should not. Also, we can impose that a switch between a
detected person and a ∗, a non-detected person, should have
a different cost than a switch between two detected persons.
Finally, using duality, and from now on using more compact
matrix notation, we can equivalently define Dcomp (cf. (2)) as
Dcomp (A, B) = min

W ∈P T

T
X


tr W (t)† DAB (t)

t=1

subject to

T
−1
X
t=1

kW (t + 1) − W (t)k ≤ α

for some α. Acting by analogy, Dnat can also be re-defined
in a similar way. In other words, we do not need to worry
about the sum of distance cost and switching cost.
V. R ELATED WORK
Except for our work, we found no similarity measure for
sets of trajectories that is both mathematically consistent (a
metric) and, at the same time, is useful and can deal with

5

identity switches, i.e. it allows time-dependent associations.
We focus our discussion around these characteristics. However,
several of the ideas we review can be incorporated into our
metrics to define new variants that compete with past work in
settings not discussed, given the scope of this paper.
Our work is related to the general problem of defining a
distance between two sets, however, this is a topic too vast to
review in this paper alone. In [13], the reader can find many of
those distances. In this article, the two sets A and B are sets of
trajectories, and this limits the scope of our discussion. In the
simplest case, when trajectories have only one vector, typical
definitions compute an average or sum distance between all
pairs of elements from A and B or just from a few pairs, e.g.
[14]. Knowing which pairs to use when computing distances
requires a procedure that matches elements of A with elements
of B, e.g. [1], [15]. In general, however, each trajectory is
composed of a set of vectors indexed by time, which limits
our discussion even more.
To the best of our knowledge, the most rigorous works on
metrics for sets of trajectories are based on [1]. In [1] the
authors propose a distance for sets of vectors, the optimal subpattern assignment metric (OSPA), and explain its advantages
over other distances in the context of multi-object filters. The
OSPA metric has better sensitivity than the Hausdorff metric
to cardinality differences between sets and does not lead to
complicated interpretations as does the optimal mass transfer
metric (OMAT) [16], proposed to address the limitations of
the Hausdorff metric. OSPA, a metric for sets of vectors, can
be defined from any distance between two vectors.
All the spin-offs of [1] focus on designing a metric for
two sets of trajectories for the purpose of evaluating the
performance of tracking algorithms. We recall however that,
apart from tracking, many applications in machine learning
and AI benefit if we work with a metric rather than a similarity
measure that is not a metric. For example, the algorithms
mentioned in the introduction [3]–[5] can only cluster, classify
and find nearest neighbors if D is a metric. None of the
spin-offs of [1] allow associations that change with time and
hence suffer from the same restricted applicability as OSPA
(cf. Section II-(ii)).
The OSPA-T metric [10] for sets of trajectories is defined
in two steps. First, we optimally match full tracks in A to full
tracks in B while considering that tracks have different lengths
and can be incomplete. Second, we assign labels to each track
based on this match and compute the OSPA metric for each
time using a new metric d for pairs of vectors. d uses both
the vectors’ components and their labels. Finally, we sum the
OSPA values across all time instants. Although the first step
alone defines a metric, the authors in [17] point out that the
full two-step procedure that describes OSPA-T is not a metric.
[17] defines the OSPAMT to be a metric and be more
reliable than OSPA-T. The OSPAMT metric also optimally
matches complete trajectories in A to complete trajectories in
B but unlike OSPA-T allows us to match one trajectory in A to
multiple trajectories in B (and vice-versa). The authors make
this design choice to not penalize a tracker when it outputs
only one track for two objects that move closely together.
Some extensions to OSPA incorporate measurement uncer-

tainty. The Q-OSPA metric [18] weighs the distance between
pairs of points by the product of their certainty and by
adding a new term that is proportional to the product of
the uncertainties. The H-OSPA metric [19] uses OSAP with
distributions as states instead of vectors and uses the Hellinger
distance between distributions instead of the Euclidean distance between vectors. Both works only allow sets that contain
points, not trajectories. However, it is easy to combine them
with [10] or [17] and get a metric for sets of trajectories.
The papers above are relatively recent, as is the search
for mathematical metrics for sets of trajectories. However,
researchers studying multi-object tracking have been using
similarity measures for sets of trajectories to rank tracking
algorithms for a while. Reviewing all the work done in this
area is impossible. Especially because evaluating tracking
performance has many challenges other than the problem
of defining a similarity measure. See [20], [21] for some
examples. Nonetheless, we mention various works that relate
to our problem. We emphasize that none of the following
works defines a metric mathematically.
Most of our paper is about finding an association between
the elements in A and B (cf. Section II). In [22], which is
expanded in [23], the authors are one of the first to identify
this as the central problem in defining D, although some of
their ideas draw from the much earlier Ph.D. thesis of one
of the authors [24]. They propose an one-to-one association
between A and B but this association is optimally computed
independently at every time instant. Also, there is no discussion about the number of association changes that might occur.
The CLEAR MOT are used widely in part because they
allow control over the number of times that the association
between A and B changes. It appears that [25] is one of
the first that allow this. Like the CLEAR MOT, [25] uses a
sequential matching procedure that tries to keep the association
from the previous time instant if possible. The association that
[25] uses at each time t is not one-to-one optimal like in
[22] or in the CLEAR MOT. Rather, the authors use a simple
thresholding rule to decide which elements to associate. The
idea of using a simple threshold rule to associate A and B has
survived until relatively recently. For example, [26] match a
full trajectory in A to a whole trajectory in B if they are close
in space for a sufficiently long time interval. The authors in
[27] use a similar thresholding rule.
Shortly after [22] and [23], some of the same authors
discuss again the problem of associating A to B. [28] proposes
four different methods for this problem. First: A and B are
optimally matched independently at each time instant, possibly
generating different associations at every time instant. Second:
the association between A and B cannot change with time.
Like in the OSPA-based metrics, this restricts the measure’s
applicability (cf. Section II). Third: allow the association
between A and B to change in time but only in special
circumstances. Unfortunately, as they point out, this leads
to an NP-hard problem. Fourth: use heuristics to minimize
the number of changes in association. Some of these ideas
resemble those used in the CLEAR MOT.
Measuring trackers’ performance is not just about defining
similarity measures for sets of trajectories, or only concerned

6

with establishing associations between A and B. If we have
already matched the elements of A and B, which quantity
should we compute from this match? A typical quantity that
researchers calculate is the average or total distance between
matched points. Our metrics are a combination of this quantity
with the switching cost in the A-B association. Distancerelated quantities apart, researchers also compute quality measures for the match itself, e.g. the number of trajectories in A
that do not match to any trajectory in B (spurious tracks and
missed tracks) or the number of times the match between A
and B changes. Quantities like track purity and coalescence
are often also computed once a match is established. [6]–[8]
and [9] list many other measures of similarity between A and
B and measures of quality for individual tracks.
It is worth mentioning a few non-mainstream works. [29]
defines a distance based on comparing the occurrence of special discrete events in A and B. [30] proposes an information
theoretic similarity measure. Finally, [31] proposes a similarity
measure based on hidden Markov models to allow unequal
temporal sampling rates in the trajectories.
VI. L IMITATIONS OF THE CLEAR MOT
In the context of visual tracking, the next lemma shows
that there are situations in which the average tracking distance
cost over time gets arbitrarily close to zero with time while
the CLEAR MOT produces an association ΣMOT that fails to
see that. In other words, the CLEAR MOT can be counterintuitive. Since none of the definitions of Section IV deal
with time averages, in this section we use the following two
definitions.
For any Σ ∈ ΠT , A, B ∈ S we let
T −1
1 X
I{Σ(t) 6= Σ(t + 1)}
swi(Σ) =
T − 1 t=1

(5)

denote the empirical frequency of identity switches, i.e. association changes, where I{·} is the indicator function. Let
dist(Σ, A, B) =

T
m
1 X X AB
D
(t)
T t=1 i=1 i Σi (t)

(6)

denote the average distance between A and B under Σ =
(Σ(1), ..., Σ(T )). Note that, for example, DM OT P = T ×
dist(ΣM OT P , A, B).
Lema 1. For any threshold thrM OT >0, there exists trajectory
sets A, B ∈ S and an association Σ ∈ ΠT such that
dist(Σ, A, B) < O(1/T ),
swi(Σ) = 0 and,

dist(ΣMOTP , A, B) > m thr − O(1/T ).
The following lemma shows that, for any thrM OT > 0, the
MOTP measure is mathematically inconsistent.
Lema 2. MOTP is not a metric for any threshold thrM OT >0.
The proofs of these two lemmas are in Appendix A.
It is also possible to prove that MOTA, the other widely
used measure in the CLEAR MOT, does not define a metric.
See www.jbento.info/papers/metriccompanion.pdf.

VII. P ROPERTIES OF OUR METRICS
The metrics we introduce do not produce the counterintuitive results of OSPA-ST or MOTP because they control
the tradeoff between switches and distances in a globally
optimal way. In addition, we also show that they are a metric
under mild conditions on K, k.k and d.

Definition 5. A map K : ΠT 7→ R+
0 is a permutation measure if it satisfies the following three properties (i) K(Σ) = 0
if and only if Σ is constant Σ = (σ, σ, ..., σ) for some σ ∈ Π,
(ii) K(Σ−1 ) = K(Σ) and (iii) K(Σ ◦ Σ0 ) ≤ K(Σ) + K(Σ0 ).
Clearly, if K is a permutation measure so is αK, α > 0.
One straightforward choice for K is to count the number of
times that the association between A and B changes.
PT −1
Theorem 1. Let Kcount (Σ) =
t=1 I(Σ(t + 1) 6= Σ(t)).
Kcount is a permutation measure.
Another two desirable choices for K are (a) the function
that sums the minimum number of transpositions to go from
one permutation to the next and (b) the function that sums the
number of adjacent transpositions to go from one permutation
to the next. In what follows kCayley (σ) gives the minimum
number of transpositions to obtain the identity permutation
from σ ∈ Π and kKendall (σ) gives the number of adjacent
transposition that the Bubble-Sort algorithm performs when
sorting σ to obtain the identity permutation. The Cayley
distance goes back to [32] and the Kendall distance to [33].
PT −1
Theorem 2. Let Ktrans (Σ) =
t=1 kCayley (Σ(t + 1) ◦
Σ(t)−1 ). Ktrans is a permutation measure.
PT −1
Theorem 3. Let Kadjtrans (Σ) = t=1 kKendall (Σ(t + 1) ◦
Σ(t)−1 ). Kadjtrans satisfies Definition 5.
The proof of Theorems 1, 2 and 3 is in Appendix B.
Although many intuitive choices for K satisfy properties
(i), (ii) and (iii) of Definition 5, some natural ones do not.
For example, given a β ≥ 1 we might want to define
Kmaxcount as Kmaxcount (Σ) = Kcount (Σ) if Kcount (Σ) ≤ β
and Kmaxcount (Σ) = ∞ if Kcount (Σ) > β (we can replace
∞ by some very large number if we want to be technical
about the range of K being R+
0 ). This K forces us not to
create an association between A and B more intricate than a
certain amount β, something natural to desire. The following
is proved in Appendix B.
Theorem 4. Kmaxcount does not satisfy (iii) in Definition 5.
Thus, it is not a permutation measure.
We now state our first main result.
Theorem 5. If K is a permutation measure and d is a metric,
then the map Dnat induced by them is a metric on S.
Even if a function K violates some of the properties in
Definition 5, it could still induce a Dnat that is a metric.
However, we often find that, from a set of associations Σ
and Σ0 that violate Definition 5, we can build three sets of
trajectories A, B and C that violate some of the properties
required of a metric. This is the case, for example, for Dnat
induced by Kmaxcount and d equal to the Euclidean metric.

7

Theorem 6. The map Dnat , induced by K = Kmaxcount and
the Euclidean distance d, is not a metric.
The proof of this theorem is in Appendix B. In this sense,
Definition 5 is required for Dnat to be a family of metrics.
We now focus on Dcomp .
Definition 6. A matrix norm k.k is a switching norm if for
any four matrices w1 , w2 , w10 , w20 ∈ P
kw20 w2 − w10 w1 k ≤ kw20 − w10 k + kw2 − w1 k.

(7)

The following Lemma gives sufficient conditions for a
metric k.k to satisfy property (7). See Appendix C for the
proof.
Lema 3. If k.k is a sub-multiplicative norm and kW k ≤ 1
for all W ∈ P then k.k is a switching norm.
This lemma implies, for example, that the 1-norm, ∞-norm
and spectral norm for matrices are valid choices for k.k.
We now state our second most important result.
Theorem 7. If k.k is a switching norm and d is a metric then
the map Dcomp induced by k.k and d is a metric on S.
The proof of this theorem is in Appendix C.
The use of k.k1 (matrix norm) in Dcomp is extremely useful
because it induces the changes of association to be sparse and,
as the next theorem shows, reduces Dcomp to solving a linear
program. Recall that all LPs can be solved in polynomial time
[34]. The theorem’s proof is in Appendix C.
Theorem 8. For any A, B ∈ S, the metric Dcomp (A, B)
induced by the matrix 1-norm and any d can be computed
(in polynomial time) by solving a linear program.
This LP can be a made sparse if we impose that for every
(i, j, t) such that Ai (t) and Bj (t) are distant we must have
Wij (t) = 0, i.e. we cannot associate distant points. Sparsity
allows us to reduce the effective number of optimization
variables in (2) and speedup computations further.
To end this section, let us explicitly include a scaling factor
α > 0 in the definition of Dcomp . To be specific,
Dcomp (A, B) = min

W ∈P T

α × swi(W ) + dist(W, A, B), (8)

where, changing the definition of (5) and (6) in Section VI,
swi(W ) =
dist(W, A, B) =

T
−1
X
t=1
T
X

kW (t + 1) − W (t)k and
tr(W (t)† DAB (t)).

(9)

(10)

t=1

If we compute Dcomp for different α’s we obtain different
pairs of values dist and swi. We can obtain more pairs of
values if we compute dist and swi using as W the permutation
matrices representing the association produced by the CLEAR
MOT or OSPA-ST. Even using MOTP alone, we can compute
different values for swi and dist by changing thrM OT .
If we fix A and B, we can display all these different pairs
on a 2D scatter plot where each point is a pair (dist, swi)
evaluated on a different W ∈ P T . Using such a scatter plot

is a great way to assess the performance of a tracker B on
ground-truth A under different similarity measures or when
we do not know which α or thrM OT to use to compute
Dcomp and DM OT P . For a fixed A and B, a good measure D
generates pairs closer to the origin. A very good measure D
generates pairs only on the Pareto frontier of this scatter plot.
Not surprisingly, the pairs (dist, swi) that Dcomp produces for
different values of α generate this Pareto frontier. This follows
from a well-known result in convex optimization theory that
we state in Theorem 9 (see [35] for a proof). In this context,
Dcomp is the best metric we can hope. In particular, none of the
examples where MOTP or OSPA-ST produce counter-intuitive
results, like the counter example behind the proof of Lemma
1, lead to Dcomp giving counter-intuitive results. The reader
unfamiliar with convex optimization can jump to Section VIII.
Let Ω be a convex set, e.g. P T , and let f and g be two
convex functions in Ω, e.g. swi(.) and dist(., A, B). Let R =
{(s, t) ∈ R2 : s ≥ f (x) and t ≥ g(x), x ∈ Ω}. This set could
be, for example, the points in our scatter plot plus points with
worse costs. Let ∂R be the boundary of R. Since R is convex,
∂R is its Pareto frontier. For instance, ∂R could be the Pareto
frontier we discussed above. Let p(α) ∈ R2 be the curve of
(f, g) pairs generated by solving minx∈Ω f (x) + αg(x) for
different values of α > 0. This could be a tradeoff curve of
(swi, dist) pairs generated by Dcomp for different α’s.
Theorem 9. If (s, t) ∈ ∂R then either (s, t) = p(α0 ) for some
α0 > 0 or (s, t) is a convex combination of p(α0 ) and p(α1 )
for some α0 , α1 > 0.
VIII. N UMERICAL RESULTS : Dcomp COMPUTATION TIME

In practice, there are many ways to compute Dcomp , like
when solving a convex optimization problem. To illustrate how
easy it is to get code working, we have a simple Matlab code
for Dcomp in www.jbento.info/papers/metriccompanion.pdf. In
the same document, we also have a simple Matlab code
to estimate Dnat . However, to explore the limits of practical performance, we coded a non-trivial solver in C using
parADM M , an implementation of the Alternating Direction
Method of Multipliers (ADMM) that is available at github.
com/parADMM/engine. parADM M has good performance
in practice [36]. The ADMM is known to scale well, and its
modular nature makes it easy to research future variants of
Dcomp without having to re-write much code. [37] is a good
introduction to the ADMM and its applications.
In Figure 3 we plot run-time in computing Dcomp against
the total duration T of the input data for a different number of
free association variables per time instant t. We use the term
“free association variables” because, as explained after Thm.
8, a few variables Wij (t) can be set to zero to sparsify the
problem and save computation time. We choose the euclidean
distance for d and the one-norm for matrix norm k.k in the
switching cost. Similar run-times hold for other metrics. The
run-time is computed for randomly generated A and B on a
single core of a 1.4GHz Intel Core i5 MacBook Air. ADMM
always converged to 1% accuracy in less than 150 iterations.
To interpret the plots, imagine we want to evaluate the
quality of a tracker when tracking 22 objects. Imagine that

8

the tracker operates at 30 frames per second and also that our
tracker is noisy so that it produces a few false tracks that create
approximately 10 extra points per instant. To compute Dcomp ,
and after we extend the ground-truth and hypothesis sets from
A and B to A+ and B + , we are dealing with distance matrices
DAB (t) with about ((22 + 10) × 2)2 = 4096 variables per
instant t. Using Fig. 3 we see that it take us about 40 seconds
to evaluate the accuracy of 800/30 = 26.6 seconds of data.
If we reduce the number of free variables per frame to half,
AB
e.g. by setting Wij (t) = 0 if Dij
(t) is larger than a given
threshold, then we can reduce the time to process 26.6 secs.
of data to about 20 secs.

trackers T racker09 and T racker11 respectively. The data set
is part of the Multiple Object Tracking Benchmark [40] and
is widely used in computer vision. It comes from a pedestrian
street filmed from an elevated point for 3 minutes and 45
seconds and can be downloaded from [41]. In Figure 4-(b) we
show the performance of the trackers in [42] and [43] on the
PETS2009 data set, also part of the Multiple Object Tracking
Benchmark. We call these trackers T racker12 and T racker15
respectively. Its duration is 1 minute and 54 seconds, and it can
be downloaded from [?]. More exact knowledge of these data
sets and trackers is outside the scope of this paper. The point
we want to make is in regard to comparing similarity measures.
Not about comparing trackers’ performance on different data
sets. We produced all the plots using the exact same output
that each tracker produced in its respective paper, thanks to
the authors who provided us with their trackers’ output. When
coding d+ , we set M = 20 for AVG-TownCenter and M = 50
for PETS2009.

IX. N UMERICAL RESULTS : O PTIMAL TRADEOFF CURVES

A. Real trackers and real data

(a)

(b)

3500

300

3000

Tracker15
MOTP

Tracker11
MOTP

2500
2000

Tracker09
MOTP

Switch cost

250

Switch cost

To the best of our knowledge, Dcomp is the first measure
that is a metric, can be computed in polynomial time and, in
addition, deals with the tradeoff between distance cost and
switching cost optimally. In this sense, Dcomp (and future
variants) is the best metric we can hope for (cf. Section VII).
To illustrate this optimal tradeoff, we build and compare
tradeoff curves obtained from Dcomp and MOTP. A tradeoff
curve is a set of points (swi, dist) where swi and dist
are computed using (9) and (10). For Dcomp , we obtain the
different points along the curve by changing α > 0 in (8). For
MOTP we generate the tradeoff curve by changing thrM OT .
We do this for both synthetic and real data. We use the
Euclidean metric for d+ and the component-wise 1-norm for
the matrix norm k.k.
The direct interpretation of our results is that Dcomp is
better than MOTP. However, the important underlying fact is
that Dcomp builds better associations than (i) the heuristics
widely used in the literature, e.g. the CLEAR MOT, and
(ii) the optimal associations before our work that do not
allow switches, e.g. OSPA-ST. Therefore, although we restrict
the comparison to MOTP, we can show similar improvement
over many measures that first establish a heuristic association
between A and B. For example, Multiple Object Tracking
Accuracy (MOTA), False Alarms per Frame, Ratio of Mostly
Tracked trajectories, Ratio of Mostly Lost trajectories, the
number of False Positives, number of False Negatives, number
of ID Switches, the number of tracks Fragmentation and many
of the measures listed in [7] and [9].

200
150

1500

100

1000

Tracker11
Dcomp

500

Tracker09
Dcomp

50
0

0
3

3.05

3.1

3.15

Distance cost

3.2

3.25
4
x 10

2

Tracker12
MOTP

Tracker15
Dcomp

Tracker12
Dcomp
2.5

3

3.5

Distance cost

4
4
x 10

Fig. 4. (a) Tradeoff plot for T racker09 and T racker11 on the AVGTownCenter data set; and (b) tradeoff plot for T racker12 and T racker15
on the PETS2009 data set. Smaller values (in either axis) is better.

As expected, the tradeoff curves from MOTP understate
the performance of the trackers: all trackers are achieving
a substantially smaller number of switches without incurring
larger distance costs than what MOTP reports. Interestingly,
for these trackers and data sets, Dcomp keeps the same relative
ordering of performance as MOTP. It is conceivable that there
are situations in which a tracker 1 is better than a tracker 2
according to MOTP but not according to Dcomp . It would be
interesting to find such examples in future work.
B. Random ensemble of trajectories

Run-time (secs)

Above, A and B are relatively close to each other because
all
the trackers are good trackers. In this section, we aim
In Figure 4-(a) we show the performance of the trackers in
to
study
A and B that are more different. Hence, we use
[38] and [39] on the AVG-TownCentre data set. We call these
synthetic data to control the distance between A and B. We
(a)
(b)
randomly generate A with 25 trajectories and make B a
120
# free vars. per instant
Max. trajectory length, T
distorted version of the trajectories in A. The trajectories in
120
2.5 × 103
50
100
3
A have random start and end times and the objects in each
3.6 × 10
250
100
trajectory randomly change their velocity’s direction along
4.9 × 103
450
80
80
6.4 × 103
650
the way. The trajectories in B are generated by randomly (i)
60
60
8.1 × 103
850
fragmenting the trajectories in A, (ii) removing some of the
10 × 103
40
40
resulting trajectories, (iii) adding noise to all trajectories and
20
20
(iv) flipping or not the ID of two trajectories if they pass by
0
each other close enough. In the end, B might have more or less
0
2
4
6
8
10
0
200
400
600
800
1000
3
Max. trajectory length, T
# free vars. per instant (×10 ) than 25 trajectories. In total, we have four knobs to increase
Fig. 3. Time to compute Dcomp (within 1% accuracy) as a function of (a) the or reduce the distance between A and B. These knobs are,
length of trajectories; and (b) the number of association variables per instant.

9

(i) the amplitude of noise, AM P noise; (ii) the probability of
fragmenting a track at each point in time, F RAGprob; (iii)
the probability of deleting a points in the track, DELprob;
and (iv) the threshold distance after which we allow to tracks
ID to be switched or not randomly, SW Idist.
Here, trajectories are far more diverse and complex than
those in Section IX-A and in most publicly available real
data sets. Real objects, like people, have relatively simple
trajectories. In addition, we do not just test two data sets,
like in Section IX-A. We generate data for about 20 different
configurations for each of the four knobs described above and
for each of these configurations we generate 30 random sets A
and B. Hence, and in the context of computer vision tracking,
it is as if we test 2400 different data sets of ground-truth and
output trajectories.
We study the similarity between A and B using tradeoff
plots with distance cost on the y-axis and switching cost on
the x-axis. The smaller the area under the curve (AUC), the
closer A and B are. In Fig. 5 we show the average AUC for A
and B under different knob settings. Each AUC is normalized
by the largest AUC possible. The largest AUC is the product
of the largest distance cost possible with the largest switching
cost possible. Each point in the plots is an average over 30
random pairs A and B with the same knobs’ setting. In each
plot we keep all but one knob constant.
(a)

(b)

0.4

0.18
0.16

MOTP

0.35

MOTP

tackers as above. If we interpret A and B as the ground-truth
and output of a tracker respectively, MOTP almost always says
that the tracker is worse than what it really is. Dcomp can see
similarities between A and B that MOTP cannot.
X. C ONCLUSION
The problem of defining a similarity measure for sets of
trajectories is crucial for computer vision, machine learning,
and general AI. An essential aspect of this problem is finding
a meaningful association between the elements of the sets.
Existing measures that define useful associations fail to be a
metric mathematically speaking, e.g., the CLEAR MOT. The
ones that are a metric, only consider restrictive associations,
i.e. associations that cannot change in time, e.g. OSPAbased metrics. Dcomp is the first that simultaneously (1) is a
metric, (2) allows time-dependent associations and hence can
associate parts of trajectories to parts of trajectories, (3) allows
controlling the complexity of this association in a globally
optimal way and (4) has polynomial computation time.
The general idea of defining mathematical metrics for
sets of trajectories using convex programs is our greatest
overarching contribution. We are currently exploring variants
of our metric that allow incorporating uncertainty, as well
as richer comparisons between A and B without losing its
useful properties. We are also exploring the use of this metric
in a machine learning application for fast classification and
retrieval of human actions/activities. We will present these
extensions in future work.

0.14

0.3

R EFERENCES

0.12

Dcomp

0.2

0.1

AUC

AUC

0.25

Dcomp

0.08

0.15

0.06
0.1

0.04

0.05

0.02

0
0

5

10

15

20

25

0
0

30

0.05

0.1

AM P noise

0.15

0.2

0.25

0.3

0.35

DELprob

(c)

(d)
0.18

0.16

0.16

MOTP

0.14

0.14

0.12

MOTP

0.12

Dcomp

0.08
0.06

AUC

AUC

0.1
0.1

0.08

Dcomp

0.06

0.04

0.04

0.02

0

0.02

0.05

0.1

0.15

0.2

0.25

F RAGprob

0.3

0.35

0
0

2

4

6

8

10

SW Idist

Fig. 5. AUC (normalized) versus (a) noise amplitude; (b) point deletion
probability; (c) fragmenting probability; and (d) switching distance. Smaller
AUC is better.

As expected from Theorem 9, the AUC of Dcomp is smaller
than the AUC of MOTP. Note that it is incorrect to interpret
these results as saying that MOTP is a scaled version of
Dcomp . We are computing exactly the same quantities for both
measures: dist and swi according to (10) and (9). We just
use a different W for each measure. The curves of Figure 5
have a much deeper significance: they say that the conclusions
that hold for real data hold in great generality, now in 2400
different tests and not just for two real data sets and four

[1] D. Schuhmacher, B.-T. Vo, and B.-N. Vo, “A consistent metric for
performance evaluation of multi-object filters,” Signal Processing, IEEE
Trans. on, vol. 56, no. 8, pp. 3447–3457, 2008.
[2] B. Keni and S. Rainer, “Evaluating multiple object tracking performance:
the clear mot metrics,” EURASIP Journal on Image and Video Processing, vol. 2008, 2008.
[3] V. Ganti, R. Ramakrishnan, J. Gehrke, A. Powell, and J. French, “Clustering large datasets in arbitrary metric spaces,” in Data Engineering,
1999. Proceedings., 15th Intern. Conf. on. IEEE, 1999, pp. 502–511.
[4] J. Kleinberg and E. Tardos, “Approximation algorithms for classification problems with pairwise relationships: Metric labeling and markov
random fields,” Journal of the ACM (JACM), vol. 49, 2002.
[5] P. N. Yianilos, “Data structures and algorithms for nearest neighbor
search in general metric spaces,” in Proceedings of the fourth annual
ACM-SIAM Symposium on Discrete algorithms. Society for Industrial
and Applied Mathematics, 1993, pp. 311–321.
[6] S. S. Blackman, “Multiple-target tracking with radar applications,”
Dedham, MA, Artech House, Inc., 1986, 463 p., vol. 1, 1986.
[7] R. L. Rothrock and O. E. Drummond, “Performance metrics for
multiple-sensor multiple-target tracking,” in AeroSense 2000. Intern.
Society for Optics and Photonics, 2000, pp. 521–531.
[8] Y. Bar-Shalom, X. R. Li, and T. Kirubarajan, Estimation with applications to tracking and navigation: theory algorithms and software. John
Wiley & Sons, 2004.
[9] A. A. Gorji, R. Tharmarasa, and T. Kirubarajan, “Performance measures
for multiple target tracking problems,” in Information Fusion (FUSION),
2011 Proceedings of the 14th Intern. Conf. on. IEEE, 2011, pp. 1–8.
[10] B. Ristic, B.-N. Vo, D. Clark, and B.-T. Vo, “A metric for performance
evaluation of multi-target tracking algorithms,” Signal Processing, IEEE
Trans. on, vol. 59, no. 7, pp. 3452–3457, 2011.
[11] I. CVX Research, “CVX: Matlab software for disciplined convex
programming, version 2.0,” http://cvxr.com/cvx, Aug. 2012.
[12] H. W. Kuhn, “The hungarian method for the assignment problem,” Naval
Research Logistics Quarterly, vol. 2, no. 1-2, pp. 83–97, 1955.
[13] M. M. Deza and E. Deza, Encyclopedia of distances. Springer, 2009.
[14] O. Fujita, “Metrics based on average distance between sets,” Japan
Journal of Industrial and Applied Mathematics, vol. 30, 2013.

10

[15] A. Gardner, J. Kanno, C. A. Duncan, and R. Selmic, “Measuring distance
between unordered sets of different sizes,” in Computer Vision and
Pattern Recognition (CVPR), 2014 IEEE Conf. on. IEEE, 2014.
[16] J. R. Hoffman and R. P. Mahler, “Multitarget miss distance via optimal
assignment,” Systems, Man and Cybernetics, Part A: Systems and
Humans, IEEE Trans. on, vol. 34, no. 3, pp. 327–336, 2004.
[17] T. Vu and R. Evans, “A new performance metric for multiple target
tracking based on optimal subpattern assignment,” in Information Fusion
(FUSION), 2014 17th Intern. Conf. on. IEEE, 2014, pp. 1–8.
[18] H. Xiaofan, R. Tharmarasa, T. Kirubarajan, and T. Thayaparan, “A track
quality based metric for evaluating performance of multitarget filters,”
Aerospace and Electronic Systems, IEEE Trans. on, vol. 49, 2013.
[19] S. Nagappa, D. E. Clark, and R. Mahler, “Incorporating track uncertainty into the ospa metric,” in Information Fusion (FUSION), 2011
Proceedings of the 14th Intern. Conf. on. IEEE, 2011, pp. 1–8.
[20] T. Ellis, “Performance metrics and methods for tracking in surveillance,”
in Proceedings of the 3rd IEEE Intern. Workshop on Performance
Evaluation of Tracking and Surveillance (PETS02). Citeseer, 2002.
[21] A. Milan, K. Schindler, and S. Roth, “Challenges of ground truth
evaluation of multi-target tracking,” in Computer Vision and Pattern
Recognition Workshops (CVPRW), 2013 IEEE Conf. on. IEEE, 2013.
[22] B. E. Fridling and O. E. Drummond, “Performance evaluation methods
for multiple-target-tracking algorithms,” in Orlando’91, Orlando, FL.
Intern. Society for Optics and Photonics, 1991, pp. 371–383.
[23] O. E. Drummond and B. E. Fridling, “Ambiguities in evaluating performance of multiple target tracking algorithms,” in Aerospace Sensing.
Intern. Society for Optics and Photonics, 1992, pp. 326–337.
[24] O. E. Drummond, “Multiple-object estimation,” 1975.
[25] S. B. Colegrove, L. Davis, and S. J. Davey, “Performance assessment
of tracking systems,” in Signal Processing and Its Applications, 1996.
ISSPA 96., Fourth Intern. Symposium on. IEEE, 1996.
[26] F. Yin, D. Makris, and S. A. Velastin, “Performance evaluation of object
tracking algorithms,” in 10th IEEE Intern. Workshop on Performance
Evaluation of Tracking and Surveillance (PETS2007), 2007.
[27] F. Bashir and F. Porikli, “Performance evaluation of object detection and
tracking systems,” in IEEE Intern. Workshop on Performance Evaluation
of Tracking and Surveillance (PETS), vol. 5, 2006.
[28] O. E. Drummond, “Methodologies for performance evaluation of multitarget multisensor tracking,” in SPIE’s Intern. Symposium on Optical
Science, Engineering, and Instrumentation. Intern. Society for Optics
and Photonics, 1999, pp. 355–369.
[29] S. Pingali and J. Segen, “Performance evaluation of people tracking
systems,” in Applications of Computer Vision, 1996. WACV’96., Proceedings 3rd IEEE Workshop on. IEEE, 1996, pp. 33–38.
[30] K. K. Edward, P. D. Matthew, and B. H. Michael, “An information
theoretic approach for tracker performance evaluation,” in Computer
Vision, 2009 IEEE 12th Intern. Conf. on. IEEE, 2009, pp. 1523–1529.
[31] F. Porikli, “Trajectory distance metric using hidden markov model based
representation,” in IEEE European Conf. on Computer Vision, PETS
Workshop, vol. 3, 2004.
[32] A. Cayley, “Lxxvii. note on the theory of permutations,” The London,
Edinburgh, and Dublin Philosophical Magazine and Journal of Science,
vol. 34, no. 232, pp. 527–529, 1849.
[33] M. G. Kendall, “A new measure of rank correlation,” Biometrika, pp.
81–93, 1938.
[34] L. Khachiian, “Polynomial algorithm in linear programming,” in
Akademiia Nauk SSSR, Doklady, vol. 244, 1979, pp. 1093–1096.
[35] S. Boyd and L. Vandenberghe, Convex optimization.
Cambridge
university press, 2004.
[36] N. Hao, A. Oghbaee, M. Rostami, N. Derbinsky, and J. Bento, “Testing
fine-grained parallelism for the admm on a factor-graph,” arXiv preprint
arXiv:1603.02526, 2016.
[37] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, “Distributed
optimization and statistical learning via the alternating direction method
of multipliers,” Foundations and Trends® in Machine Learning, vol. 3,
no. 1, pp. 1–122, 2011.
[38] B. Benfold and I. Reid, “Guiding visual surveillance by tracking human
attention.” in BMVC, 2009, pp. 1–11.
[39] ——, “Stable multi-target tracking in real-time surveillance video,” in
Computer Vision and Pattern Recognition (CVPR), 2011 IEEE Conf. on.
IEEE, 2011, pp. 3457–3464.
[40] “Multiple object tracking benchmark,” http://www.motchallenge.net, accessed: 2015-03-01.
[41] “Coarse gaze estimation in visual surveillance,” http://www.robots.ox.
ac.uk/ActiveVision/Research/Projects/2009bbenfold headpose/project.
html#datasets, accessed: 2015-03-01.

[42] B. Yang and R. Nevatia, “Multi-target tracking by online learning of
non-linear motion patterns and robust appearance models,” in Computer
Vision and Pattern Recognition (CVPR), 2012 IEEE Conf. on. IEEE,
2012, pp. 1918–1925.
[43] F. Poiesi and A. Cavallaro, “Tracking multiple high-density homogeneous targets,” Circuits and Systems for Video Technology, IEEE Trans.
on, vol. 25, no. 4, pp. 623–637, 2015.
[44] “Pets2009 benchmark data set,” http://www.cvg.reading.ac.uk/
PETS2009/a.html, accessed: 2015-03-01.

A PPENDIX A
T HEORY ON THE LIMITATIONS OF THE CLEAR MOT
Let us formally describe the heuristic used by the CLEAR
MOT.
Definition 7. The CLEAR MOT matching heuristic defines
ΣMOT sequentially as follows.
P
+
1) Initialize ΣMOT (1) such that i d+ (A+
i (1), BΣMOTi (1) (1))
is minimal;
2) For each t > 1 do: for all i, j ∈ {1, ..., m} such that
+
ΣMOTi (t − 1) = j and d+ (A+
i (t), Bj (t)) < thrM OT
fix ΣMOTi (t) = j. We call such matches as anchored.
Set
non-fixed components of ΣMOT (t) such that
P the
+
+
+
d
(A
i (t), BΣMOT (t) (t)) is minimal.
i
i

Proof of Lemma 1. We construct a validating example for any
1 < thrM OT < 2, with A = {A1 , A2 } and B = {B1 , B2 },
i.e. m = 2, and where Ai and Bi are 1D trajectories. We
generalize this example to any thrM OT and m at the end.
Consider the two sets of one-dimensional trajectories A =
{A1 , A2 } and B = {B1 , B2 } defined in Figure 6. Time is on
the x-axis (left to right) and space on the y-axis (bottom to
top). T1 and T2 are fixed. T3 grows with T .
B1
A2

3

A1
C1

1
B2
T1

T2

T

T3

C2

Fig. 6. Example that shows that (a) the CLEAR MOT heuristic is bad and (b)
MOTP is not a metric. For visualization purposes, trajectories that are close
are actually on top of each other.

Since we assume 1 < thrM OT < 2, the CLEAR MOT
builds an association sequence ΣMOT that initially matches A1
to B1 but some time after T1 matches A1 to B2 to minimize
the distance between matched points. After T1 + T2 , this last
association is anchored given that 1 < thrM OT . Hence,
ΣMOT = {(1, 2), ..., (1, 2), (2, 1), (2, 1), ...}.
The number of times that ΣMOT (t) 6= ΣMOT (t + 1) is 1,
1
thus
P swi(ΣMOT ) = T −1 = O(1/T ). For t after T1 + T2 ,
i kAi (t) − BΣMOTi (t) (t)k = 2. Thus dist(ΣMOT , A, B) >
2(T −T1 −T2 )
= 2 − O(1/T ). However, if we choose Σ =
T

11

{(1, 2), ..., (1, 2)}, we have swi(Σ) = 0 and dist(Σ, A, B) <
T2 ×4
= O(1/T ). The result of the lemma follows.
T
To see that the proof holds for any m, we extend A and B
as follows. Without loss of generality, we assume m is even.
If the 1D trajectory Ai above is equal to (Ai (1), ..., Ai (T )),
(k)
define the 2D trajectory Ai such that
(k)

Ai (t) = [Ai (t); Ck] ∈ R2 ,
where C is a constant large enough such that trajectories for
different k’s are not close to each other under the d+ measure.
(k)
We define Bi similarly. Define
(0)

(0)

(1)

(1)

(m−1)

A = {A1 , A2 , A1 , A2 , ..., A1

(m−1)

, A2

},

and similarly B. In this setting, the bounds previously computed on swi(ΣMOT ) and swi(Σ) change by a factor of m,
while the bounds on dist(ΣMOT , A, B) and dist(Σ, A, B)
change by a factor of m/2. Thus the statement of the lemma
still holds.
To extend the proof for an odd m, append to A and B
two equal trajectories far away from all other trajectories such
that they are matched to each other. They do not contribute to
either swi or dist.
Finally, to see that the proof also holds for any thrM OT ,
we rescale space-axis in Figure 6. This changes the bounds
on dist by a factor of thrM OT and leaves the bounds on swi
unchanged, thus obtains the result.
Proof of lemma 2. We construct A, B, C ∈ S for which
the triangle inequality is violated. Specifically, D(A, B) >
D(A, C) + D(C, B).
Without loss of generality, we assume 1 < thrM OT < 2.
To see that the result holds for all thr > 0, we employ the
space-rescaling trick in the proof of Lemma 1.
Consider the sets A = {A1 , A2 }, B = {B1 , B2 } and C =
{C1 , C2 } as in Fig. 6, where the trajectories extend to some
large T . T1 and T2 are fixed. T3 grows with T . To make
calculations simpler, we work with D divided by T in Def. 3.
Let us compute D(A, B) first. The association ΣMOT for this
distance is {(1, 2), .., (1, 2), (2, 1), ...} because (i) we start with
the association {A1 ↔ B1 , A2 ↔ B2 }, (ii) at some point after
T1 we need to change the association to {A1 ↔ B2 , A2 ↔
B1 } because the initial association exceeds thrM OT P < 2
and (iii) for times after the T1 + T2 the association {A1 ↔
B2 , A2 ↔ B1 } is anchored because thrM OT > 1. Therefore,
D(A, B) > 2(T T−T2 ) .
Now we compute D(A, C). The association for D(A, C)
is ΣMOT = {(1, 2), ..., (1, 2)} because (i) we start with
{A1 ↔ C1 , A2 ↔ C2 }, (ii) the association A1 ↔ C1 is
always anchored because the distance between A1 and C1
is always zero and thus always smaller than thrM OT > 1
and (iii) after some point, when the distance between A2 and
C2 exceeds thrM OT < 2, MOTP still keeps the association
A2 ↔ C2 because A1 and C1 are already anchored. Under this
2
association, numerical computation leads to D(A, C) < 4T
T .
4T2
Similarly, D(C, B) < T .
Therefore, for T large enough we have D(A, B) >
2(T −T2 )
4T2
2
> 4T
T
T + T > D(A, C) + D(C, B).

A PPENDIX B
P ROPERTIES OF OUR METRICS : Dnat

To prove Theorem 5, we need the following lemma.
Lema 4. The map d+ is a metric on Rp ∪ {∗}.

Proof. We verify that d+ satisfies the four conditions of a
metric. Let x00 , x0 , x ∈ Rp ∪ {∗}.
Non-negativity and symmetry are obvious.
To verify the coincidence property, observe that d+ (x, x0 ) =
0 implies either x = x0 = ∗ or, since M > 0, d+ (x, x0 ) =
d(x, x0 ) = 0. Because d is a metric, this in turn implies that
x = x0 = 0. In other words, d+ (x, x0 ) = 0 ⇔ x = x0 .
To verify the subadditivity property, we need to consider
eight different cases of the triangle inequality. We first consider
the non-trivial cases. If x, x0 , x00 ∈ Rp , then
d+ (x, x00 ) = min{2M, d(x, x00 )}
≤ min{2M, d(x, x0 ) + d(x0 , x00 )}

≤ min{2M, d(x, x0 )} + min{2M, d(x0 , x00 )}
= d+ (x, x0 ) + d+ (x0 , x00 ).

If x0 =∗ and x, x00 ∈ Rp , then M =d+ (x0 , x00 )=d+ (x, x0 ) and
d+ (x, x00 ) = min{2M, d(x, x00 )} ≤ d+ (x, x0 ) + d+ (x0 , x00 ).
It is easy to check the other six cases.
Proof of Theorem 5. Let A, B, C be three elements in S. We
verify the four conditions of a metric for Dnat .
Coincidence property: We show that Dnat (A, B) = 0 if
and only if A = B. Recall that A and B are unordered
sets of trajectories. Hence A = B implies that there is an
isomorphism between A and B. In other words, they are equal
apart from a relabeling of the elements. If A = B and we
set Σ = (σ, σ, ..., σ) then the function to minimize on the
right-hand-side of equation (1) is equal to zero. This σ is an
isomorphism between A and B. Since the minimum of (1)
must always be non-negative, we conclude that A = B ⇒
Dnat (A, B) = 0. Conversely, assume that Dnat (A, B) = 0
and let Σ∗ = (Σ∗ (1), ..., Σ∗ (T )) be a minimizer in (1).
Dnat (A, B) = 0 implies that K(Σ∗ ) = 0. Therefore Σ∗i (t) =
Σ∗i (1), for all t and i. Since the labeling of the trajectories
does not affect the computation of Dnat , we assume without
loss of generality that their labeling is such that we can write
Σ∗i (t) = i. Dnat (A, B) = 0 also implies that, for all t and
+
+
i, we have d+ (A+
(t)) = d+ (A+
i (t), BΣ∗
i (t), Bi (t)) = 0.
i (t)
+
Since d+ is a metric, this in turn implies that A+
i (t) = Bi (t)
+
for all i and t, which is the same as saying that A = B + .
Hence A = B. To be more specific, A is equal to B apart
from a relabeling of its trajectories.
Symmetry property: Since Dnat only depends on A and B
through d+ we have Dnat (A, B) = Dnat (B, A).
Subadditivity property: We prove Dnat (A, C)
≤
Dnat (A, B) + Dnat (B, C). First, notice that we can
add any extra number of ∗-only trajectories to A, B or
C without changing Dnat . Recall that m is number of
trajectories in A+ , B + and C + . In this part of the proof,
m should be the sum of the cardinalities of the two sets of
highest cardinality among A, B and C. In Section III, m

12

was just the sum of the cardinalities of A and B. T is the
maximum time index observed in A, B and C.
Since d+ is a metric, we can write that
d

+

+
(A+
i (t), CΣi (t) (t))
+

+d

+
(BΣ
0
Σ

i

+

≤d

+
(A+
i (t), BΣ0Σ

i (t)

(t) (t))

+
(t) (t), CΣi (t) (t))
(t)

(11)

for any Σ0 = (Σ0 (1), ..., Σ0 (T )) ∈ ΠT and for all i and t. Now
notice that
m
m
X
X
+
+
+
+
d+ (BΣ
(t),
C
(t))
=
d+ (BΣ
0
0 (t) (t), Ci (t)).
(t)
Σi (t)
i

Σi (t)

i=1

i=1

Using this together with (11), we can write
T X
m
X
t=1 i=1
T X
m
X

+
d+ (A+
i (t), CΣi (t) (t)) ≤

Since the left-hand-side is at most 1, we only need to consider
the case in which the right-hand-side is less than 1, i.e.,
I(Σ(t + 1) ◦ Σ(t)−1 6= I) + I(Σ0 (t + 1) ◦ Σ0 (t)−1 6= I) = 0.
In this case, it follows that Σ(t + 1) = Σ(t) and Σ0 (t + 1) =
Σ0 (t). Consequently, the left-hand-side equals 0 as well in this
case. Hence the property is verified.
Proof of Theorem 2 and Theorem 3. We prove Theorem 2.
The proof for Kadjtrans is similar. The first two properties
of the permutation measure are immediate to check from the
definition of Ktrans . To prove the third property it suffices to
show that

kCayley (Σ0 (t + 1) ◦ Σ(t + 1)) ◦ (Σ0 (t) ◦ Σ(t))−1
≤ kCayley (Σ(t+1))◦Σ(t)−1 )+kCayley (Σ0 (t+1)◦Σ0 (t))−1 ).

To prove this we use of the following two facts.
Fact 1: if σ, σ 0 ∈ Π then kCayley (σ ◦ σ 0 ) ≤ kCayley (σ) +
t=1 i=1
kCayley (σ 0 ). To see why this is true, notice that this inequality
Let us define Σ00 = (Σ00 (1), ..., Σ00 (T )) ∈ ΠT where Σ00i (t) = can be rewritten as k
−1
) ≤ kCayley (a ◦ b−1 ) +
Cayley (a ◦ c
Σ0Σi (t) (t). This means Σ00 = Σ0 ◦ Σ. We can use Σ0 to rewrite k
−1
0
) where a = σ ◦ σ , b = σ 0 and c = I, the
Cayley (b ◦ c
the expression above as
identity permutation. Then, it is basically saying that shortest
T X
m
T X
m
X
X
set of transpositions that take σ1 to σ3 is smaller than any set
+
+
d+ (A+
d+ (A+
(t)) of transpositions that first take σ1 to σ2 and then σ2 to σ3 .
i (t), CΣi (t) (t)) ≤
i (t), BΣ00
(t)
i
t=1 i=1
t=1 i=1
Fact 2: if σ, σ 0 ∈ Π then kCayley (σ ◦ σ 0 ◦ σ −1 ) =
m
T X
X
kCayley (σ 0 ). This is true because σ◦σ 0 ◦σ −1 is just a relabeling
+
+
d+ (BΣ
(12) of the permutation σ 0 and k
+
0 (t) (t), Ci (t)).
i
Cayley is invariant to relabeling.
t=1 i=1
Let
Using Definition 5, we can write
σA = Σ(t) ◦ Σ(t + 1)−1 ,
σB = Σ0 (t) ◦ Σ0 (t + 1)−1 ,
+
d+ (A+
i (t), BΣ0

Σi (t)

(t) (t))

+
+
+ d+ (BΣ
0 (t) (t), Ci (t)).
i

K(Σ) = K(Σ0−1 ◦ Σ0 ◦ Σ) ≤ K(Σ0−1 ) + K(Σ0 ◦ Σ)
= K(Σ0 ) + K(Σ00 ).

(13)

Now we add both
and (13) and
PT sides
Pm of + (12)
+
obtain
K(Σ) +
d
(A
(t),
CΣ+i (t) (t))
≤
i
t=1
i=1
P
P
T
m
+
+
00
+
0
K(Σ ) +
d (Ai (t), BΣ00 (t) (t)) + K(Σ ) +
i
PT Pm +t=1 + i=1
+
t=1
i=1 d (BΣ0i (t) (t), Ci (t)).
Finally, we find the minimum of both sides of the inequality
over all pairs of Σ and Σ0 . Recall the relationship Σ00 = Σ0 ◦
Σ and the fact that we can choose Σ0 independently of Σ.
Consequently,
min K(Σ) +

Σ∈ΠT

T X
m
X

+
d+ (A+
i (t), CΣi (t) (t))

t=1 i=1
T X
m
X
00
+

≤ min K(Σ ) +
Σ00 ∈ΠT

+ min K(Σ0 ) +
Σ0 ∈ΠT

+
d (A+
i (t), BΣ00 (t) (t))
i

t=1 i=1
T X
m
X

+
+
d+ (BΣ
0 (t) (t), Ci (t)).
i

t=1 i=1

Hence, Dnat (A, C) ≤ Dnat (A, B) + Dnat (B, C).
Proof of Theorem 1. The first two properties of the permutation measure are trivial to verify. To verify the third property,
it is sufficient to prove that

I (Σ0 (t + 1) ◦ Σ(t + 1)) ◦ (Σ0 (t) ◦ Σ(t))−1 6= I
≤ I(Σ(t + 1) ◦ Σ(t)−1 6= I) + I(Σ0 (t + 1) ◦ Σ0 (t)−1 6= I).

and σC = Σ0 (t) ◦ σA ◦ Σ0 (t)−1 .

Observe that the permutation σC ◦ σB satisfies

σC ◦ σB ◦ (Σ0 (t + 1) ◦ Σ(t + 1)) ◦ (Σ0 (t) ◦ Σ(t))−1 = I.
Finally, we can apply Fact 2 followed by Fact 1, and obtain
(dropping Cayley for clarity).

k (Σ0 (t + 1) ◦ Σ(t + 1)) ◦ (Σ0 (t) ◦ Σ(t))−1
−1
−1
−1
−1
−1
−1
= k(σB
◦ σC
) ≤ k(σB
) + k(σC
) = k(σB
) + k(σA
)

= k(Σ(t + 1) ◦ Σ(t)−1 ) + k(Σ0 (t + 1) ◦ Σ0 (t)−1 ).

Proof of Theorem 4. We give a counter example that violates
property (iii) for β = 1. It is also easy to come up with similar
counter examples that violate property (iii) for any value of
β ≥ 1. Let I = (1, 2) be the identity permutation and let
σ = (2, 1) be the permutation that swaps 1 and 2. Let Σ =
(I, σ, σ) and let Σ0 = (I, I, σ). We have Kmaxcount (Σ) =
1 and Kmaxcount (Σ0 ) = 1 but Kmaxcount (Σ0 ◦ Σ) = ∞ >
Kmaxcount (Σ0 ) + Kmaxcount (Σ).
Proof of Theorem 6. We provide a special case where the
triangle inequality is violated. Let A, B and C be three sets of
trajectories. We assume β = 1, but it is easy to change A, B
and C such that the proof holds for any β,2 . Let I = (1, 2) be
the identity permutation and let σ 0 = (2, 1) be the permutation
2 It is easy to see that we do not in fact need d to be the Euclidean distance
for the proof to hold.

13

that swaps 1 and 2. Let A = {A1 , A2 }, B = {B1 , B2 },
C = {C1 , C2 }, where
A1 = (2, −2, −2), B1 = (2, 2, 2),

A2 = (−2, 2, 2),

C1 = (2, 2, −2),

B2 = (−2, −2, −2), C2 = (−2, −2, 2).

Now consider equation (1) with K = Kmaxcount and β = 1.
The optimization problem for Dnat (A, B),
3 X
2
n
o
X
+
min K(Σ) +
d+ (A+
(t),
B
(t))
i
Σi (t)
Σ∈ΠT

t=1 i=1

0

0

has a minimum of 1 at Σ = (I, σ , σ ). We can see this
because K forces us to either do one switch only or no switch
at all. Doing no switch at all makes us incur a cost larger than
1 in the distance term. Similarly, the optimization problem for
Dnat (B, C) has a minimum of 1 at Σ = (I, I, σ 0 ). When we
solve the optimization problem for Dnat (A, C), we are only
allowed to perform one change in the association between
A and C, otherwise the term Kmaxcount makes us pay a
very large cost. With only one change in the association, we
incur a distance of 4 for t = 1 or t = 2 or t = 3. Hence,
Dnat (A, C) ≥ 4 > 1 + 1 = Dnat (A, B) + Dnat (B, C).
A PPENDIX C
P ROPERTIES OF OUR METRICS : Dcomp
Proof of Theorem 7. Let A, B and C be any elements of S.
Coincidence property: If Dcomp (A, B) = 0, then W (t) =
AB
W (1) for all t. Hence, Dij
(t) = 0 for all i, j such that
Wij (1) > 0. Recall that if Wij is a doubly stochastic matrix,
then there exists a permutation σ = (σ1 , . . . , σm ) ∈ Π, such
AB
that Wiσi > 0 for all i. Therefore, Diσ
(t) = 0 for all t and i.
i
In other words, A and B are identical apart from a relabeling
of their elements.
Symmetry property: Using the properties of trace, we have
†

tr(W (t)D
= tr(D

AB

AB

†

(t)) = tr((W (t)D

†

(t) W (t)) = tr(D

BA

AB

†

(t)) )

(t)W (t)) = tr(W (t)D

BA

(t)).

Minimizing with respect to {W (t)} is the same as minimizing with respect to {W (t)† }. Thus Dcomp (A, B) =
Dcomp (B, A).
Subadditivity property: We prove that Dcomp (A, C) ≤
Dcomp (A, B) + Dcomp (B, C).
First, notice that we can add any extra number of ∗-only
trajectories to A, B or C without changing Dcomp . Recall
that m is number of trajectories in A+ , B + and C + . In this
part of the proof, m should be the sum of the cardinalities
of the two sets of highest cardinality among A, B and C. In
Section III, m was just the sum of the cardinalities of A and
B. T is the maximum time index observed in A, B and C.
First note that, since d+ is a metric we have that
AB
BC
DAC (t)ij ≤ Dik
(t) + Dkj
(t) for any k. Let W1 =
T
(W1 (1), ..., W1 (T )) ∈ P and W2 = (W2 (1), ..., W2 (T )) ∈
P T . We multiply both sides of the previous inequality by
W1 (t)ik W2 (t)kj and sum over i, j, k to obtain
m
X
W1ik W2kj DAC ij ≤
i,j,k=1

m
X
i,j,k=1

AB
BC
+ W1ik W2kj Dkj
,
W1ik W2kj Dik

whereP
we omitted t in W and D.
PmSince W1 (t), W2 (t) ∈ P, we
m
have j=1 W2 (t)kj = 1 and i=1 W1 (t)ik = 1. To simplify
this expression, and again omitting t in W and D, we re-write
the previous inequality in matrix notation as

tr (W1 W2 )† DAC ≤ tr(W1 † DAB ) + tr(W2 † DBC ).
From our assumption on k.k (c.f. Property (7)), we have
kW1 (t+1)W2 (t+1)−W1 (t)W2 (t)k ≤ kW1 (t+1)−W1 (t)k
+ kW2 (t + 1) − W2 (t)k.

Adding the last two inequalities, summing over t and minimizing over W1 , W2 ∈ P T we have
min

T
−1
X

W1 ,W2 ∈P T

kW1 (t + 1)W2 (t + 1)

t=1

− W1 (t)W2 (t)k +

T
X



tr (W1 (t)W2 (t))† DAC (t)

t=1

≤ min

W1 ∈P T

+ min

W2 ∈P T

T
−1
X

kW1 (t + 1) − W1 (t)k +

T
X

t=1

t=1

T
−1
X

T
X

kW2 (t + 1) − W2 (t)k +

t=1

tr(W1 (t)† DAB (t))
tr(W2 (t)† DBC (t)).

t=1

Note that for any W1 (t), W2 (t) ∈ P, we have W1 (t)W2 (t) ∈
P. Therefore, in the minimization performed on the left hand
side, we can replace W1 (t)W2 (t) by a single W (t). The
subadditivity property follows.
Proof of Lemma 3. Let w1 , w2 , w10 , w20 ∈ P, whose norms are
less than 1.
kw20 w2 − w10 w1 k ≤ kw20 (w2 − w1 + w1 ) − w10 w1 k

≤ kw20 (w2 − w1 )k + kw20 w1 − w10 w1 k ≤ kw20 kk(w2 − w1 )k
+ k(w20 − w10 )kkw1 k ≤ k(w2 − w1 )k + k(w20 − w10 )k.

The third inequality above is obtained using sub-multiplicity.
Proof of Theorem 8. The constraints which define P are a
set of linear constraints. In addition, the first term in the
objective is a linear function
PT −1of {W (t)}. Notice also that
we can replace the term
t=1 kW (t + 1) − W (t)k in the
PT −1
e
,
if
we
add the additional constraints
objective by
t=1 t
that kW (t + 1) − W (t)k ≤ et for all t. We can also represent
these additional constraints as linear constraints. Specifically,
since
X
kW (t + 1) − W (t)k = max
|Wij (t + 1) − Wij (t)|,
j

i

P
each of these constraints can be replaced by i hij (t) ≤ et
for all t and j if we add the additional constraints
|Wij (t + 1) − Wij (t)| ≤ hij (t)
for all i, j and t. Each of these constraints can be replaced
two linear constraints, namely
Wij (t + 1) − Wij (t)) ≤ hij (t),

−Wij (t + 1) + Wij (t)) ≤ hij (t)

