\documentclass[XUPS,XML,SOM,Unicode,francais, NoFloatCountersInSection]{cedram}
\setcounter{tocdepth}{2}

\usepackage{../xups24}
\graphicspath{{xups24-04_figures}}
\usepackage{tikz-cd}
\usepackage{adjustbox}

%\XUPScorrections

\hyphenation{fini finie finies finis topo-lo-gi-que topo-lo-gi-ques durant}
\newcommand\mto{\mathchoice{\longmapsto}{\mapsto}{\mapsto}{\mapsto}}

\begin{document}
\frontmatter
\title{Théorie de la persistance (2/2): stabilité}

\author{\firstname{Mathieu} \lastname{Carrière}}
\address{DataShape team, Centre Inria d'Université Côte d'Azur}
\email{mathieu.carriere@inria.fr}
\urladdr{https://www-sop.inria.fr/members/Mathieu.Carriere}

%\thanks{Journées X-UPS 2024. Introduction à l'analyse de données. Éditions de l'École polytechnique, 2024}

\begin{abstract}
Une composante centrale de la théorie de la persistance est le théorème de stabilité, qui garantit que des diagrammes de persistance issus des sous-niveaux de fonctions proches en norme infinie, sont eux-mêmes proches au sens de la distance bottleneck. Dans cet exposé, nous étudierons différentes répercussions de ce théorème en analyse de données et en inférence géométrique et statistique, ainsi que sa version algébrique définie au niveau des modules de persistance.
\end{abstract}

\maketitle

\tableofcontents
\mainmatter

Nous avons vu dans le texte~\cite{chap-pers-1} que les diagrammes de persistance sont bien définis (dans le cas des modules pdf),
et qu'ils sont calculables en temps cubique pour les filtrations simpliciales. Le but de ce texte est d'explorer le troisième
pilier de la théorie de la persistance, à savoir le théorème de stabilité, qui stipule que les diagrammes de persistance
issus des sous-niveaux de deux fonctions proches en norme infinie sont eux-mêmes proches, au sens d'une certaine distance
entre diagrammes, que nous allons définir en section~\ref{subsec:diag-dist}. Nous formulerons ensuite le théorème de stabilité
en section~\ref{subsec:th-stab}, et~nous verrons ses répercussions directes en inférence géométrique et statistique dans les sections~\ref{subsec:stab-cech}
et~\ref{subsec:inference-geom}. Enfin, nous clôturerons ce texte en abordant la version algébrique et générale du théorème
de stabilité au niveau des modules de persistance, via la distance d'entrelacement, en section~\ref{subsec:module-dist}.

\begin{remarque*}
Dans ce texte, et dans un souci de simplification, nous nous restreignons à $T=\R$, $\mathbb K=\Z/2\Z$, et aux diagrammes de cardinaux finis, et dont les coordonnées des points sont elles aussi
finies. Ces diagrammes apparaissent d'ailleurs très fréquemment en pratique, lorsqu'ils sont calculés sur des jeux de données de taille finie.
On désigne par $\dgspace$ l'ensemble de ces diagrammes. Remarquons pour finir que la plupart des notions définies dans ce texte se généralisent sans problème
aux diagrammes avec une infinité de points, et/ou des points dans le plan étendu $\R\times{}]-\infty,+\infty]$.
\end{remarque*}

\section{Distances entre diagrammes de persistance}
\label{subsec:diag-dist}

Une manière naturelle de comparer des diagrammes de persistance consiste à associer les points des deux diagrammes entre eux,
et de mesurer le coût d'un tel appariement en calculant les distances entre les points qui ont été ainsi mis en correspondance.
Cette approche, qui sous-tend effectivement la définition des distances usuelles entre diagrammes, nécessite cependant de ne chercher
que des correspondances \emph{partielles} entre les points des diagrammes, car on ne peut pas garantir a priori que les cardinaux des diagrammes
sont égaux.

