# Some Remarks on the Algebraic Properties of Group Invariant Operators in Persistent Homology

Patrizio Frosini, Nicola Quercioli

► To cite this version:

Patrizio Frosini, Nicola Quercioli. Some Remarks on the Algebraic Properties of Group Invariant Operators in Persistent Homology. 1st International Cross-Domain Conference for Machine Learning and Knowledge Extraction (CD-MAKE), Aug 2017, Reggio, Italy. pp.14-24, 10.1007/978-3-319-66808-6_2. hal-01677132

HAL Id: hal-01677132

https://inria.hal.science/hal-01677132

Submitted on 8 Jan 2018

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Some remarks on the algebraic properties of group invariant operators in persistent homology

Patrizio Frosini and Nicola Quercioli

Department of Mathematics, University of Bologna, Italy
patrizio.frosini@unibo.it, nicola.quercioli@studio.unibo.it

**Abstract.** Topological data analysis is a new approach to processing digital data, focusing on the fact that topological properties are quite important for efficient data comparison. In particular, persistent topology and homology are relevant mathematical tools in TDA, and their study is attracting more and more researchers. As a matter of fact, in many applications data can be represented by continuous real-valued functions defined on a topological space $X$, and persistent homology can be efficiently used to compare these data by describing the homological changes of the sub-level sets of those functions. However, persistent homology is invariant under the action of the group Homeo($X$) of all self-homeomorphisms of $X$, while in many cases an invariance with respect to a proper subgroup $G$ of Homeo($X$) is preferable. Interestingly, it has been recently proved that this restricted invariance can be obtained by applying $G$-invariant non-expansive operators to the considered functions. As a consequence, in order to proceed along this line of research we need methods to build $G$-invariant non-expansive operators. According to this perspective, in this paper we prove some new results about the algebra of GINOs.

**Keywords:** Natural pseudo-distance, filtering function, group action, group invariant non-expansive operator, persistent homology group, topological data analysis

## Introduction

Topological data analysis (TDA) is an emerging research field that is revealing important in managing the deluge of data of the present digital world. The ability of describing and comparing how data are connected to each other in a topological sense is a key point for their efficient comparison [3]. Persistent topology and homology are relevant mathematical tools in TDA, and many researchers are investigating these concepts both from a theoretical and an applicative point of view [6]. Their approach is based on the fact that datasets can be often represented by real-valued continuous functions defined on a topological space $X$ [2]. The theory of persistence analyzes the properties of these functions that “persist” in presence of noise. In particular, this analysis can be done by studying the evolution of the $k$-dimensional holes of the sub-level sets associated with those
functions. This theory admits also an extension to the case of functions taking values in $\mathbb{R}^m$ (cf., e.g., [4,5]).

Recently, this line of research has been inserted in a theoretical framework that could be of use to establish a link between persistence theory and machine learning [10]. The main idea consists in looking at shape comparison as a problem concerning the approximation of a given observer instead of the approximation of data. In this setting each observer is seen as a collection of suitable operators acting on the family of functions that represents the set of possible data. These operators describe the way the information is elaborated by the observer, on the basis of the assumption that the observer is not entitled to choose the data but only the method to process them.

The operators we consider often refer to some kind of invariance. Invariance is an important property in shape analysis, and “approximating an observer” usually means to understand not only the way she/he looks at data, but also the equivalences she/he refers to in data comparison. For example, in character recognition the observer is interested in distinguishing the symbols 6 and 9, so that the invariance group should not contain rotations, while this is no more true if the observer is interested in comparing spiral shells.

