distances between persistence modules. Amongst them, the matching distance [27] attracts the attention
of multi-parameter persistence practitioners.
To compute the matching distance between two n-parameter persistence modules, one uses the fact
that restricting an n-parameter filtration to any affine line of positive slope through the parameter
space yields a 1-parameter filtration. There is therefore a corresponding restriction of the n-parameter
persistence module to a 1-parameter module along that line. This construction allows for the knowledge
and computational methods from the 1-dimensional case to be applied to the n-dimensional case.
Indeed, following this idea, the matching distance is defined as a supremum of the one-dimensional
bottleneck distance, over the collection of all lines of positive slope in the parameter space, i.e.,
dmatch(M, N) := sup
L:u=s ⃗m+b
ˆmL·dB(dgm ML,dgm NL),
where ˆmLis a normalization term explained in Section 2. However, exactly computing this distance is
not an easy task given the nature of its definition. As a first step towards an exact computation, several
approximations of this distance have been provided for 2-dimensional persistence modules [4, 22]. The
exact computation of the matching distance is currently only possible for 2-dimensional modules [20],
with recent computational improvements in terms of time complexity [5]. These methods exploit the
duality of points and lines in the plane.
While approximated computations can be very useful in practice, computing the exact value of the
matching distance has its own merits. One of them is that it can distinguish modules for which the rank
invariant is a complete invariant, such as rectangle decomposable modules, as the matching distance is
a metric for the rank invariant. [7]
In this paper, we propose a method to compute the matching distance based on a refinement of
the framework developed in [1], in which we compute the rank invariant of a multi-persistence module
from a finite set of critical parameter values. These critical parameter values capture all the changes
in homology occurring throughout the multi-filtration. They may also be used to partition the set of
positive lines in the parameter space into equivalence classes, where each equivalence class maintains the
same birth and death ordering within the restricted module for all possible homology classes.
Based on these results, we formulate the idea that the critical values must be relevant to the choice
of lines for the computation of the matching distance. Leveraging the framework of [1] to compute the
matching distance allows us to reduce the number of lines necessary to compute the matching distance
to a finite set, thus reducing the computation to a maximum rather than a supremum without exploiting
the point-line duality used in [20]. Through some examples, we show that considering only lines passing
through pairs of critical values is not sufficient. This is because the definition of matching distance
depends on the bottleneck distance, and lines in the same equivalence class might not be such that the
bottleneck distance is always achieved by the same pairing of births/deaths, as will be further explained
in Section 3.
To overcome this problem, we analyze where switches might happen in the matching which achieves
the bottleneck distance, identifying a set of points in the parameter space which we later on refer to
as the set of switch points. This set allows us to refine our equivalence relation on the set of positive
lines (see Section 4) by partitioning lines through the parameter space using the union of the critical
parameter values with the switch points. Using this union, it is possible to identify all the lines at which
the matching distance can be realised. We explain in detail how to compute all relevant parameter values
and show that the matching distance is attained either at: a line through a pair of points in this union,
or a line of diagonal slope through exactly one of the points in the union (see Theorem 3.1).
The contribution of this paper is to advance the state of the art, although still restricted to two dimen-
sions, in two ways: computing the matching distance in a way which is both geometrically interpretable
and implementable. In contrast to other methods such as [20, 5], we provide a geometric understanding
of different lines, including horizontal, vertical, and diagonal lines, as well as lines through critical values,
and their contribution to the matching distance. In addition, the method we propose leads to explicit
computations of important lines, which will lead to an algorithm that can be implemented.
The paper is structured as follows. In Section 2, we give necessary background from multi-parameter
persistent homology, as well as some of the concepts coming from the framework developed in [1]. We
also provide some examples of two-parameter persistence modules for which we explicitly show which
lines are necessary to compute the matching distance. In Section 3, we provide the statement and proof
of our main theoretical result Theorem 3.1 and include a discussion on the role of vertical and horizontal
lines. In Section 4, we provide guidelines for the computation of the switch points, which are necessary
to the exact computation of the matching distance. Finally, in Section 6, we discuss future directions of
study.
2