Massimo Ferri
Antonella Tavaglione
Lorenzo Zuffi
Alessandro Mella
$\mathbb{X}$ triangulable manifold
$f$ continuous.
$\mathbb{X}_{i} = f^{-1}\left(\left(-\infty, a_i\right]\right)$
$\mathbb{X}_{1} \subseteq \cdots \subseteq \mathbb{X}_{n} = \mathbb{X}$
Quantifiable and stable
Flexible
Robust
Graphs
Quivers
Labelled point clouds
Beyond topological persistence
A category $\mathbf C$ is composed of some objects $\textrm{Obj}(\mathbf C)$ and some morphisms $\textrm{Morph}(\mathbf C)$ between objects: $ A \xrightarrow{\phi} B $
Morphisms need to obey some simple axioms:
The language of category theory allows to describe
heterogeneous mathematical objects in a uniform way.
Category theory offers a pure theory of functions, not a
theory of functions derived from sets. (D. Scott)
Examples:
$\textbf{FinSet}$ is the category whose objects are
finite sets. Morphisms are functions between sets, with the
usual composition $\circ$.
Other categories: $\textbf{FinVec}_{\mathbb{K}}$,
$\textbf{FinSimp}$.
A functor is a mapping between two categories that preserves the categorical structure, i.e. objects, morphisms and composition.
It is common to define things in terms of so called universal properties. Let's work with the familiar category of sets:
It is common to define things in terms of so called
universal properties. Let's work with the familiar
category of sets vector spaces:
$\mathbb{X}_1\subseteq\dots\subseteq\mathbb{X}_n$
We associate to each $\mathbb{X}_i$ the dimension of the image
of a map between vector spaces, e.g.,
$\beta_k(\mathbb{X}_i,\mathbb{K}) =$
$=\textrm{dim}Z_k(\mathbb{X}_i,\mathbb{K}) - \textrm{dim}B_k(\mathbb{X}_i,\mathbb{K})$
Let $(\mathbf{C},\mathcal{U})$ be a concrete category.
We define axioms that enable to transition back and forth between
subobjects of $X\in\textrm{Obj}(\mathbf{C})$ and subsets of
$\mathcal{U}(X)$.
$\beta^*_0(X_i) = |Z_0(X_i)| - |B_0(X_i)|$
A coherent sampling ${\mathcal V}$ on $(\mathbf{C}, {\mathcal U})$ is the assignment to each $X\in \textrm{Obj}(\mathbf{C})$ of a set ${\mathcal V}(X)$ of subsets of ${\mathcal U}(X)$, such that
Example: Clique communities
Coherent samplings require restricting the source category to accept only monic morphisms, restricting to functors $\mathbf{FinGraph}_{monic}\to\mathbf{FinSet}$.
Given any of its objects $X$, let $F: 2^{{\mathcal U}(X)} \to \{true, false\}$ be any feature such that $F(\emptyset)= false$. We call $F$-set any set $A\subseteq {\mathcal U}(X)$ such that $F(A) = true$.
Example: Hubs detection
In a regular category $\mathbf{R}$, every morphism $X\xrightarrow{\phi}Y$ can be factored in $X\twoheadrightarrow Z\hookrightarrow Y$, such that $\phi=\mu\circ\epsilon$, $\epsilon:X\twoheadrightarrow Z$ is a regular epimorphism (quotient), and $\mu:Z\hookrightarrow Y$ is a monomorphism. This allows us to define naturally the notion of image.
Examples: $\mathbf{Set}$, $\mathbf{Group}$, $\mathbf{RMod}$, $\mathbf{Ring}$.
Intuition:
Let $X, Y$ be sets, and $f:X\rightarrow Y$.
Consider
$$X \times_Y X = \left\{(x_1,x_2)\in X\times X \textrm{ s.t. } f(x_1)=f(x_2) \right\}$$
Consider $p_1: X \times_Y X \rightarrow X$ and $p_2: X \times_Y X \rightarrow X$, then
$$X\twoheadrightarrow X / (p_1\sim p_2) \hookrightarrow Y$$
where the injection is defined as $i(\overline{x}) = f(x)$, for any $\overline{x}\in X / (p_1\sim p_2)$.
An Abelian category $\mathbf{C}$ has zero object, biproducts, every
morphism has kernel and cokernel, each monomorphism is a kernel
and each epimorphism is a cokernel.
Any Abelian category is regular.
Example:
The category $\textbf{Mod}_R$ of modules on a ring is
Abelian.
1. The zero object is the $0$-module (the trivial group equipped with
the trivial $R$ action).
2. $\textbf{Mod}_R$ has kernels and cokernels. Let $f: N_1\rightarrow N_2$,
then $ker(f) =\{x | f(x)=0\}$, and $coker(f)=N_2/Im(f)$.
3. A homomorphism $f: N_1\rightarrow N_2$ is a monomorphism (epimorphism)
only if it is an injection (surjection).
Like Vec
Length as a notion of dimension
$$0 \simeq X_0 \hookrightarrow X_1 \hookrightarrow \dots
\hookrightarrow X_n \simeq X$$ where all $X_{i+1}/X_i$ are simple.
Unlike Vec
No notion of basis
Simple object: Let $\mathbf{C}$ be an Abelian category. $X\in Obj(\mathbf{C})$ is simple if its only subobjects are $0$ and $X$.
Lemma (Schur lemma) Given $S, S^\prime$ simple objects in an Abelian category, morphisms from $S$ to $S^\prime$ are either zero or invertible.
An Abelian category is semisimple if all its objects are semisimple, i.e. each object can be written as a finite sum of simple objects.
Example: (Maschke's theorem) The category of representations of a finite group $G$ over a field of characteristic not dividing $|G|$ (or $0$) is semisimple.
Like Vec
Exact sequences split, i.e. any exact sequence is isomorphic to
$$0\rightarrow X \rightarrow X\oplus Y\rightarrow Y\rightarrow 0$$
Unlike Vec
More than one simple objects.
Persistent homology requires a few basic ingredients:
Properties of persistent Betti numbers
Given $u_1\le u_2 \le v_1 \le v_2$:
Definition (Categorical persistence function). $p:\textrm{Morph}(\mathbf C) \to \mathbb Z$ such that, given $u_1\to u_2 \to v_1 \to v_2$:
We recover the original definition when $\mathbf C = (\mathbb R, \le)$.
From a rank
Given a rank $r:\textrm{Obj}(\mathbf C) \to \mathbb Z$,
the rank of the image of a morphism $\phi \mapsto r(im(\phi))$
is a categorical persistence function:
From another categorical persistence function
Given a categorical persistence function $p$ in
$\mathbf D$ and a functor $F:\mathbf C \to \mathbf D$,
$p\circ F$ is a categorical persistence function in $\mathbf C$:
A categorical persistence function
$p:\textrm{Morph}(\mathbf C) \to \mathbb Z$ and a
functor $(\mathbb R, \le) \to \mathbf C$ induce a
categorical persistence function on $(\mathbb R, \le)$,
the classical case.
Functors $(\mathbb R, \le) \to \mathbf C$, i.e.
$(\mathbb R, \le)$-indexed diagrams in $\mathbf C$,
generalize filtrations.
Classical framework | Categorical framework |
---|---|
Topological spaces | Source category $\mathbf C$ |
Vector spaces | Regular target category $\mathbf R$ |
Dimension | Rank function on $\mathbf R$ |
Homology functor | Arbitrary functor $\mathbf C \to \mathbf R$ |
Filtration of topological spaces | $(\mathbb R, \le)$-indexed diagram in $\mathbf C$ |
Given a persistence function $p:\textrm{Morph}(\mathbf{C})\to \mathbb Z$, and a functor $F:(\mathbb R, \le) \to \mathbf{C}$ we can define:
Definition Given $p_F$ as above, we can define the cornerpoint multiplicity of $u < v$ as:
$$ \mu(u, v) = \min p_F(\beta, \gamma)-p_F(\alpha, \gamma) - p_F(\beta, \delta)+p_F(\alpha, \delta)$$
where the minimum is taken over $\alpha, \beta, \gamma, \delta$ respecting $\alpha < u < \beta$ and $\gamma < v < \delta$.
In practice, the tighter the above inequalities are, the smaller the right-hand side is.
Remark More generally, $p_F(\beta, \gamma)-p_F(\alpha, \gamma) - p_F(\beta, \delta)+p_F(\alpha, \delta)$ denotes the sum of multiplicities of cornerpoints inside the rectangle $(\alpha, \beta] \times (\gamma, \delta]$ (technical assumption: $\alpha, \beta, \gamma, \delta$ must be right-regular).
Definition We denote $\mathcal{D}F$ the persistence diagram of $F$ (cornerpoints with multiplicity).
In $\mathbf{R}^{(\mathbb R, \le)}$ we have "interval objects" of the type:
$$ \chi_{I, S}(a) = \begin{cases}{} S&\text{if } a \in I\\ 0 &\text{otherwise} \end{cases} $$ and $$ \chi_{I, S}(a \le b) = \begin{cases}{} \textrm{Id}_S&\text{if } a, b \in I\\ 0 &\text{otherwise} \end{cases} $$
Bottleneck distance is defined as usual in terms of persistence diagrams, as the infimum $l_\infty$ distance of bijections of $\mathcal{D}F$ and $\mathcal{D}G$
Theorem (Stability) Given a category $\mathbf{C}$ with finite colimits, a persistence function $p$ on $\mathbf{C}$ and two tame $(\mathbb R,\le)$-indexed diagrams $F, G:(\mathbb R, \le) \to \mathbf{C}$, the interleaving distance between $F,G$ is greater or equal than the bottleneck distance:
Theorem (Tightness) Given a semisimple Abelian category $\mathbf{R}$ with essentially one simple object and the persistence function $\phi \mapsto length(im(\phi))$, interleaving and bottleneck distances are equal on tame $(\mathbb R, \le)$-indexed diagrams.
The multicolored persistence diagram is simply the sum of persistence diagrams of the components superimposed in different "colors".
Multicolored bottleneck distance is defined in terms of persistence
diagrams, as the infimum $l_\infty$ distance of color-preserving bijections
of $\mathcal{D}F$ and $\mathcal{D}G$.
Theorem (Multicolored stability) Let $\mathcal{C}$ be a coloring on a ranked regular category $(\mathbf{C}, r)$ with finite colimits. Given two tame $(\mathbb R,\le)$-indexed diagrams $F, G:(\mathbb R, \le) \to \mathbf{C}$, the interleaving distance between $F,G$ is greater or equal than the multicolored bottleneck distance:
Theorem (Multicolored tightness) Given a semisimple Abelian category $\mathbf{R}$ and the rank function $length$, interleaving and multicolored bottleneck distances are equal on tame $(\mathbb R, \le)$-indexed diagrams.