In presence of an invariance group, the natural pseudo-metric can be used as a ground-truth for shape comparison. Let us consider a set $\Phi$ of continuous $\mathbb{R}$-valued functions defined on a topological space $X$ and a subgroup $G$ of the group Homeo($X$) of all self-homeomorphisms of $X$. We assume that the group $G$ acts on $\Phi$ by composition on the right. Now we can define the *natural pseudo-distance* $d_G$ on $\Phi$ by setting $d_G(\varphi_1, \varphi_2) = \inf_{g \in G} \|\varphi_1 - \varphi_2 \circ g\|_{\infty}$, where $\| \cdot \|_{\infty}$ denotes the sup-norm. Roughly speaking, $d_G$ is based on the attempt to find the best correspondence between two functions of $\Phi$. If $d_G(\varphi_1, \varphi_2)$ is small, by definition there exists a homeomorphism $g \in G$ such that $\varphi_2 \circ g$ is a good approximation of $\varphi_1$ with respect to the sup-norm. If $\varphi_1$ and $\varphi_2$ describe the results of two measurements of $X$ (e.g., two pictures, two CT scans, or two financial series), the fact that $d_G(\varphi_1, \varphi_2)$ is small means that the considered measurements can be aligned well by the reparameterization expressed by a suitable homeomorphism $g$.

Unfortunately, $d_G$ is usually difficult to compute. However, one can approximate the natural pseudo-distance by means of persistent homology and $G$-invariant non-expansive operators (GINOs).

We recall that persistent homology describes the $k$-dimensional holes (components, tunnels, voids, ...) of the sub-level sets of a topological space $X$ with respect to a given continuous function $\varphi: X \to \mathbb{R}^m$. If $m = 1$, persistent homology is described by suitable collections of points called *persistence diagrams* [8]. These diagrams can be compared by a suitable metric $d_{\text{match}}$, called *bottleneck* (or *matching*) distance (see the appendix of this paper).

It is known that if we compute the classical bottleneck distance between persistence diagrams associated with the functions $F(\varphi_1)$, $F(\varphi_2)$ and let $F$ vary in the set of all $G$-invariant non-expansive operators on the space $\Phi$, we obtain the same information given by the natural pseudo-distance $d_G$ [11]. Therefore,
the goal of approximating $d_G$ naturally leads to the problem of approximating the space $\mathcal{F}(\Phi, G)$ of all $G$-invariant non-expansive operators on $\Phi$. In [11] it has been proved that this space is compact, if we assume that $\Phi$ is compact. This guarantees that, in principle, $\mathcal{F}(\Phi, G)$ can be approximated by a finite subset.

In order to proceed along this line of research we need general methods to build $G$-invariant non-expansive operators. According to the goal of realizing those methods, this paper is devoted to prove some new results about the algebra of GINOs.

Our work is organized as follows. In Section 1 we introduce our mathematical setting. In Section 2 we give some new results about $G$-invariant non-expansive operators: in particular, we show how we can produce new GINOs by composition, translation, weighted average, maximization and, more in general, by means of a 1-Lipschitzian function applied to pre-existing GINOs. A short appendix about persistent homology concludes the paper.

# 1 Our mathematical model

Let $X$ be a non-empty compact metric space, triangulated by a finite (and hence compact) simplicial complex. We suppose that the $k$-th homology group of $X$ is nontrivial. For $k = 0$ the homology group always verifies the last assumption. Since $X$ could be embedded in a larger (finitely) triangulable space $Y_k$ with non-trivial homology in degree $k$, and substituted with $Y_k$, for $k \ge 1$ the condition is not restrictive. Let us consider a subspace $\Phi$ of the topological space $C^0(X, \mathbb{R})$ of all real-valued continuous functions from $X$, endowed with the topology induced by the sup-norm $\| \cdot \|_{\infty}$. Since $X$ is compact, the considered functions are uniformly continuous. We suppose that $\Phi$ contains at least the constant functions taking every finite value $c$ with $|c| \le \sup_{\varphi \in \Phi} \|\varphi\|_{\infty}$. Each function in the space $\Phi$ will be called an *admissible filtering function on $X$*. The space $\Phi$ contains the functions that the observer considers as acceptable data. We also assume that a subgroup $G$ of the group $\text{Homeo}(X)$ of all homeomorphisms from $X$ onto $X$ is given, and that if $\varphi \in \Phi$ and $g \in G$, then $\varphi \circ g \in \Phi$. In other words, the group $G$ acts on $\Phi$ by composition on the right. We do not require $G$ to be a proper subgroup of $\text{Homeo}(X)$, so that the equality $G = \text{Homeo}(X)$ may hold. One can easily show that $G$ is a topological group with respect to the topology of the uniform convergence, and that the right action of $G$ on the set $\Phi$ is continuous.

