The Optimality of the Interleaving Distance on Multidimensional Persistence Modules

Details The Optimality of the Interleaving Distance on Multidimensional Persistence Modules The Optimality of the Interleaving Distance on Multidimensional Persistence Modules

2011-06-27

arxiv.org/abs/1106.5305v2

Computer Science

Computational Geometry

55 pages. Changes to version 2: Optimality result for well behaved ordinary persistence modules over arbitrary fields added; e

Scientific paper

Building on an idea of Chazal et al. [11], we introduce and study the interleaving distance, a pseudometric on isomorphism classes of multidimensional persistence modules. We present five main results about the interleaving distance. First, we show that in the case of ordinary persistence, the interleaving distance is equal to the bottleneck distance on tame persistence modules. Second, we prove a theorem which implies that the restriction of the interleaving distance to finitely presented multidimensional persistence modules is a metric. The same theorem, together with our first result, also yields a converse to the algebraic stability theorem of [11]; this answers a question posed in that paper. Third, we observe that the interleaving distance is stable in three senses analogous to those in which the bottleneck distance is known to be stable. Fourth, we introduce several notions of optimality of metrics on persistence modules and show that when the underlying field is the field of rational numbers or a field of prime order, the interleaving distance is optimal with respect to one of these notions. This optimality result, which is new even for ordinary persistence, is the central result of the paper. We also prove that a version of this result holds for ordinary persistence modules over any field, provided we restrict attention to a class of well behaved ordinary persistence modules containing the finitely presented ones. Fifth, we show that the computation of the interleaving distance between two finitely presented multidimensional persistence modules M and N reduces to deciding the solvability of O(log m) systems of multivariate quadratic equations, each with O(m^2) variables and O(m^2) equations, where m is the total number of generators and relations in a minimal presentation for M and a minimal presentation for N.

Affiliated with

Also associated with

No associations

Rating

The Optimality of the Interleaving Distance on Multidimensional Persistence Modules does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Optimality of the Interleaving Distance on Multidimensional Persistence Modules, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Optimality of the Interleaving Distance on Multidimensional Persistence Modules will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-638075