\begin{definition}
\label{def:corr-partielle}
Soient
$D,D'\in\dgspace$ deux diagrammes de persistance. Une \emph{correspondance partielle} $\corr$ entre $D$ et $D'$ est un sous-ensemble du produit cartésien $D\times D'$ tel que les projections
\[
\pi_1:
\begin{cases}
\begin{aligned}
\corr & \to D \\
(p,p') & \mto p
\end{aligned}
\end{cases}
\quad\quand\quad
\pi_2:\begin{cases}
\begin{aligned}
\corr & \to D' \\
(p,p') & \mto p'
\end{aligned}
\end{cases}
\]
sont injectives. L'ensemble des correspondances partielles entre $D$ et~$D'$ est noté $\corr(D,D')$.

En outre, le \emph{coût d'ordre} $q\in\N$ associé à la correspondance partielle~$\corr$, et noté $c_q(\corr)$, se calcule ainsi:
\[
c_q(\corr):= \biggl(\sum_{(p,p')\in \corr}\|p - p'\|^q_\infty + c^1_q(\corr) + c^2_q(\corr)\biggr)^{1/q},
\]
où les coûts additionnels $c^1_q(\corr), c^2_q(\corr)$ sont définis par
\[
\begin{aligned}
c^1_q(\corr) &:=\sum_{p\in D\setminus \im(\pi_1)} \|p-\pi_\Delta(p)\|^q_\infty, \\
c^2_q(\corr) &:=\sum_{p'\in D'\setminus \im(\pi_2)} \|p'-\pi_\Delta(p')\|^q_\infty,
\end{aligned}
\]
où $\pi_\Delta(\cdot)$ désigne la projection sur la diagonale.
\end{definition}

Le coût d'une correspondance partielle $\corr$ consiste donc à additionner les distances entre les points mis en correspondance par $\corr$,
ainsi que les distances à la diagonale des points restants.
Il est en effet bon de rappeler ici que la distance à la diagonale joue un rôle particulier dans la théorie de la persistance, en cela
qu'elle correspond de manière équivalente à la longueur des barres dans le code-barres, et donc à la durée de vie des différentes
classes d'homologie persistante. Voir la figure~\ref{fig:matching} pour un exemple de correspondance.

\begin{figure}[htb]
\centering
\includegraphics[width=0.4\textwidth]{matching}
\caption{\label{fig:matching} Exemple de correspondance partielle entre deux diagrammes. En haut du plan, deux points bleus sont appariés au même point rouge de multiplicité $2$.}
\end{figure}

\begin{remarque}
Étant donnés deux diagrammes de persistance~$D$ et~$D'$, la correspondance partielle triviale $\corr=\varnothing\in\corr(D,D')$ entre~$D$ et~$D'$
a donc pour coût la somme des distances à la diagonale des points de $D\cup D'$.
\end{remarque}

Une fois le coût d'une correspondance bien défini, la distance la plus naturelle entre diagrammes de persistance consiste finalement
à calculer le coût du meilleur appariement entre leurs points.

\begin{definition}
Soient $D$ et $D'$ deux diagrammes de persistance.
Soit $q\in\N^*$. La \emph{distance de Wasserstein d'ordre} $q$ entre $D$ et $D'$ est définie par:
\begin{equation}
d_q(D,D'):= \inf\, \{c_q(\corr)\mid \corr\in\corr(D,D')\}.
\end{equation}
\end{definition}

Lorsqu'on laisse $q$ tendre vers $+\infty$, la distance de Wasserstein d'ordre $q$ tend vers une distance particulière et importante, appelée
la \emph{distance du goulot de bouteille} $\bottleneckd$:

\begin{definition}
Soient $D$ et $D'$ deux diagrammes de persistance.
La~\emph{distance du goulot de bouteille} entre $D$ et $D'$ est définie par:
\begin{equation}
\bottleneckd(D,D'):= \inf\, \{c_\infty(\corr)\mid \corr\in\corr(D,D')\},
\end{equation}
où $c_\infty(\corr)$ est la borne supérieure de la réunion des trois ensembles de réels
\begin{itemize}
\item
$\{\|p - p'\|_\infty\mid (p,p')\in \corr\}$,
\item
$\{\|p-\pi_\Delta(p)\|_\infty\mid p\in D\setminus \im(\pi_1)\}$,
\item
$\{\|p'-\pi_\Delta(p')\|_\infty\mid p'\in D'\setminus \im(\pi_2)\}$.
\end{itemize}
\end{definition}

\section{Théorème de stabilité des diagrammes de persistance}
\label{subsec:th-stab}

L'intérêt principal de la distance du goulot de bouteille est qu'elle permet d'énoncer simplement un résultat de stabilité, ou de robustesse,
associé aux diagrammes de persistance issus des sous-niveaux de fonctions continues à valeurs réelles.

\begin{theoreme}[Stabilité]
\label{th:stab}
Soit $X$ un complexe simplicial compact, et soient $f,g:X\to\R$ deux fonctions continues à valeurs réelles définies sur $X$.
Soient $D(f)$ et $D(g)$ les diagrammes de persistance obtenus à partir des filtrations issues des sous-niveaux
de $f$ et $g$. Alors, on a:
\begin{equation}
\bottleneckd(D(f), D(g)) \leq \|f-g\|_\infty,
\end{equation}
où $\|f-g\|_\infty:=\max\, \{|f(x)-g(x)|\mid x\in X\}$.
\end{theoreme}

Ce résultat est apparu pour la première fois
dans~\cite{Cohen-Steiner2007} et a ensuite donné lieu à plusieurs généralisations, notamment une version purement algébrique prouvée dans~\cite[\S\,5.6]{Chazal2016} et présentée un peu plus loin dans ce texte (théorème~\ref{thm:bottle-inter}). Comme nous le verrons, la version originale ci-dessus est un corollaire facile de la version algébrique.

Il est à noter que les distances de Wasserstein satisfont elles aussi à un théorème de stabilité, mais la borne supérieure est
plus difficile à énoncer, voir à ce sujet~\cite[Prop.\,5]{Mileyko2011}.
Ce théorème est d'une impor\-tance capitale au sein de la théorie de la persistance pour plusieurs raisons.

D'une part, il permet de formaliser la notion
d'importance attachée à la longueur des barres d'un code-barres (ou des distances à la diagonale d'un diagramme de persistance):
lorsque les fonctions ne diffèrent que légèrement, le théorème de stabilité impose aux diagrammes d'être proches au sens de la distance du goulot de bouteille,
ce qui en retour signifie qu'il existe deux sous-ensembles de points dans ces diagrammes dont les coordonnées sont similaires, et que les points restants
sont nécessairement près de la diagonale, de telle manière que leurs coûts ne pèsent pas trop sur la distance du goulot de bouteille. \emph{Les distances à la diagonale faibles
caractérisent donc les petites oscillations, tandis que le signal global se lit dans les points éloignés de la diagonale.}
Voir la figure~\ref{fig:stabilite}.

\begin{figure}[htb]
\centering
\includegraphics[width=0.8\textwidth]{stabilite}
\caption{\label{fig:stabilite} Deux fonctions continues définies sur (une triangulation de) la droite réelle, leurs codes-barres, et leurs diagrammes de persistance.
Comme ces deux fonctions sont proches en norme infinie, leurs diagrammes de persistance sont à distance du goulot de bouteille faible; en effet, ils ne diffèrent que via des points proches de la diagonale.}
\end{figure}

D'autre part, ce théorème a des répercussions directes en inférence géométrique et en statistique, que nous allons maintenant explorer.

\section{Application aux filtrations de {\v C}ech}
\label{subsec:stab-cech}

Une des applications les plus courantes de la théorie de la persistance est l'inférence géométrique sur des nuages de points, où la tâche consiste à identifier les structures géométriques
d'un espace topologique à partir d'un échantillonnage de cet espace uniquement. Cela peut permettre d'identifier que les données observées sont en réalité tirées sur un espace
qui a la topologie, par exemple, d'un tore, comme cela arrive couramment lorsque l'on travaille sur des données angulaires (puisqu'un tore n'est en définitive qu'un produit cartésien d'intervalles de la forme
$[0,2\pi]$). Voir par exemple la figure~\ref{fig:confiance}.
Une telle inférence permet ensuite de raffiner les modèles ou les descripteurs construits sur ces données, comme le montrent les nombreux modèles génératifs et prédictifs spécifiquement
optimisés pour traiter des données vivant sur des sphères, des tores, des espaces hyperboliques, etc.

Une technique courante pour caractériser la géométrie et la topologie d'un nuage de points consiste à étudier les sous-niveaux de la fonction distance au nuage, qui ensemble forment une filtration dont la version combinatoire est
appelée la filtration de {\v C}ech.

\begin{definition}
\label{def:fonction-distance}
Soit $P\subset\R^d$ un nuage de points fini (plus généralement un sous-espace compact) de $\R^d$. La \emph{fonction distance à $P$}, notée $f_P$, est définie par:
\[f_P:x\in\R^d\mto \min_{p\in P}\,\|x-p\|_2.\]
\end{definition}

La filtration induite par les sous-niveaux de $f_P$ est donc une filtration de $\R^d$ qui consiste à faire grossir des boules
centrées sur les points de $P$. Voir la figure~\ref{fig:union-boules}. En particulier, cette filtration permet de capturer des
structures topologiques et géométriques de $P$ à plusieurs échelles: en effet, les groupes d'homologie calculés sur l'union
des boules pour un rayon donné ne sont pas nécessairement isomorphes à ceux calculés pour un rayon plus petit ou plus grand.
En un sens, l'homologie persistante évite de devoir choisir et fixer un rayon en capturant les
groupes d'homologie à toutes les échelles, ou rayons, possibles, et en encodant les classes d'homologie qui persistent durant
certaines plages de rayons.

\begin{figure}[htb]
\centering
\includegraphics[width=0.3\textwidth]{balls2}
\includegraphics[width=0.3\textwidth]{balls3}
\includegraphics[width=0.3\textwidth]{balls4}
\caption{\label{fig:union-boules} Exemple de nuage de points dont la topologie de l'union des boules change en fonction du rayon: pour des rayons faibles,
l'union des boules a la même topologie que plusieurs lettres \og B\fg (gauche), pour des rayons plus grands, la topologie de l'union est celle
d'une seule lettre \og A\fg (milieu), et pour des rayons extrêmes, l'union est formée d'une seule composante connexe sans autre structures topologiques particulières.}
\end{figure}

Bien que théoriquement satisfaisante, il est évidemment impossible de filtrer complètement l'espace euclidien $\R^d$ en pratique.
Heureusement, on peut démontrer\footnote{La preuve utilise un résultat important appelé le \emph{théorème du nerf}.} que les sous-niveaux de $f_P$ ont les mêmes groupes d'homologie que les complexes simpliciaux issus d'une
filtration calculable qui s'appelle la \emph{filtration de {\v C}ech}.

\begin{definition}
Soit $P=\{x_1,\dots,x_n\}\subset\R^d$ un nuage de points fini de~$\R^d$.
La filtration de {\v C}ech associée à $P$ est la filtration
\[
\{\Delta_n^{P,\mathrm{Cech}}(r)\mid r\geq 0\}
\]
du simplexe complet
$\Delta^P_n$ à $n=|P|$ sommets identifiés bijectivement
aux points de $P$, définie, pour tout simplexe $\sigma\in \Delta_n^P$, par:
\[\sigma=\{x_{i_1},\dots,x_{i_k}\} \in \Delta_n^{P,\mathrm{Cech}}(r) \iff \bigcap_{j=1}^k B(x_{i_j},r)\neq\varnothing,\]
où $B(x,r):=\{y\in\R^d\mid \|x-y\|\leq r\}$ désigne la boule euclidienne de rayon $r$.
Le diagramme de persistance associé est noté $\DCech(P)$.
\end{definition}

Voir la figure~\ref{fig:cech-rips}.
Le diagramme de persistance de {\v C}ech permet donc de fournir une estimation de la topologie d'un espace à partir seulement de complexes simpliciaux calculés sur un nuage de points issu de cet espace.

De plus, étant donnés deux nuages de points $P$ et $P'$, une application directe du théorème de stabilité permet d'obtenir:
\[\bottleneckd(\DCech(P), \DCech(P')) = \bottleneckd(D(f_P), D(f_{P'}))\leq \|f_P-f_{P'}\|_\infty.\]
La raison pour laquelle ce résultat est important est qu'il permet de relier les diagrammes de {\v C}ech à une distance très utile
en géométrie, la \emph{distance de Hausdorff}.

\begin{definition}
\label{def:hausdorff}
Soient $X,Y$ deux sous-espaces compacts de $\R^d$. La~\emph{distance de Hausdorff} entre $X$ et $Y$
est définie par:
\[
\hausd(X,Y):= \max\, \{ \max\,\{f_Y(x)\mid x\in X\}, \max\,\{f_X(y)\mid y\in Y\}\},
\]
où $f_X, f_Y$ sont définies comme à la définition~\ref{def:fonction-distance}.
\end{definition}

\begin{lemme}
Soient $X,Y$ deux sous-espaces compacts de $\R^d$. Alors, on~a:
\[\hausd(X,Y)=\|f_X-f_Y\|_\infty.\]
\end{lemme}

\begin{proof} Montrons d'abord que $\hausd(X,Y)\leq \|f_X-f_Y\|_\infty$.
Supposons que $\hausd(X,Y)$ soit atteinte par un certain $x^*\in X$.
Alors, on~a:
\[
\begin{aligned}
\hausd(X,Y) & = f_Y(x^*) \\
& = f_Y(x^*) - f_X(x^*) \\
& \leq |f_Y(x^*)-f_X(x^*)| \\
& \leq \|f_Y-f_X\|_\infty.
\end{aligned}
\]
Le même argument peut être appliqué au cas où $\hausd(X,Y)$ est atteinte par un certain $y^*\in Y$, en intervertissant simplement $X$ et $Y$.

Montrons maintenant que $\hausd(X,Y)\geq \|f_X-f_Y\|_\infty$. Soit $z\in\R^d$.
Alors, on a:
\[
\begin{aligned}
f_X(z)-f_Y(z) & = \|z-\pi_X(z)\|_2-\|z-\pi_Y(z)\|_2 \\
& \leq \|z-\pi_X(\pi_Y(z))\|_2 - \|z-\pi_Y(z)\|_2 \\
& \leq \|\pi_X(\pi_Y(z))-\pi_Y(z)\|_2 \text{ par l'inégalité triangulaire}\\
& = f_X(\pi_Y(z)) \\
& \leq \sup\,\{f_X(y)\mid y\in Y\} \\
& \leq \hausd(X,Y).
\end{aligned}
\]
La même séquence d'inégalités peut être appliquée pour borner $f_Y(z)-f_X(z)$, en intervertissant simplement $X$ et $Y$.
Ceci permet d'obtenir $|f_X(z)-f_Y(z)| \leq \hausd(X,Y)$ pour tout $z\in\R^d$, et donc $\|f_X-f_Y\|_\infty \leq \hausd(X,Y)$.
\end{proof}

Ce lemme permet d'obtenir le résultat suivant, dont nous allons observer les retombées statistiques dans la section suivante.
\begin{corollaire}
\label{cor:cech-stab}
Soient $X$ un sous-espace compact de $\R^d$, et $\hat X_n\subset X$ un échantillonnage de $X$ à $n$ points.
Alors, on a:
\[\bottleneckd(D(f_X), \DCech(\hat X_n)) \leq \hausd(X,\hat X_n).\]
\end{corollaire}

\section{Inférence géométrique et intervalles de confiance}
\label{subsec:inference-geom}

De manière générale, étant donné un estimateur $\hat\theta_n$ d'une quantité cible $\theta^*$ associée à une distribution de probabilité (comme, par exemple, sa moyenne),
et calculé sur un échantillon de $n$ points issu de cette distribution, une question centrale de
la statistique consiste à construire des \emph{intervalles de confiance}
pour celui-ci, c'est-à-dire, pour un seuil de confiance $\alpha\in [0,1]$ donné, de trouver $d_\alpha > 0$ tel que $\proba(|\hat\theta_n-\theta^*| > d_\alpha)\leq \alpha$. L'inférence géométrique consiste ainsi à calculer des estimateurs pour déterminer (avec un certain niveau de probabilité) la topologie du support de certaines distributions de probabilité.
Supposons par exemple que ce support soit un sous-espace compact $X$ de $\R^d$, et que sa topologie soit caractérisée par $D(f_X)$.
Un estimateur possible, suggéré par le corollaire \ref{cor:cech-stab}, est donc $\DCech(\hat X_n)$. De plus, ce corollaire permet de transférer le calcul d'intervalles de confiance pour
$\bottleneckd(D(f_X), \DCech(\hat X_n))$ à celui d'intervalles de confiance pour $\hausd(X,\hat X_n)$. En effet, en supposant connu un certain $d_\alpha$ associé à un seuil de confiance $\alpha$ pour
$\hausd(X,\hat X_n)$, il s'ensuit trivialement du corollaire~\ref{cor:cech-stab} que
\[\proba(\bottleneckd(D(f_X), \DCech(\hat X_n)) > d_\alpha) \leq \proba(\hausd(X,Y) > d_\alpha) \leq \alpha.\]

En outre, la distance de Hausdorff est un objet bien connu en inférence géométrique, car elle caractérise à quel point un échantillonnage est uniforme --- voir sur ce point la figure~\ref{fig:hausdorff},
et ses intervalles de confiance sont faciles à obtenir pour des mesures de probabilité appelées mesures $(a,b)$-standard.

Dans cette section, nous allons donc présenter quelques résultats d'inférence géométrique via la distance de Hausdorff, et leur utilisation pour
les diagrammes de persistance. Ces résultats sont tirés et adaptés de~\cite{Chazal2015b, Fasy2014}, que l'on pourra consulter pour une exposition et des preuves plus détaillées.

\begin{figure}[htb]
\centering
\includegraphics[width=.5\textwidth]{hausdorff}
\caption{\label{fig:hausdorff} Exemple de calcul de la distance de Hausdorff sur deux échantillonnages d'une sphère. Sur l'échantillon de gauche, la distance est faible car n'importe
quel point de la sphère (comme celui représenté par une croix) est proche d'au moins un point de l'échantillon. Au contraire, pour l'échantillon de droite, il existe des points de la sphère
pour lesquels le point de l'échantillon le plus proche reste quand même très éloigné.}
\end{figure}

\begin{definition}
Soit $\mu$ une mesure de probabilité à support compact $X\subset \R^d$. Soient $a,b >0$ deux réels positifs.
La mesure $\mu$ est appelée $(a,b)$-standard si on a, pour tout $x\in X$ et $r>0$:
\[\mu(B(x,r))\geq \min\,\{1, ar^b\}.\]
\end{definition}

L'intérêt des mesures $(a,b)$-standards est qu'elles permettent de contrôler des quantités
aisément reliables à la distance de Hausdorff entre le support et un échantillon de celui-ci,
dénommées \emph{nombre de recouvrement} (\emph{covering number} en anglais) et \emph{nombre de stockage} (\emph{packing number} en anglais).

\begin{definition}
Soit $X$ un sous-espace compact de $\R^d$ et $r>0$.
Le \emph{nombre de recouvrement} de $X$ de rayon $r$ est défini par:
\begin{multline*}
\covering(X,r):=\min\,\{k\in\N^*\mid \exists (x_1,\dots,x_k)\in X^k\\ \text{ tels que }X \subseteq\textstyle \bigcup_{i=1}^k B(x_i,r)\}.
\end{multline*}
Le \emph{nombre de stockage} de $X$ est défini par:
\[
\begin{aligned}
\packing(X,r):=\max\,\{k\in\N^*\mid \exists & (x_1,\dots,x_k)\in X^k \text{ tels que } \\
& \forall 1\leq i\leq k, B(x_i,r)\subseteq X \text{ et } \\
& \forall 1\leq i\neq j\leq k, B(x_i,r)\cap B(x_j,r)=\varnothing\}.
\end{aligned}
\]
\end{definition}

Le nombre de recouvrement de rayon $r$ est donc le nombre minimal de boules de rayon $r$ avec lesquelles on peut entièrement couvrir $X$,
tandis que le nombre de stockage de rayon $r$ est le nombre maximal de boules de rayon $r$ que l'on peut arranger dans $X$ sans qu'elles ne
s'intersectent. Ces deux quantités sont reliées de la manière suivante:

\begin{lemme}
Soit $X$ un sous-espace compact de $\R^d$ et $r>0$. Alors, on~a:
\[\covering(X,2r)\leq \packing(X,r).\]
\end{lemme}

\begin{proof}
Soit $k\in\N^*$ un entier réalisant le nombre de stockage, et $c_1,\dots,c_k$ les centres des boules correspondantes.
Supposons par l'absurde que $\bigcup_{i=1}^k B(c_i,2r)$ ne recouvre pas $X$. Il existe donc un certain $x\in X$ tel
que $x \not\in \bigcup_{i=1}^k B(c_i,2r)$, c'est-à-dire tel que $\|x-c_i\|_2 > 2r$ pour tout $1\leq i \leq k$.
Il s'ensuit que la boule $B(x,r)$ n'intersecte aucune des boules $B(c_i,r)$ (sinon la distance $\|x-c_i\|_2$ serait inférieure à $2r$
par l'inégalité triangulaire), et donc que l'on peut augmenter le nombre de stockage d'une unité. C'est une contradiction, car ce nombre est
maximal.
Ainsi, $\bigcup_{i=1}^k B(c_i,2r)$ recouvre entièrement $X$, d'où l'on peut tirer l'inégalité désirée.
\end{proof}

Pour les mesures $(a,b)$-standards, on peut facilement borner supérieurement le nombre de stockage et le nombre de recouvrement.

\begin{lemme}
\label{lem:bound-pack}
Soit $\mu$ une mesure $(a,b)$-standard de support compact $X\subset\R^d$.
Alors
\[
\covering(X,2r) \leq \packing(X,r) \leq \max\,\{1,1/(ar^b)\}.
\]
\end{lemme}

\begin{proof}
Le résultat étant trivial pour $r\geq a^{-1/b}$, on suppose que $r < a^{-1/b}$. Soit $k\in\N^*$ un entier réalisant le nombre
de stockage, et $c_1,\dots,c_k$ les centres des boules correspondantes. On a donc
\[
\begin{aligned}
k \cdot a r^b & \leq \sum_{i=1}^k \mu\left(B(c_i,r)\right) \\
& = \mu\Bigl(\bigcup_{i=1}^k B(c_i,r)\Bigr) \text{ car les boules sont disjointes} \\
& \leq 1.
\end{aligned}
\]
Les inégalités recherchées découlent directement de la séquence.
\end{proof}

On peut finalement utiliser le nombre de recouvrement pour le calcul des intervalles de confiance de la distance de Hausdorff,
et~obtenir le résultat suivant:

\begin{proposition}
\label{prop:confiance}
Soit $\mu$ une mesure $(a,b)$-standard de support compact $X\subset\R^d$.
Soit $\hat X_n$ un échantillonnage de $X$ à $n$ points. Soit $d_\alpha > 0$. Alors on a:
\[\proba(\hausd(X,\hat X_n) > d_\alpha) \leq \min\,\Bigl\{1,\frac{4^b}{a d_\alpha^b} \exp(-na\cdot (d_\alpha/2)^b)\Bigr\}.\]
\end{proposition}

\begin{proof}
Cette preuve passe par une formulation équivalente de la distance de Hausdorff, que l'on laisse en exercice au lecteur:

\begin{exercice}
Montrer que:
\[\textstyle
\hausd(X,\hat X_n)=\inf\{\varepsilon > 0\mid X\subseteq \bigcup_{\hat x\in \hat X_n} B(\hat x, \varepsilon)\}.\]
\end{exercice}

On a donc
\[\textstyle\proba(\hausd(X,\hat X_n) > d_\alpha) = \proba(\sup_{x\in X}\, \min_{\hat x \in \hat X_n} \|x-\hat x\|_2 > d_\alpha).\]
Soit $k\in\N^*$ un entier réalisant le nombre de recouvrement de rayon $d_\alpha/2$,
et $c_1,\dots,c_k$ les centres des boules correspondantes.
De plus, pour tout $x\in X$, soit $c_x\in\{c_1,\dots,c_k\}$ le centre tel que $x\in B(c_x,d_\alpha/2)$. On a:
\[
\begin{aligned}
\min_{\hat x \in \hat X_n} \|x-\hat x\|_2 & \leq \|x-\hat x_i\|_2\leq \|x-c_x\|_2 + \|c_x-\hat x_i\|_2, 1\leq i\leq n, \\
& \leq \|x-c_x\|_2 + \max_{1\leq j\leq k} \min_{\hat x\in \hat X_n} \|c_j-\hat x\|_2 \\
& \leq d_\alpha/2 + \max_{1\leq j\leq k} \min_{\hat x\in \hat X_n} \|c_j-\hat x\|_2
\end{aligned}
\]
Ainsi on obtient
\[\sup_{x\in X}\min_{\hat x \in \hat X_n} \|x-\hat x\|_2 \leq d_\alpha/2 + \max_{1\leq j\leq k} \min_{\hat x\in \hat X_n} \|c_j-\hat x\|_2,\]
et donc
\[\textstyle\proba(\hausd(X,\hat X_n) > d_\alpha)\leq \proba(\max_{1\leq j\leq k} \min_{\hat x\in \hat X_n} \|c_j-\hat x\|_2 > d_\alpha/2).\]

La probabilité $\proba(\max_{1\leq j\leq k} \min_{\hat x\in \hat X_n} \|c_j-\hat x\|_2 > d_\alpha/2)$ est la probabilité
qu'il existe un centre pour lequel tous les points de l'échantillon sont à distance au moins $d_\alpha/2$. Ainsi, si l'on
note $E_{j,i}$ l'événement $\{\hat x_i \in B(c_j,d_\alpha/2)\}$, on a:
\[
\begin{aligned}
{\textstyle\proba(\max_{1\leq j\leq k} \min_{\hat x\in \hat X_n} \|c_j-\hat x\|_2 > d_\alpha/2)} & = \textstyle\proba\left(\bigcup_{j=1}^k \bigcap_{i=1}^n E_{j,i}^c\right) \\
\leq \sum_{j=1}^k {\textstyle\proba\left(\bigcap_{i=1}^n E_{j,i}^c\right)} & = \sum_{j=1}^k \left[1-\mu(B(c_j,d_\alpha/2))\right]^n \\
& \leq k\cdot\bigl[1-a(d_\alpha/2)^b\bigr]^n.
\end{aligned}
\]
Sachant que $k=\covering(X,d_\alpha/2)\leq \sfrac{4^b}{ad_\alpha^b}$ d'après le lemme~\ref{lem:bound-pack}, et~en utilisant l'inégalité
$(1-x)^n\leq \exp(-nx)$ pour tout $x\in [0,1]$, on~obtient le résultat désiré.
\end{proof}

La proposition~\ref{prop:confiance} peut ensuite être utilisée pour le calcul de la \emph{vitesse de convergence}, c'est-à-dire du calcul de l'espérance
$\mathbb{E}\left[\bottleneckd(D(f_X),\DCech(\hat X_n))\right]$,
via l'identité $\mathbb{E}[d]=\int_\alpha \proba(d\geq \alpha)\mathrm{d}\alpha$, pour toute variable aléatoire $d$ positive. En outre,
il est même possible de démontrer que $\DCech(\hat X_n)$ est un estimateur \emph{optimal}, au sens où il n'existe pas d'estimateur de $D(f_X)$
dont la vitesse de convergence soit meilleure.

La proposition~\ref{prop:confiance} est néanmoins limitée par la nécessité de connaître $a$ et $b$ pour pouvoir calculer des intervalles de confiance.
Bien que l'on ne connaisse pas forcément leurs valeurs \emph{a priori}, il est toutefois possible de les estimer numériquement. Une fois calculés, les intervalles de confiance peuvent être ensuite visualisés directement sur les diagrammes de persistance, comme
montré dans la figure~\ref{fig:confiance}.

\begin{figure}[p]
\centering
\includegraphics[width=.9\textwidth]{arm.pdf}
\caption{\label{fig:confiance}
Deux exemples d'inférence géométrique sur des données réelles. Dans la première (\emph{haut}), différentes configurations d'un bras robotique sont collectées. Une configuration
étant caractérisée par les deux angles aux jointures, les données vivent sur un tore. Dans la deuxième (\emph{bas}), des cellules, ainsi que l'expression de leurs gènes, ont été prélevées à différentes phases du
cycle cellulaire, les données vivent donc sur un cercle (plongé dans $\R^{\#\text{gènes}}$).
Dans chacun des deux cas,
on peut calculer le diagramme de {\v C}ech, et, pour un seuil de confiance $\alpha$ donné (dans cette figure, $\alpha=0.05\%$),
visualiser les points correspondants à du bruit (dû par exemple à l'échantillonnage)
via une bande de hauteur $2d_\alpha$ au-dessus de la diagonale.
On voit que les points caractéristiques de la géométrie des espaces sous-jacents (deux points en dimension $1$ et un point en dimension $0$ pour le tore, un point en dimension $0$ et un point en dimen\-sion $1$ pour le cercle)
sont bien situés en dehors de la bande: ils sont sûrs à $95\%$.}
\end{figure}

\section{Théorème de stabilité des modules de persistance}
\label{subsec:module-dist}

La stabilité des diagrammes de persistance, telle que présentée en section~\ref{subsec:th-stab}, découle en réalité d'une formulation algébrique de la stabilité (théorème~\ref{thm:bottle-inter} ci-dessous),
qui, elle, s'énonce au niveau des modules de persistance via la \emph{distance d'entrelacement}.

\begin{definition}
Soient
\[
M=\{\{M_t\}_{t\in\R},\{m_{t,t'}\}_{t\leq t'\in\R}\}\quand M'=\{\{M'_t\}_{t\in\R},\{m'_{t,t'}\}_{t\leq t'\in\R}\}
\]
deux modules de persistance indexés sur $\R$. Soit $\eps > 0$. Les modu\-les~$M$ et~$M'$ sont \emph{$\eps$-entrelacés} si et seulement si il existe
deux familles d'applications linéaires
\[
\{\phi_t:M_t\to M'_{t+\eps}\mid t\in\R\}\quand \{\psi_t:M'_t\to M_{t+\eps}\mid t\in\R\}
\]
telles que les diagrammes suivants commutent pour tout $t \leq t'\in\R$:
\[
\begin{aligned}
\begin{tikzcd}
M_t \arrow[rr, "m_{t,t+2\eps}"]\arrow[rd, "\phi_t"] & & M_{t+2\eps} \\
& M'_{t+\eps}\arrow[ru, "\psi_{t+\eps}"] &
\end{tikzcd}
& \begin{tikzcd}
M'_t \arrow[rr, "m'_{t,t+2\eps}"]\arrow[rd, "\psi_t"] & & M'_{t+2\eps} \\
& M_{t+\eps}\arrow[ru, "\phi_{t+\eps}"] &
\end{tikzcd}
\\
\begin{tikzcd}
M_t \arrow[r, "m_{t,t'}"]\arrow[d, "\phi_t"] & M_{t'}\arrow[d, "\phi_{t'}"] \\
M'_{t+\eps}\arrow[r, "m'_{t+\eps, t'+\eps}"] & M'_{t'+\eps}
\end{tikzcd}
& \begin{tikzcd}
M'_t \arrow[r, "m'_{t,t'}"]\arrow[d, "\psi_t"] & M'_{t'}\arrow[d, "\psi_{t'}"] \\
M_{t+\eps}\arrow[r, "m_{t+\eps, t'+\eps}"] & M_{t'+\eps}
\end{tikzcd}
\end{aligned}
\]

La \emph{distance d'entrelacement} entre $M$ et $M'$ est alors définie comme suit:
\[\interleavingd(M,M'):= \inf\,\{\eps > 0\mid M,M'\text{ sont }\eps\text{-entrelacés}\}.\]
\end{definition}

Lorsque les modules de persistance sont pdf, et donc que l'on peut calculer leurs diagrammes de persistance, on peut montrer que
la distance d'entrelacement est en fait égale à la distance du goulot de bouteille.

\begin{theoreme}[Stabilité algébrique]
\label{thm:bottle-inter}
Soient $M,M'$ deux modules de persistance pdf, et $D(M),D(M')$ les diagrammes de persistance correspondants. Alors, on a:
\[\bottleneckd(D(M),D(M')) = \interleavingd(M,M').\]
\end{theoreme}

Une preuve complète de ce résultat est donnée dans~\cite[\S\,5.4]{Chazal2016}. Ici nous nous contenterons d'une preuve simple démontrant un résultat moins fort mais suffisant pour nos besoins, à savoir que $\bottleneckd(D(M),D(M')) \leq 8\, \interleavingd(M,M')$.

\begin{proof}
Soit $\e>\interleavingd(M,M')$. On discrétise le module~$M$ sur la grille $2\e\Z = \{2k\e \mid k\in\Z\}$, c'est-à-dire que l'on forme le module $\bar M=(M_t)_{t\in 2\e\Z}$ avec les applications linéaires internes induites de~$M$. Comme $M$ est pdf, il se décompose en une somme directe de modules intervalles: $M\cong \bigoplus_{j\in \mathcal{J}} \field_{I_j}$. On a alors $\bar M \cong \bigoplus_{j\in \mathcal{J}} \field_{I_j\cap 2\e\Z}$, par les définitions point à point de l'isomorphisme et de la somme directe données dans le texte~\cite{chap-pers-1} (notons que l'on peut avoir \hbox{$I_j\cap 2\e\Z =\emptyset$}, auquel cas le facteur $\field_{I_j}$ devient nul après discrétisation). Il~s'ensuit que $\bottleneckd(D(M), D(\bar M)\leq 2\e$.

De même, on discrétise $M'$ sur la grille $\e+2\e\Z = \{\e+2k\e \mid k\in\Z\}$ en formant le module $\bar M'=(M'_t)_{t\in \e+2\e\Z}$ avec les applications linéaires internes induites de~$M'$, et l'on a alors $\bottleneckd(D(M'), D(\bar M')\leq 2\e$.

Comme $\e>\interleavingd(M,M')$, il existe un $\e$-entrelacement de $M$ et $N$ par des familles d'applications
\[
(\phi_t\colon M_t\to M'_{t+\e})_{t \in \R}\quand(\psi_t\colon M'_t\to M_{t+\e})_{t \in \R}.
\]
Cet entrelacement nous donne le diagramme commutatif suivant, où la première ligne est le module discrétisé~$\bar M$ et la deuxième ligne est l'autre module discrétisé~$\bar M'$:
\[
\adjustbox{scale=.75,center}{
\begin{tikzcd}
\cdots\arrow[r,""] & M_{(2k-2)\eps} \arrow[rr, "m_{(2k-2)\eps,2k\eps}"]\arrow[rd, "\phi_{(2k-2)\eps}"] & & M_{2k\eps}\arrow[rr, "m_{2k\eps,(2k+2)\eps}"]\arrow[rd, "\phi_{2k\eps}"] & & M_{(2k+2)\eps}\arrow[r,""] & \cdots \\
& \cdots\arrow[r,""] & M'_{(2k-1)\eps}\arrow[rr, "m'_{(2k-1)\eps, (2k+1)\eps}"]\arrow[ru, "\psi_{(2k-1)\eps}"] & & M'_{(2k+1)\eps}\arrow[ru, "\psi_{(2k+1)\eps}"]\arrow[r,""] & \cdots &
\end{tikzcd}
}
\]
Considérons maintenant le module~$N$ formé par la suite d'applications diagonales dans ce diagramme. Plus précisément, on définit $(N_t)_{t\in\e\Z}$ avec $N_{2k\e} = M_{2k\e}$ et $N_{\e+2k\e} = M'_{\e+2k\e}$, reliés par les applications internes $\phi_{2k\e}\colon N_{2k\e}\to N_{\e+2k\e}$ et $\psi_{\e+2k\e}\colon N_{\e+2k\e}\to N_{(2k+2)\e)}$. Par commutativité du diagramme, $\bar M$ est aussi la discrétisation de~$N$ sur la grille~$2\e\Z$, tandis que $\bar M'$ est aussi la discrétisation de~$N$ sur la grille~$\e+2\e\Z$. Comme plus haut, on a donc $\bottleneckd(D(N), D(\bar M))\leq 2\e$ et $\bottleneckd(D(N), D(\bar M'))\leq 2\e$. L'inégalité triangulaire nous donne alors:
\begin{multline*}
\bottleneckd(D(M), D(M'))
\leq \bottleneckd(D(M),D(\bar M)) + \bottleneckd(D(\bar M) , D(N)) \\
+ \bottleneckd(D(N),D(\bar M')) + \bottleneckd(D(\bar M'),D(M')) \leq 8\eps.
\end{multline*}
Comme cette inégalité large est vraie pour tout $\e>\interleavingd(M,M')$, elle l'est également pour $\e=\interleavingd(M,M')$, d'où le résultat.
\end{proof}

\begin{remarque}
Dans la preuve du théorème nous avons considéré les diagrammes de persistances de modules définis seulement sur des grilles dans~$\R$, et pas sur $\R$ tout entier. Cela requiert de choisir une convention pour définir les bornes des intervalles, qui ne sont autrement pas définies de manière unique. Par exemple, sur la grille $2\e\Z$, pour tous $k\leq k'\in\Z$ on a
\begin{align*} \{2k\e, 2(k+1)\e,\cdots, 2k'\e\} &= [2k\e, 2k'\e]\ \cap\ 2\e\Z\\
&= [2k\e, (2k'+1)\e[\ \cap\ 2\e\Z\\
&={} ](2k-1)\e, (2k'+1)\e[\ \cap\ 2\e\Z\\
&={} ](2k-1)\e, 2k'\e]\ \cap\ 2\e\Z
\end{align*}
On a donc quatre conventions possibles pour définir les bornes des intervalles. Le choix de convention n'a pas d'influence sur la preuve, car toutes donnent l'inégalité $\bottleneckd(M, \bar M)\leq 2\e$ pour tout module pdf~$M$ indexé sur~$\R$ (ou sur une grille plus fine comme $\e\Z$, munie de la même convention) et son discrétisé~$\bar M$ sur la grille~$2\e\Z$.
\end{remarque}

L'intérêt de la stabilité algébrique (théorème~\ref{thm:bottle-inter}) est de s'affranchir complètement du cadre fonctionnel du théorème de stabilité usuel (théorème~\ref{th:stab}). Ce dernier en est d'ailleurs un corollaire facile. En~effet, si l'on considère deux fonctions $f,g:X\to\R$ définies sur un complexe simplicial compact, et que l'on se donne n'importe quel $\eps>\|f-g\|_\infty$, on a aisément
\[f^{-1}((-\infty,t])\subseteq g^{-1}((-\infty,t+\eps])\]
et
\[g^{-1}((-\infty,t])\subseteq f^{-1}((-\infty,t+\eps]),\]
pour tout $t\in\R$. La fonctorialité de l'homologie permet ensuite de direc\-tement déduire des applications linéaires associées aux inclusions ci-dessus,
et donc un $\eps$-entrelacement entre les modules de persistance $M(f)$ et $M(g)$ issus des sous-niveaux de $f$ et $g$. Ceci permet finalement d'obtenir:
\[\bottleneckd(D(f),D(g))=\interleavingd(M(f),M(g))\leq \|f-g\|_\infty\]
(ou bien $\bottleneckd(D(f),D(g))\leq 8\interleavingd(M(f),M(g))\leq 8\|f-g\|_\infty$ si l'on passe par la version faible démontrée ici).

\bigskip

Un autre avantage de la distance d'entrelacement est qu'elle permet parfois de contrôler simplement la proximité entre deux modules de persistance issus de
filtrations spécifiques, et donc aussi entre leurs diagrammes de persistance (via le théorème~\ref{thm:bottle-inter}).
Une illustration classique de cet avantage concerne les diagrammes de {\v C}ech, définis en section~\ref{subsec:stab-cech}.
En effet, en pratique, le calcul effectif de diagrammes de {\v C}ech est souvent coûteux (même si possible via l'utilisation de complexes simpliciaux spécifiques appelés complexes alpha).
On préfère donc souvent calculer une approximation facilement calculable de la filtration de {\v C}ech, appelée \emph{filtration de Vietoris-Rips}.

\begin{definition}
Soit $P=\{x_1,\dots,x_n\}\subset\R^d$ un nuage de points fini de $\R^d$.
La filtration de Vietoris-Rips associée à $P$ est la filtration $\{\Delta_n^{P,\mathrm{Rips}}(r)\mid r\geq 0\}$ du simplexe complet
$\Delta^P_n$ à $n=|P|$ sommets identifiés bijectivement
aux points de $P$, définie, pour tout simplexe $\sigma\in \Delta_n^P$, par:
\[\sigma=\{x_{i_1},\dots,x_{i_k}\} \in \Delta_n^{P,\mathrm{Rips}}(r) \iff \|x_{i_j}-x_{i_{j'}}\|_2 \leq r, \forall 1\leq j,j'\leq k.\]
Le diagramme de persistance associé est noté $\DRips(P)$.
\end{definition}

\begin{lemme}
Soit $r\geq 0$. Alors, on a les inclusions suivantes entre complexes simpliciaux:
\[\Delta_n^{P,\mathrm{Rips}}(r) \subseteq \Delta_n^{P,\mathrm{Cech}}(r) \subseteq \Delta_n^{P,\mathrm{Rips}}(2r).\]
\end{lemme}

\begin{proof}
Soit $r\geq 0$. Montrons la première inclusion. Soit $\sigma=\{x_{i_1},\dots,x_{i_k}\}$ un $k$-simplexe de $\Delta_n^{P,\mathrm{Rips}}(r)$.
Alors, pour tout $1\leq j\leq k$, on a $\|x_{i_1}-x_{i_j}\|_2 \leq r$ et donc $x_{i_1}\in B(x_{i_j},r)$. Ainsi $x_{i_1}\in\bigcap_{j=1}^k B(x_{i_j},r)$ et $\sigma\in\Delta_n^{P,\mathrm{Cech}}(r)$.

Montrons maintenant la deuxième inclusion. Soit $\sigma=\{x_{i_1},\dots,x_{i_k}\}$ un $k$-simplexe de $\Delta_n^{P,\mathrm{Cech}}(r)$.
Alors, pour tout $1\leq j,j'\leq k$, on a $B(x_{i_j},r)\cap B(x_{i_{j'}},r)\neq\varnothing$. Soit $z\in B(x_{i_j},r)\cap B(x_{i_{j'}},r)$. Alors, par l'inégalité triangulaire, on a:
\[\|x_{i_j}-x_{i_{j'}}\|_2\leq\|x_{i_j}-z\|_2 +\|z-x_{i_{j'}}\|_2\leq 2r,\]
et donc $\sigma \in \Delta_n^{P,\mathrm{Rips}}(2r)$.
\end{proof}

Voir la figure~\ref{fig:cech-rips}.

\begin{figure}[htb]
\centering
\includegraphics[width=.8\textwidth]{cech}
\caption{\label{fig:cech-rips} Exemple de nuage de points et de boules de rayon $r$ centrées sur les points (\emph{gauche}),
son complexe de {\v C}ech de rayon $r$ (\emph{centre}), et son complexe de Vietoris-Rips de rayon $2r$ (\emph{droite}). On peut voir
que le complexe de Vietoris-Rips contient un simplexe supplémentaire: en effet, il suffit pour les complexes de Vietoris-Rips que toutes
les paires de points aient une distance inférieure au rayon pour pouvoir ajouter le simplexe correspondant.}
\end{figure}

La fonctorialité de l'homologie permet donc d'obtenir directement le corollaire suivant:

\begin{corollaire}
Soit $P=\{x_1,\dots,x_n\}\subset\R^d$ un nuage de points fini de~$\R^d$.
Soit $\DCech^{\log}(P)$ et $\DRips^{\log}(P)$ les logarithmes\footnote{Ces logarithmes sont bien définis car les coordonnées des points des diagrammes de {\v C}ech et Vietoris-Rips
sont positives par définition.}
des diagrammes de {\v C}ech et Vietoris-Rips correspondants:
\[\DCech^{\log}(P):=\{(\log(p_x),\log(p_y))\in\R^2\mid (p_x,p_y)\in\DCech(P)\},\]
\[\DRips^{\log}(P):=\{(\log(p_x),\log(p_y))\in\R^2\mid (p_x,p_y)\in\DRips(P)\}.\]
Alors, on a:
\[\bottleneckd(\DCech^{\log}(P), \DRips^{\log}(P))\leq \log(2).\]
\end{corollaire}

\backmatter
\bibliographystyle{jepalpha+eid}
\bibliography{xups24-04}
\end{document}