**Definition 1.** Assume that a space $\Phi \subseteq C^0(X, \mathbb{R})$ and a group $G \subseteq \text{Homeo}(X)$ are given. Each function $F: \Phi \to \Phi$ is called a $G$-invariant *Non-expansive Operator (GINO) for the pair $(\Phi, G)$*, if:

1. $F$ is $G$-invariant: $F(\varphi \circ g) = F(\varphi) \circ g, \forall \varphi \in \Phi, \forall g \in G$;

2. $F$ is non-expansive: $\|F(\varphi_1) - F(\varphi_2)\|_{\infty} \le \|\varphi_1 - \varphi_2\|_{\infty}, \forall \varphi_1, \varphi_2 \in \Phi$.

If $\Phi$ is the space of all normalized grayscale images represented as functions from $\mathbb{R}^2$ to $[0, 1]$ and $G$ is the group of rigid motions of the plane, a simple example of operator $F \in \mathcal{F}(\Phi, G)$ is given by the Gaussian blurring filter, i.e.
the operator $F$ taking $\varphi \in \Phi$ to the function $\psi(x) = \frac{1}{2\pi\sigma^2} \int_{\mathbb{R}^2} \varphi(y)e^{-\frac{\|x-y\|^2}{2\sigma^2}} dy$ (see Figure 1).

<figure><img src="image_2.png" /><figcaption>Fig. 1. The Gaussian blurring filter as an example of $G$-invariant non-expansive operator for $G$ equal to the group of rigid motions of the plane.</figcaption></figure>

For another approach to $G$-invariant persistent homology we refer the interested reader to [9].

## 2 Some new results on group invariant non-expansive operators

In this section we will prove some new results about the algebra of GINOs, showing how new GINOs can be built by using pre-existing GINOs. The simplest one is based on functional composition.

**Proposition 1.** If $F_1, F_2$ are GINOs for $(\Phi, G)$, then $F := F_2 \circ F_1$ is a GINO for $(\Phi, G)$.

*Proof.* 1. Since $F_1, F_2$ are $G$-invariant, $F$ is $G$-invariant:

$$ 
\begin{align*}
F(\varphi \circ g) &= (F_2 \circ F_1)(\varphi \circ g) = F_2(F_1(\varphi \circ g)) \\
&= F_2(F_1(\varphi) \circ g) = F_2(F_1(\varphi)) \circ g \\
&= F(\varphi) \circ g
\end{align*}
$$

for every $\varphi \in \Phi$ and every $g \in G$.
2. Since $F_1, F_2$ are non-expansive, $F$ is non-expansive:

$$
\begin{align*}
\|F(\varphi_1) - F(\varphi_2)\|_{\infty} &= \|(F_2 \circ F_1)(\varphi_1) - (F_2 \circ F_1)(\varphi_2)\|_{\infty} \\
&= \|F_2(F_1(\varphi_1)) - F_2(F_1(\varphi_2))\|_{\infty} \\
&\le \|F_1(\varphi_1) - F_1(\varphi_2)\|_{\infty} \\
&\le \|\varphi_1 - \varphi_2\|_{\infty}
\end{align*}
$$

$\forall \varphi_1, \varphi_2 \in \Phi.$

□

Let $F_1, \dots, F_n$ be GINOs for $(\Phi, G)$. We can consider the function

$$
\max(F_1, \dots, F_n)(\varphi) := [\max(F_1(\varphi), \dots, F_n(\varphi))]
$$

from $\Phi$ to $C^0(X, \mathbb{R})$, where $[\max(F_1(\varphi), \dots, F_n(\varphi))]$ is defined by setting

$$
[\max(F_1(\varphi), \dots, F_n(\varphi))](x) := \max(F_1(\varphi)(x), \dots, F_n(\varphi)(x)).
$$

**Proposition 2.** Let $F_1, \dots, F_n$ be GINOs for $(\Phi, G)$.
If $\max(F_1, \dots, F_n)(\Phi) \subseteq \Phi$, then $\max(F_1, \dots, F_n)$ is a GINO for $(\Phi, G)$.

In order to proceed, we recall the proof of the following lemma (cf. [1]):

**Lemma 1.** For every $u_1, \dots, u_n, v_1, \dots, v_n \in \mathbb{R}$ it holds that

$$
| \max(u_1, \dots, u_n) - \max(v_1, \dots, v_n) | \leq \max(|u_1 - v_1|, \dots, |u_n - v_n|).
$$

Proof. Without loss of generality we can suppose that $\max(u_1, \dots, u_n) = u_1$.
If $\max(v_1, \dots, v_n) = v_1$ the claim trivially follows. It only remains to check the
case $\max(v_1, \dots, v_n) = v_i$, $i \neq 1$. We have that

$$
\begin{align*}
\max(u_1, \dots, u_n) - \max(v_1, \dots, v_n) &= u_1 - v_i \\
&\le u_1 - v_1 \\
&\le |u_1 - v_1| \\
&\le \max(|u_1 - v_1|, \dots, |u_n - v_n|).
\end{align*}
$$

Similarly, we obtain

$$
\begin{align*}
\max(v_1, \dots, v_n) - \max(u_1, \dots, u_n) &= v_i - u_1 \\
&\le v_i - u_i \\
&\le |v_i - v_i| \\
&\le \max(|u_1 - v_1|, \dots, |u_n - v_n|).
\end{align*}
$$

This proves the statement.

□
Now we can prove the Proposition 2:

*Proof.* 1. Since $F_1, \dots, F_n$ are $G$-invariant, $\max(F_1, \dots, F_n)$ is $G$-invariant:

$$ \begin{aligned} \max(F_1, \dots, F_n)(\varphi \circ g) &= [\max(F_1(\varphi \circ g), \dots, F_n(\varphi \circ g))] \\ &= [\max(F_1(\varphi) \circ g, \dots, F_n(\varphi) \circ g)] \\ &= [\max(F_1(\varphi), F_n(\varphi)] \circ g \\ &= \max(F_1, \dots, F_n)(\varphi) \circ g \end{aligned} $$

for every $\varphi \in \Phi$ and every $g \in G$.

2. Lemma 1 and non-expansivity of $F_1, \dots, F_n$ imply that $\forall x \in X$ and $\forall \varphi_1, \varphi_2 \in \Phi$:

$$ \begin{aligned} & |\max(F_1(\varphi_1(x)), \dots, F_n(\varphi_1(x))) - \max(F_1(\varphi_2(x)), \dots, F_n(\varphi_2(x)))| \\ & \le \max(|F_1(\varphi_1(x)) - F_1(\varphi_2(x))|, \dots, |F_n(\varphi_1(x)) - F_n(\varphi_2(x))|) \\ & \le \max(\|F_1(\varphi_1) - F_1(\varphi_2)\|_{\infty}, \dots, \|F_n(\varphi_1) - F_n(\varphi_2)\|_{\infty}) \\ & \le \max(\|\varphi_1 - \varphi_2\|_{\infty}, \dots, \|\varphi_1 - \varphi_2\|_{\infty}, \dots, \|\varphi_1 - \varphi_2\|_{\infty}) \\ & = \|\varphi_1 - \varphi_2\|_{\infty}. \end{aligned} $$

Since it holds for every $x \in X$, we obtain that $\|\max(F_1, \dots, F_n)(\varphi_1) - \max(F_1, \dots, F_n)(\varphi_2)\|_{\infty} \le \|\varphi_1 - \varphi_2\|_{\infty}$. $\square$

<figure><img src="image_3.png" /></figure>

Let $F$ be a GINO for $(\Phi, G)$ and $b \in \mathbb{R}$. We can consider the function

$$ F_b(\varphi) := F(\varphi) - b $$

from $\Phi$ to $C^0(X, \mathbb{R})$.

**Proposition 3.** Assume that $F$ is a GINO for $(\Phi, G)$ and $b \in \mathbb{R}$. If $F_b(\Phi) \subseteq \Phi$ then the operator $F_b$ is a GINO for $(\Phi, G)$.

*Proof.* 1. Since $F$ is $G$-invariant, $F_b$ is $G$-invariant too:

$$ F_b(\varphi \circ g) = F(\varphi \circ g) - b = F(\varphi) \circ g - b = F_b(\varphi) \circ g $$

for every $\varphi \in \Phi$ and every $g \in G$.

2. Since $F$ is non-expansive, $F_b$ is non-expansive too:

$$ \begin{aligned} \|F_b(\varphi_1) - F_b(\varphi_2)\|_{\infty} &= \|F(\varphi_1) - b - (F(\varphi_2) - b)\|_{\infty} \\ &= \|F(\varphi_1) - F(\varphi_2)\|_{\infty} \\ &\le \|\varphi_1 - \varphi_2\|_{\infty} \end{aligned} $$

for every $\varphi_1, \varphi_2 \in \Phi$.

<figure><img src="image_4.png" /></figure>
Let $F_1, \dots, F_n$ be GINOs for $(\Phi, G)$ and $(a_1, \dots, a_n) \in \mathbb{R}^n$ with $\sum_{i=1}^n |a_i| \le 1$. We can consider the function

$$F_{\Sigma}(\varphi) := \sum_{i=1}^{n} a_i F_i(\varphi)$$

from $\Phi$ to $C^0(X, \mathbb{R})$.

**Proposition 4.** Assume that $F_1, \dots, F_n$ are GINOs for $(\Phi, G)$ and $(a_1, \dots, a_n) \in \mathbb{R}^n$ with $\sum_{i=1}^n |a_i| \le 1$. If $F_{\Sigma}(\Phi) \subseteq \Phi$, then $F_{\Sigma}$ is a GINO for $(\Phi, G)$.

*Proof.* 1. $F_{\Sigma}$ is $G$-invariant, because $F_1, \dots, F_n$ are $G$-invariant:

$$F_{\Sigma}(\varphi \circ g) = \sum_{i=1}^{n} a_i F_i(\varphi \circ g) = \sum_{i=1}^{n} a_i (F_i(\varphi) \circ g) = F_{\Sigma}(\varphi) \circ g$$

for every $\varphi \in \Phi$ and for every $g \in G$.

2. Since $F_1, \dots, F_n$ are non-expansive and $\sum_{i=1}^n |a_i| \le 1$, $F_{\Sigma}$ is non-expansive:

$$\begin{aligned}
\|F_{\Sigma}(\varphi_1) - F_{\Sigma}(\varphi_2)\|_{\infty} &= \left\| \sum_{i=1}^{n} a_i F_i(\varphi_1) - \sum_{i=1}^{n} a_i F_i(\varphi_2) \right\|_{\infty} \\
&= \left\| \sum_{i=1}^{n} a_i (F_i(\varphi_1) - F_i(\varphi_2)) \right\|_{\infty} \\
&\le \sum_{i=1}^{n} |a_i| \|(F_i(\varphi_1) - F_i(\varphi_2))\|_{\infty} \\
&\le \sum_{i=1}^{n} |a_i| \|\varphi_1 - \varphi_2\|_{\infty} \le \|\varphi_1 - \varphi_2\|_{\infty}
\end{aligned}$$

for every $\varphi_1, \varphi_2 \in \Phi$.

□

The last three results are generalized by the next one. Let $F_1, \dots, F_n$ be GINOs for $(\Phi, G)$ and $L$ be a 1-Lipschitzian map from $\mathbb{R}^n$ to $\mathbb{R}$, where $\mathbb{R}^n$ is endowed with the usual norm $\|(x_1, \dots, x_n)\|_{\infty} = \max_{1 \le i \le n} |x_i|$. Now we consider the function

$$L^*(F_1, \dots, F_n)(\varphi) := [L(F_1(\varphi), \dots, F_n(\varphi))]$$

from $\Phi$ to $C^0(X, \mathbb{R})$, where $[L(F_1(\varphi), \dots, F_n(\varphi))]$ is defined by setting

$$[L(F_1(\varphi), \dots, F_n(\varphi))](x) := L(F_1(\varphi)(x), \dots, F_n(\varphi)(x)).$$

**Proposition 5.** Assume that $F_1, \dots, F_n$ are GINOs for $(\Phi, G)$ and $L$ is a 1-Lipschitzian map from $\mathbb{R}^n$ to $\mathbb{R}$. If $L^*(F_1, \dots, F_n)(\Phi) \subseteq \Phi$, then $L^*(F_1, \dots, F_n)$ is a GINO for $(\Phi, G)$.
Proof. 1. The G-invariance of $F_1, \dots, F_n$ implies that $L^*(F_1, \dots, F_n)$ is G-invariant:

$$ 
\begin{aligned}
L^*(F_1, \dots, F_n)(\varphi \circ g) &= [L(F_1(\varphi \circ g), \dots, F_n(\varphi \circ g))] \\
&= [L(F_1(\varphi) \circ g, \dots, F_n(\varphi) \circ g)] \\
&= [L(F_1(\varphi), \dots, F_n(\varphi))] \circ g \\
&= L^*(F_1, \dots, F_n)(\varphi) \circ g
\end{aligned}
$$

for every $\varphi \in \Phi$ and every $g \in G$.

2. Since $F_1, \dots, F_n$ are non-expansive and $L$ is 1-Lipschitzian, for every $x \in X$ and every $\varphi_1, \varphi_2 \in \Phi$ we have that

$$ 
\begin{aligned}
& |L(F_1(\varphi_1)(x), \dots, F_n(\varphi_1)(x)) - L(F_1(\varphi_2)(x), \dots, F_n(\varphi_2)(x))| \\
& \le \|(F_1(\varphi_1)(x)) - F_1(\varphi_2(x)), \dots, F_n(\varphi_1)(x)) - F_n(\varphi_2(x))\|_{\infty} \\
& = \max_{1 \le i \le n} |F_i(\varphi_1(x)) - F_i(\varphi_2(x))| \\
& \le \max_{1 \le i \le n} \|F_i(\varphi_1) - F_i(\varphi_2)\|_{\infty} \\
& \le \|\varphi_1 - \varphi_2\|_{\infty}.
\end{aligned}
$$

In conclusion,

$$ \|L^*(F_1, \dots, F_n)(\varphi_1) - L^*(F_1, \dots, F_n)(\varphi_2)\|_{\infty} \le \|\varphi_1 - \varphi_2\|_{\infty}. $$

Therefore $L^*(F_1, \dots, F_n)$ is non-expansive.

□

## Conclusions

In this paper we have illustrated some new methods to build new G-invariant non-expansive operators from pre-existing ones. The ability of doing that is important to produce large sets of GINOs, in order to get good approximations of the topological space $\mathcal{F}(\Phi, G)$ and hence good approximations of the natural pseudo-distance $d_G$. The approximation of $\mathcal{F}(\Phi, G)$ can be seen as an approximation of the considered observer, represented as a collection of invariant operators.

In order to show the use of the approach based on GINOs, a simple demonstrator has been realized, illustrating how this technique could make available new methods for image comparison. The demonstrator is named GIPHOD-G-Invariant Persistent HOmology Demonstrator and is available at the web page http://giphod.ii.uj.edu.pl/index2/ (joint work with Grzegorz Jabłoński and Marc Ethier). The user is asked to choose an invariance group in a list and a query image in a dataset $\Phi^*$ of quite simple synthetic images obtained by adding a small number of bell-like functions (see Figure 2). After that, GIPHOD provides ten images that are judged to be the most similar to the proposed query image with respect to the chosen invariance group (see Figure 3). In this case study, the dataset $\Phi^*$ is a subset of the set $\Phi$ of all continuous functions from
the square [0, 1] × [0, 1] to the interval [0, 1]. Each function represents a grayscale
image on the square [0, 1] × [0, 1] (1=white, 0=black). GIPHOD uses a collection
of GINOs for each invariance group G and tries to approximate dG by means of
the previously described technique, based on computing the persistent homology
of the functions F(φ) for φ ∈ Φ and F varying in our set of operators.

Many questions remain open. In particular, the extension of our approach to
operators taking the pair (Φ, G) into a different pair (Ψ, H) should be studied.
We are planning to do that in a forthcoming paper.

<figure><img src="image_5.png" /><figcaption>**Fig. 2.** GIPHOD asks the user to choose an invariance group in a list and a query image in a dataset.</figcaption></figure>

Acknowledgment

The research described in this article has been partially supported by GNSAGA-
INdAM (Italy).

References

1. S. Biasotti, A. Cerri, P. Frosini, D. Giorgi, *A new algorithm for computing the 2-dimensional matching distance between size functions*, Pattern Recognition Letters, vol. 32, n. 14, 1735–1746 (2011).
<figure><img src="image_6.png" /><figcaption>**Fig. 3.** GIPHOD provides ten images that are judged to be the most similar to the proposed query image with respect to the chosen invariance group.</figcaption></figure>

2. S. Biasotti, L. De Floriani, B. Falcidieno, P. Frosini, D. Giorgi, C. Landi, L. Pa-paleo, M. Spagnuolo, Describing shapes by geometrical-topological properties of real functions, ACM Computing Surveys, vol. 40, n. 4, 12:1–12:87 (2008).

3. G. Carlsson, *Topology and data*, Bull. Amer. Math. Soc. (N.S.) 46, no. 2, 255–308 (2009).

4. G. Carlsson, A. Zomorodian, *The theory of multidimensional persistence*, Discrete & Computational Geometry, vol. 42, no. 1, 71–93 (2009).

5. A. Cerri, B. Di Fabio, M. Ferri, P. Frosini, and C. Landi, *Betti numbers in multidimensional persistent homology are stable functions*, Mathematical Methods in the Applied Sciences, vol. 36, 1543–1557 (2013).

6. H. Edelsbrunner, D. Morozov, *Persistent homology: theory and practice*, European Congress of Mathematics, 31–50 (2013).

7. H. Edelsbrunner, J. L. Harer, *Persistent homology—a survey*, Contemp. Math., vol. 453, 257–282 (2008).

8. H. Edelsbrunner, J. L. Harer, *Computational Topology. An introduction*, American Mathematical Society, Providence, RI, 2010.

9. P. Frosini, *G-invariant persistent homology*, Mathematical Methods in the Applied Sciences, vol. 38, n. 6, 1190–1199 (2015).

10. P. Frosini, *Towards an observer-oriented theory of shape comparison*, Proceedings of the 8th Eurographics Workshop on 3D Object Retrieval, Lisbon, Portugal, A. Ferreira, A. Giachetti, and D. Giorgi (Editors), 5-8 (2016).

11. P. Frosini, G. Jabłoński, *Combining persistent homology and invariance groups for shape comparison*, Discrete & Computational Geometry, vol. 55, n. 2, 373–409 (2016).
**Appendix: Persistent homology**

We recall some basic definitions and facts in persistent homology. A more detailed and formal treatment can be found in [7]. In plain words, persistent homology describes the changes of the homology groups of the sub-level sets $X_t = \varphi^{-1}((-\infty, t])$ varying $t$ in $\mathbb{R}$, for each real-valued continuous function $\varphi : X \to \mathbb{R}$. The parameter $t$ can be seen as an increasing time, whose change produces the birth and death of $k$-dimensional holes in the sub-level set $X_t$. For $k = 0, 1, 2$, the expression “$k$-dimensional holes” refers to connected components, tunnels and voids, respectively.

The concept of persistence can be formalized by the definition of persistent homology group with respect to the function $\varphi : X \to \mathbb{R}$:

**Definition 2.** If $u, v \in \mathbb{R}$ and $u < v$, we can consider the inclusion $i$ of $X_u$ into $X_v$. Such an inclusion induces a homomorphism $i_k : H_k(X_u) \to H_k(X_v)$ between the homology groups of $X_u$ and $X_v$ in degree $k$. The group $\text{PH}_k^\varphi(u, v) := i_k(H_k(X_u))$ is called the $k$-th persistent homology group with respect to the function $\varphi : X \to \mathbb{R}$, computed at the point $(u, v)$. The rank $r_k(\varphi)(u, v)$ of this group is said the $k$-th persistent Betti number function with respect to the function $\varphi : X \to \mathbb{R}$, computed at the point $(u, v)$.

*Remark 1.* We can easily check that the persistent homology groups (and hence also the persistent Betti number functions) are invariant under the action of Homeo($X$).

A classical way to represent persistent Betti number functions (up to subsets of measure zero of their domain) is given by multisets named persistence diagrams. The $k$-th persistence diagram is the multiset of all pairs $p_j = (b_j, d_j)$, where $b_j$ and $d_j$ are the times of birth and death of the $j$-th $k$-dimensional hole, respectively. When a hole never dies, we set its time of death equal to $\infty$. The multiplicity $m(p_j)$ says how many holes share both the time of birth $b_j$ and the time of death $d_j$. For technical reasons, the points $(t, t)$ are added to each persistence diagram, each one with infinite multiplicity.

Persistence diagrams can be compared by a metric $\delta_{match}$, which is called bottleneck distance or matching distance. We recall here its formal definition, taking into account that each persistence diagram $D$ can contain an infinite number of points, and that each point $p \in D$ has a multiplicity $m(p) \ge 1$. For every $q \in \Delta^*$, the equality $m(q) = 0$ means that $q$ does not belong to the persistence diagram $D$. In our exposition we set $\Delta := \{(x, y) \in \mathbb{R}^2 : x = y\}$, $\Delta^+ := \{(x, y) \in \mathbb{R}^2 : x < y\}$, $\bar{\Delta}^+ := \{(x, y) \in \mathbb{R}^2 : x \le y\}$, $\Delta^* := \Delta^+ \cup \{(x, \infty) : x \in \mathbb{R}\}$ and $\bar{\Delta}^* := \bar{\Delta}^+ \cup \{(x, \infty) : x \in \mathbb{R}\}$. We endow $\bar{\Delta}^*$ with the pseudo-metric $d^*$ defined by setting $d^*(p, p')$ equal to the minimum between the cost of moving $p$ to $p'$ and the cost of moving $p$ and $p'$ onto $\Delta$, with respect to the max-norm. We observe that $d^*(p, p') = 0$ for every $p, p' \in \Delta$. If $p \in \Delta^+$ and $p \in \Delta$, then $d^*(p, p')$ equals the distance, induced by the max-norm, between $p$ and $\Delta$. Points at infinity have a finite distance only to other points at infinity, and their distance equals the Euclidean distance between their abscissas.
**Definition 3.** Let $D_1, D_2$ be two persistence diagrams. We define the bottleneck distance $\delta_{match}$ between $D_1$ and $D_2$ by setting

$$ \delta_{match}(D_1, D_2) := \inf_{\sigma} \sup_{x \in D_1} d^*(x, \sigma(x)) $$

where $\sigma: D_1 \to D_2$ is a bijection.

For further details about the concepts of persistence diagram and bottleneck distance, we refer the reader to [7].