<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[XUPS,XML,SOM,Unicode,francais, NoFloatCountersInSection]{cedram}
\setcounter{tocdepth}{1}

\usepackage{../xups24}
\graphicspath{{xups24-03_figures}}

\usepackage[french,onelanguage,ruled,shortend,algosection,norelsize]{algorithm2e}
\SetAlTitleFnt{textsc}
\SetKwSty{texttt}
\SetAlgoLined
\let\code\textsf

\hyphenation{topo-lo-gi-que appli-ca-tion appli-ca-tions inter-nes dÃ©fi-ni-tion direc-te autre-ment modu-les dimen-sion inter-val-le degrÃ©}

%\XUPScorrections

\begin{document}
\frontmatter

\title{ThÃ©orie de la persistance (1/2): structure}

\author{\firstname{Steve} \lastname{Oudot}}
\address{Inria Saclay - Ile-de-France \&amp; Ã‰cole polytechnique,
BÃ¢t. Alan Turing,
1 rue HonorÃ© d'Estienne d'Orves,
91120 Palaiseau}
\email{steve.oudot@inria.fr}
\urladdr{https://geometrica.saclay.inria.fr/team/Steve.Oudot/}

%\thanks{JournÃ©es X-UPS 2024. Introduction Ã&nbsp; l'analyse de donnÃ©es. Ã‰ditions de l'Ã‰cole polytechnique, 2024}

\begin{abstract}
Dans ce texte nous utilisons lâ€™homologie pour introduire formellement la thÃ©orie de la persistance, notamment dans ses \hbox{aspects} algÃ©briques. Nous prÃ©sentons ses principaux objets dâ€™Ã©tude, appelÃ©s modules de persistance, et nous Ã©tudions leurs propriÃ©tÃ©s de dÃ©composition. Ces dÃ©compositions forment la base des descripteurs utilisÃ©s en analyse topologique de donnÃ©es, appelÃ©s codes-barres ou diagrammes de persistance.\end{abstract}
\maketitle

\tableofcontents
\mainmatter

La thÃ©orie de la persistance s'applique Ã&nbsp; deux niveaux en parallÃ¨le: au niveau topologique, sur des filtrations d'espaces topologiques; au~niveau algÃ©brique, sur les modules induits en homologie, appelÃ©s \emph{modules de persistance}. Le c\oe ur de la thÃ©orie se situe au niveau algÃ©brique et les modules de persistance sont son principal objet d'Ã©tude. Dans ce texte on s'attachera essentiellement Ã&nbsp; leurs propriÃ©tÃ©s de dÃ©composition et au calcul des \emph{codes-barres} induits, tandis que dans le texte suivant on regardera leurs propriÃ©tÃ©s de stabilitÃ©.

Dans ce texte on fixe un corps~$\field$ et un ensemble totalement ordonnÃ©~$(T, \leq)$.

\section{Filtrations d'espaces topologiques}
Rappelons d'abord le concept classique de filtration d'espaces topologiques et donnons quelques exemples clÃ©s pour l'analyse topologique de donnÃ©es.

\begin{definition}\label{def:filt}
Une \emph{filtration} d'espaces topologiques indexÃ©e par~$T$ est une famille $(X_t)_{t\in T}$ d'espaces topologiques imbriquÃ©s au sens que $X_t\subseteq X_{t'}$ pour tous $t\leq t'\in T$.
\end{definition}

\begin{exemple}\label{ex:filt-sublevel}
Ã‰tant donnÃ© un espace topologique~$X$ et une fonction $f\colon X\to\R$, tous deux quelconques, la famille des \emph{sous-niveaux} $F_t=f^{-1}\left( ]-\infty, t]\right)$ forme une filtration indexÃ©e par~$T=\R$ muni de l'ordre usuel sur les rÃ©els. De maniÃ¨re duale, comme vu dans le texte~\cite{chap-intro}, la famille des \emph{sur-niveaux} $F^t=f^{-1}\left([t, +\infty[\right)$ forme une filtration indexÃ©e par $T=\R$ muni de l'ordre opposÃ©.
\end{exemple}

\begin{definition}\label{def:filt_simp}
Une filtration $(X_t)_{t\in T}$ est dite \emph{simpliciale} si chaque espace $X_t$ est un complexe simplicial et un sous-complexe de $X_{t'}$ pour tout $t'\geq t$ dans l'ensemble~$T$.
\end{definition}

\begin{figure}[t]
\centering
\includegraphics[width=\textwidth]{filt_simp}
\caption{En haut: une fonction rÃ©elle $f$ sur un complexe simplicial~$X$. En bas: la filtration (simpliciale) des sous-niveaux de~$f$, restreinte aux indices $\{1, 2, 3, 4, 5\}$.}
\label{fig:filt_simp}
\end{figure}

\begin{exemple}
Ã‰tant donnÃ© un complexe simplicial~$X$ et une fonction $f\colon X\to\R$ qui associe un rÃ©el Ã&nbsp; chaque simplexe de~$X$, la filtration des sous-niveaux de~$f$ est simpliciale. Voir la figure~\ref{fig:filt_simp} pour une illustration.
\end{exemple}

\section{Modules de persistance}
Comme dit en introduction de ce texte, les modules de persistance sont le principal objet d'Ã©tude de la thÃ©orie de la persistance.

\begin{definition}\label{def:module_pers}
Un \emph{$\field$-module de persistance indexÃ© par~$T$}, ou simplement \emph{module de persistance} lorsque le corps~$\field$ et l'ensemble d'indexation~$T$ sont clairs dans le contexte, est une famille $(M_t)_{t\in T}$ de $\field$\nobreakdash-espa\-ces vectoriels reliÃ©s par des applications $\field$-linÃ©aires $m_{t,t'}\colon M_t\to\nobreak M_{t'}$ pour tous $t\leq t'\in T$ telles que:
\[ \begin{cases}
m_{t,t}= \id_{M_t} &amp; \forall t\in T,\\
m_{t,t''}= m_{t',t''} \circ m_{t,t'} &amp; \forall t\leq t'\leq t'' \in T.
\end{cases} \]
Les espaces $M_t$ et les applications $m_{t,t'}$ sont appelÃ©s respectivement \emph{espaces internes} et \emph{applications internes} au module~$M$.
\end{definition}

Le cas d'usage typique des modules de persistance en analyse topologique de donnÃ©es est le suivant:

\begin{lemme}\label{lem:filt-homology}
Pour toute filtration $(X_t)_{t\in T}$ et tout degrÃ©~$k$ en homologie, la famille des groupes d'homologie $(H_k^{\mathrm{sing}}(X_t))_{t\in T}$, reliÃ©s par les applications linÃ©aires $(\iota_{t,t'})_*$ induites par les inclusions $\iota_{t,t'}\colon X_t\hookrightarrow X_{t'}$, forme un module de persistance indexÃ© par~$T$.
Celui-ci est appelÃ© le \emph{module de persistance induit} par $(X_t)_{t\in T}$ en homologie de degrÃ©~$k$.
\end{lemme}

\begin{proof}
DÃ©coule directement de la fonctorialitÃ© de l'homologie.
\end{proof}

\begin{exemple}\label{ex:mod_pers}
Le module de persistance induit en homologie de degrÃ©~$1$ par la filtration simpliciale de la figure~\ref{fig:filt_simp} restreinte aux indices $\{1, 2, 3, 4, 5\}$ est le suivant:
\[ \xymatrix@C=1.2cm{
\field\ar[r]^-{\left(\begin{smallmatrix}1\\0\end{smallmatrix}\right)}
&amp; \field^2
\ar[r]^-{\left(\begin{smallmatrix}0&amp;1\end{smallmatrix}\right)}
&amp; \field
\ar[r]^-{\left(\begin{smallmatrix}0\\1\end{smallmatrix}\right)}
&amp;
\field^2
\ar[r]^-{\left(\begin{smallmatrix}1&amp;0\\0&amp;1\end{smallmatrix}\right)}
&amp; \field^2 } \]
Notons que seules les applications internes reliant deux espaces internes successifs sont explicitÃ©es ici, les autres se dÃ©duisent par composition. La reprÃ©sentation matricielle des applications internes dÃ©pend du choix des bases pour les groupes d'homologie: ici on a pris les cycles minimaux entourant chaque ``trou'' dans le complexe simplicial pour former les bases.
\end{exemple}

\begin{definition}\label{def:submodule}
Un module de persistance~$N$ est un \emph{sous-module} d'un autre module de persistance~$M$, notÃ© $N\subseteq M$, si $N_t$ est un sous-espace vectoriel de~$M_t$ pour tout~$t\in T$, et si $n_{t,t'}$ est la restriction de~$m_{t,t'}$ Ã&nbsp;~${N_t}$ pour tous $t\leq t' \in T$.
\end{definition}

\begin{definition}\label{def:module_morph}
Un \emph{morphisme de $\field$-modules de persistance} \hbox{$\phi\colon M\to N$} est une famille d'applications $\field$-linÃ©aires $\left(\phi_t\colon M_t \to N_t\right)_{t\in T}$ telles que le diagramme suivant commute pour tous $t\leq t'\in T$:
\[ \xymatrix@C=1.2cm{
M_t \ar^-{m_{t,t'}}[r]\ar_-{\phi_t}[d] &amp; M_{t'} \ar^-{\phi_{t'}}[d] \\
N_t \ar_-{n_{t,t'}}[r] &amp; N_{t'}
} \]
\end{definition}

On a en particulier un \emph{morphisme identitÃ©} pour chaque module de persistance~$M$, notÃ© $\id_M$ et dÃ©fini point Ã&nbsp; point par $(\id_M)_t =\id_{M_t}$. On a Ã©galement un \emph{morphisme nul} $M\stackrel{0}{\longrightarrow} N$ entre toute paire de modules de persistance~$M,N$, dÃ©fini point Ã&nbsp; point par l'application linÃ©aire nulle.
La composition des morphismes de modules de persistance, quant Ã&nbsp; elle, est dÃ©finie point Ã&nbsp; point par la composition des applications linÃ©aires:

\begin{definition}\label{def:module_comp}
Pour tous morphismes de modules de persistance $L \stackrel{\phi}{\longrightarrow} M \stackrel{\psi}{\longrightarrow} N$ indexÃ©s par~$T$, la \emph{composÃ©e} $\psi \circ \phi$ est dÃ©finie par:
\[ (\psi\circ \phi)_t \ = \ \psi_t\circ \phi_t \quad \forall t\in T. \]
\end{definition}

La composition est donc associative, du fait de l'associativitÃ© de la composition des applications linÃ©aires. De plus, pour tout morphisme $\phi\colon M\to N$ on a $\phi\circ\id_M = \id_N\circ \phi= \phi$, ainsi les morphismes identitÃ©s associÃ©s aux modules de persistance forment l'identitÃ© pour la composition.

\section{Le point de vue de la thÃ©orie des catÃ©gories}
\label{sec:cat}

Les dÃ©finitions ci-dessus peuvent Ãªtre reformulÃ©es de maniÃ¨re trÃ¨s succincte en utilisant le langage de la thÃ©orie des catÃ©gories. On peut en effet voir l'ensemble totalement ordonnÃ©~$T$ comme une catÃ©gorie (notÃ©e~$\sfT$), avec un objet par Ã©lÃ©ment $t\in T$ et un unique morphisme par paire d'Ã©lÃ©ments comparables $t\leq t' \in T$. La dÃ©finition~\ref{def:module_pers} revient alors Ã&nbsp; dire que les modules de persistance sont des foncteurs de~$\sfT$ dans la catÃ©gorie des $\field$-espaces vectoriels, notÃ©s $\sfT\to \Vect_{\field}$, tandis que la dÃ©finition~\ref{def:module_morph} revient Ã&nbsp; dire que les morphismes entre modules de persistance sont les transformations naturelles entre foncteurs $\sfT\to \Vect_{\field}$, dont la composition se fait point Ã&nbsp; point comme rappelÃ© dans la dÃ©finition~\ref{def:module_comp}. Ensemble, ces Ã©lÃ©ments nous disent que les modules de persistance forment une catÃ©gorie de foncteurs.

Au-delÃ&nbsp; de ce langage, la thÃ©orie des catÃ©gories fournit un ensemble d'outils et de rÃ©sultats fondamentaux sur lesquels nous pouvons nous appuyer pour justifier les diverses propriÃ©tÃ©s des modules de persistance. En premier lieu, il est bien connu que les foncteurs Ã&nbsp; valeurs dans une catÃ©gorie abÃ©lienne comme~$\Vect_{\field}$ forment eux-mÃªmes une catÃ©gorie abÃ©lienne, avec les implications suivantes dans notre cas:
\begin{itemize}
\item pour tous modules de persistance $M,N$, l'ensemble des morphismes $M\to N$ forme un groupe abÃ©lien; de plus, la composition des morphismes de modules de persistance est bilinÃ©aire;
\item il existe un (unique) module de persistance, appelÃ© \emph{zÃ©ro-module de persistance} et notÃ©~$0$, qui a la propriÃ©tÃ© que tout morphisme $M\to 0$ ou $0\to N$ est nul, et qui se dÃ©finit comme ayant tous ses espaces internes et toutes ses applications internes nuls;
\item le produit et la somme directe de modules de persistance existent et sont dÃ©finis point Ã&nbsp; point comme dans la dÃ©finition~\ref{def:direct-sum} ci-dessous;
\item tout morphisme de modules de persistance admet un noyau et un conoyau, dÃ©finis point Ã&nbsp; point comme dans la dÃ©finition~\ref{def:kernel_image_cokernel} ci-dessous; de plus, un morphisme~$\phi$ est simplifiable Ã&nbsp; gauche pour la composition ($\phi\circ \psi = \phi \circ\psi' \Rightarrow \psi=\psi'$) si et seulement si son noyau est nul; de maniÃ¨re similaire, $\phi$ est simplifiable Ã&nbsp; droite si et seulement si son conoyau est nul.
\end{itemize}

Ainsi, on peut manipuler les modules de persistance et les morphismes qui les relient un peu Ã&nbsp; la maniÃ¨re des espaces vectoriels et des applications linÃ©aires. D'ailleurs, la thÃ©orie de la persistance contient celle des espaces vectoriels puisque la catÃ©gorie des modules de persistance indexÃ©s par un ensemble singleton (par exemple $T=\{1\}$) est Ã©quivalente Ã&nbsp; celle des espaces vectoriels, chaque module dans ce cas Ã©tant formÃ© d'un unique espace interne et chaque morphisme entre modules Ã©tant formÃ© d'une unique application linÃ©aire.

\begin{definition}\label{def:direct-sum}
Ã‰tant donnÃ©s deux modules de persistance~$M,N$, leur \emph{somme directe} $M\oplus N$ est dÃ©finie point Ã&nbsp; point, c'est-Ã&nbsp;-dire que $(M \oplus\nobreak N)_t = M_t \oplus N_t$ pour tout $t\in T$, et $mn_{t,t'} = m_{t,t'} \oplus n_{t,t'}$ pour tous $t\leq t'\in T$, oÃ¹ $(mn_t)_{t\in T}$ dÃ©signe la famille d'applications internes au module $M\oplus N$.
\end{definition}

\begin{definition}\label{def:kernel_image_cokernel}
Pour tout morphisme de modules de persistance $\phi\colon M\to N$, le noyau~$\ker\phi$, l'image~$\im \phi$ et le conoyau~$\coker \phi$ sont tous trois dÃ©finis point Ã&nbsp; point de la maniÃ¨re suivante (dÃ©crite pour le noyau et analogue pour l'image et le conoyau):
\begin{itemize}
\item pour tout $t\in T$, l'espace $(\ker \phi)_t$ est dÃ©fini comme Ã©tant $\ker \phi_t$;
\item pour tous $t\leq t' \in T$, l'application interne $(\ker \phi)_t \to (\ker \phi)_{t'}$ est dÃ©finie comme Ã©tant la restriction de $m_{t,t'}$ Ã&nbsp; $\ker \phi_t$.
\end{itemize}
\end{definition}

Un morphisme $\phi\colon M\to N$ est appelÃ© \emph{monomorphisme} lorsqu'il est simplifiable Ã&nbsp; gauche pour la composition, ce qui, comme on l'a vu plus haut, revient Ã&nbsp; dire que $\ker \phi=0$ (\ie $\ker \phi_t=0$ pour tout $t\in T$). De maniÃ¨re similaire, $\phi$ est appelÃ© \emph{Ã©pimorphisme} lorsqu'il est simplifiable Ã&nbsp; droite, ce qui revient Ã&nbsp; dire que $\coker \phi=0$ (\ie $\coker \phi_t=0$ pour tout $t\in T$). Enfin, $\phi$ est appelÃ© \emph{isomorphisme} lorsque $\ker \phi = 0 = \coker \phi$, et dans ce cas les modules $M$ et $N$ sont dits \emph{isomorphes}, notÃ© $M\cong N$.

\section{Le point de vue de l'algÃ¨bre commutative}
\label{sec:alg_comm}

Nous allons maintenant justifier l'usage du terme \emph{module} dans la dÃ©nomination des modules de persistance. Il s'avÃ¨re en effet que, sous certaines conditions, les modules de persistance peuvent Ãªtre vus comme des modules sur des algÃ¨bres. Cela provient de rÃ©sultats plus gÃ©nÃ©raux de plongement des catÃ©gories abÃ©liennes dans des catÃ©gories de modules. Pour simplifier l'exposÃ© nous allons nous concentrer sur le cas particulier oÃ¹ l'ensemble totalement ordonnÃ©~$T$ est fini: dans ce cas, les modules de persistance peuvent Ãªtre vus comme des modules sur l'algÃ¨bre des polynÃ´mes Ã&nbsp; une variable Ã&nbsp; coefficients dans~$\field$.

Supposons donc que $T$ est fini, et mÃªme, sans perte de gÃ©nÃ©ralitÃ©, que $T = \{0, 1,\dots, \ell\}\subset\N$. Soit $M$ un module de persistance indexÃ© par~$T$. On l'Ã©tend d'abord en un module de persistance~$M'$ indexÃ© par~$\N$ en posant
\[ \begin{cases}
M'_t = M_{\min\{t,\ell\}} &amp; \forall t\in\N, \\
m'_{t,t'} = m_{\min\{t,\ell\}, \min\{t',\ell\}} &amp; \forall t\leq t' \in\N.
\end{cases} \]
On vÃ©rifie aisÃ©ment que $M'$ est bien un module de persistance.
On~considÃ¨re ensuite le $\field$-espace vectoriel
\[ \bar M = \bigoplus_{t=0}^\infty M'_t \]
que l'on munit d'une structure de module Ã&nbsp; gauche sur $\field[x]$ en posant
\[ x\cdot (\alpha_0,\, \alpha_1,\, \alpha_2,\, \cdots)\quad =\quad (0,\, m'_{0,1}(\alpha_0),\, m'_{1,2}(\alpha_1),\, \cdots) \]
pour tout Ã©lÃ©ment $(\alpha_0,\, \alpha_1,\, \alpha_2,\, \cdots)$ de $\bar M$. La structure de module est complÃ©tÃ©e par composition et linÃ©aritÃ©, et l'on observe que c'est en fait une structure de module $\N$-graduÃ© sur l'algÃ¨bre $\field[x]$ (elle-mÃªme $\N$-graduÃ©e) dont la composante de degrÃ©~$t$ est~$M'_t$.

Ainsi on envoie les modules de persistance indexÃ©s par~$T$ dans les modules $\N$-graduÃ©s sur $\field[x]$. On peut montrer que cette opÃ©ration induit un plongement de catÃ©gorie abÃ©lienne, ce qui en pratique signifie que l'on peut sans problÃ¨me traiter les modules de persistance comme des modules sur l'algÃ¨bre des polynÃ´mes et utiliser des outils de l'algÃ¨bre commutative pour les Ã©tudier. On en verra un exemple dans la prochaine section.

\section{DÃ©composition des modules de persistance}
\label{sec:decomp}

L'une des questions fondamentales qui se posent Ã&nbsp; nous est celle de la classification des modules de persistance Ã&nbsp; isomorphisme prÃ¨s. Pour y rÃ©pondre nous allons Ã©noncer un thÃ©orÃ¨me de structure (thÃ©orÃ¨me~\ref{thm:decomp}) qui dÃ©compose les modules de persistance en somme directe de modules structurellement trÃ¨s simples, les \emph{modules intervalles} (dÃ©finition~\ref{def:interval_module}). C'est de ces dÃ©compositions que seront issus nos codes-barres (dÃ©finition~\ref{def:decomp_barcode}), qui, du fait de ce rÃ©sultat structurel, forment un invariant complet des modules de persistance.

\begin{definition}\label{def:decomp}
Si un module de persistance~$M$ se dÃ©compose (Ã&nbsp; isomorphisme prÃ¨s) en une somme directe $M\cong L \oplus N$ dont les deux termes sont non nuls, alors on dit que $M$ est \emph{dÃ©composable} et les termes $L, N$ sont appelÃ©s des \emph{facteurs de~$M$}. Si au contraire il n'existe pas de dÃ©composition de~$M$ de ce type, alors on dit que $M$ est \emph{indÃ©composable}.
\end{definition}

Comme on l'a vu Ã&nbsp; la section~\ref{sec:cat}, les modules de persistance sont Ã©quivalents aux espaces vectoriels lorsque l'ensemble d'indexation~$T$ est un singleton, donc leur dÃ©composition dans ce cas trÃ¨s particulier est facile. Dans le cas gÃ©nÃ©ral en revanche, la question est beaucoup plus complexe, et pour s'en convaincre il suffit de savoir que les modules de persistance ne sont alors gÃ©nÃ©ralement plus semi-simples, c'est-Ã&nbsp;-dire que tous leurs sous-modules ne sont pas des facteurs (autrement dit, il n'y a pas d'analogue du thÃ©orÃ¨me de la base incomplÃ¨te). Voici un exemple.

\begin{exemple}\label{ex:not_semi-simple}
Prenons le module de persistance $\field \stackrel{\hspace{-3pt}\id_\field}{\longrightarrow} \field$ indexÃ© sur l'ensemble~$T=\{1,2\}$. Ce module admet $0 \longrightarrow \field$ comme sous-module mais pas comme facteur. En effet, si c'Ã©tait un facteur alors, par additivitÃ© de la dimension, tout supplÃ©mentaire devrait avoir dimension~$1$ Ã&nbsp; l'indice~$1$ et dimension~$0$ Ã&nbsp; l'indice~$2$ et serait donc isomorphe Ã&nbsp; $\field\to 0$. Or, ce dernier ne peut Ãªtre un sous-module de~$M$ car $\id_{\field}$ envoie $\field$ sur $\field$ et non pas sur~$0$.
\end{exemple}

Le bon cÃ´tÃ© des choses est que, sous certaines hypothÃ¨ses, les modules de persistance indÃ©composables sont structurellement trÃ¨s simples. On les appelle des \emph{modules intervalles}.

\begin{definition}\label{def:interval_module}
Un \emph{intervalle} est un sous-ensemble~$I$ de~$T$ qui est convexe pour l'ordre, c'est-Ã&nbsp;-dire que pour tous $t\leq t' \leq t''\in T$ tels que $t,t''\in I$ on a $t'\in I$. Le \emph{module intervalle}~$\field_I$ associÃ© Ã&nbsp;~$I$ est dÃ©fini point Ã&nbsp; point par\vspace*{-3pt}\enlargethispage{\baselineskip}
\[ (\field_I)_t = \begin{cases} \field &amp; \text{si}\ t\in I, \\
0 &amp; \text{sinon,} \end{cases} \]
avec pour application interne $(\field_I)_t\to (\field_I)_{t'}$ l'identitÃ© de $\field$ si $t,t' \in I$ et l'application nulle sinon. $I$ est appelÃ© le \emph{support} de~$\field_I$.
\end{definition}

Par exemple, les modules de persistance impliquÃ©s dans l'exem\-ple~\ref{ex:not_semi-simple} sont tous des modules intervalles.

\begin{exercice}
Montrer que les modules intervalles sont indÃ©composables.
\end{exercice}

Il existe tout un Ã©ventail de rÃ©sultats de dÃ©composition en somme directe des modules de persistance. Le rÃ©sultat ci-dessous est le plus couramment employÃ©. Il fait l'hypothÃ¨se que le module de persistance considÃ©rÃ© est pdf:

\begin{definition}\label{def:pfd}
Un module de persistance~$M$ est \emph{point Ã&nbsp; point de dimension finie} (pdf) si $\dim M_t&lt;+\infty$ pour tout indice $t\in T$.
\end{definition}

\begin{theoreme}[dÃ©composition]\label{thm:decomp}
Tout module de persistance pdf~$M$ indexÃ© par un ensemble totalement ordonnÃ©~$T$ se dÃ©compose en une somme directe (potentiellement avec un nombre infini de termes au total, mais point Ã&nbsp; point finie) dont chaque terme est un module intervalle. Cette dÃ©composition est unique Ã&nbsp; isomorphisme et rÃ©ordonnancement prÃ¨s des termes.
\end{theoreme}

\begin{exemple}
Le module de persistance~$M$ de l'exemple~\ref{ex:mod_pers}, indexÃ© par $T=\{1, 2, 3, 4, 5\}$, se dÃ©compose comme suit:\vspace*{-3pt}
\[ M \cong \field_{\{1,2\}} \oplus \field_{\{2, 3, 4, 5\}} \oplus \field_{\{4,5\}} \]
Dans ce cas particulier la dÃ©composition se lit directement dans les matrices des applications internes de~$M$, qui sont diagonales. Dans le cas gÃ©nÃ©ral toutefois, les matrices n'ont pas de raison d'Ãªtre diagonales mais le thÃ©orÃ¨me de dÃ©composition dit en substance qu'il existe une famille de bases pour les espaces internes de~$M$ qui sont compatibles entre elles au sens qu'elles rendent les matrices diagonales.
\end{exemple}

\begin{remarque}\label{rem:int_general}
Lorsque $T=\R$, les intervalles supports des facteurs dans la dÃ©composition peuvent Ãªtre ouverts, semi-ouverts, ou fermÃ©s. Ceci contraste avec les intervalles du texte~\cite{chap-intro}, que l'on avait forcÃ©s Ã&nbsp; Ãªtre semi-ouverts Ã&nbsp; gauche par convention.
\end{remarque}

L'unicitÃ© de la dÃ©composition dans le thÃ©orÃ¨me~\ref{thm:decomp} implique en particulier celle des intervalles supports des facteurs, avec lesquels on peut ainsi former le \emph{code-barres} du module.

\begin{definition}\label{def:decomp_barcode}
Pour un module de persistance pdf~$M$, le \emph{code-barres} de~$M$, notÃ© $\barcode(M)$, est le multi-ensemble des intervalles supports des facteurs dans la dÃ©composition de~$M$. Lorsque $T=\R$ muni de l'ordre usuel, le \emph{diagramme de persistance}, notÃ©~$D(M)$, est le multi-ensemble de points $(a,b)$ dans le plan Ã©tendu $\R\times ]-\infty, +\infty]$ correspondant aux intervalles $[a,b]$, $]a,b]$, $]a,b[$ ou $]a,b[$ de~$\barcode(M)$.
\end{definition}

Le thÃ©orÃ¨me de dÃ©composition implique que le code-barres est un invariant complet pour les modules de persistance pdf indexÃ©s par~$T\subseteq\R$. La nature purement gÃ©omÃ©trique du code-barres en fait un outil idÃ©al pour, d'une part, l'interprÃ©tation visuelle de la structure du module, et d'autre part, la comparaison de cette structure avec celles d'autres modules. On verra en effet dans le texte~\cite{sec-stabilite} que l'on peut dÃ©finir une distance naturelle entre modules de persistance, que les codes-barres permettent de calculer exactement.

\begin{remarque}
Ici on ne dÃ©finit le diagramme de persistance que dans le cas oÃ¹~$T=\R$ car dans le cas gÃ©nÃ©ral les extrÃ©mitÃ©s (ouvertes ou fermÃ©es) des intervalles ne sont pas toujours dÃ©finies de maniÃ¨re unique. Notons par ailleurs suite Ã&nbsp; la remarque~\ref{rem:int_general} que, dans le cas oÃ¹ $T=\R$, le diagramme de persistance n'est plus Ã©quivalent au code-barres car il perd l'information sur le caractÃ¨re ouvert, semi-ouvert ou fermÃ© des intervalles. En particulier, le diagramme de persistance n'est pas un invariant complet des modules de persistance pdf.
\end{remarque}

\begin{remarque}\label{rem:pers_bonne-approche}
Dans le contexte de l'exemple~\ref{ex:filt-sublevel}, le lemme~\ref{lem:filt-homology} nous fournit un module de persistance par degrÃ© en homologie pour la filtration des sur-niveaux d'une fonction $f\colon X\to\R$ quelconque. Le~thÃ©orÃ¨me~\ref{thm:decomp} assure alors que ce module de persistance a un code-barres bien dÃ©fini, Ã&nbsp; la seule condition que les groupes d'homologie des sur-niveaux de~$f$ soient de dimension finie. Dans le cas particulier de l'homologie de degrÃ©~$0$, cette hypothÃ¨se revient Ã&nbsp; dire que les sur-niveaux de~$f$ ont chacun un nombre fini de composantes connexes par arc. Cette condition est beaucoup moins restrictive que celles que nous avons dÃ» Ã©noncer dans le texte~\cite{chap-intro}. En particulier, Ã&nbsp;~prÃ©sent le code-barres encode les intervalles de persistance de toutes les composantes connexes par arc dans les sur-niveaux de~$f$, et non plus seulement de celles engendrÃ©es par les pics de la fonction.\vspace*{-.5\baselineskip}
\end{remarque}
\enlargethispage{2\baselineskip}%
\subsection*{Origine du thÃ©orÃ¨me de dÃ©composition dans le cas oÃ¹ $T$ est fini}

Supposons que $T$ est fini, Ã©gal Ã&nbsp; $\{0, 1,\dots, \ell\}$ sans perte de gÃ©nÃ©ralitÃ©. Comme nous l'avons vu dans la section~\ref{sec:alg_comm}, on peut envoyer tout module de persistance~$M$ sur un module $\N$-graduÃ©~$\bar M$ sur l'algÃ¨bre graduÃ©e des polynÃ´mes~$\field[x]$, et cette opÃ©ration dÃ©finit un plongement de catÃ©gorie abÃ©lienne. Cela implique que l'on peut dÃ©composer~$\bar M$ en tant que module $\N$-graduÃ© sur $\field[x]$ puis en dÃ©duire une dÃ©composition de~$M$ en tant que module de persistance. C'est ce que nous allons faire maintenant.

Soit donc un module de persistance~$M$ pdf indexÃ© par~$T$. Dans la construction du module de persistance~$M'$ indexÃ© par~$\N$ donnÃ©e Ã&nbsp; la section~\ref{sec:alg_comm}, remarquons que les applications internes deviennent des isomorphismes au-delÃ&nbsp; de l'indice~$\ell$. En consÃ©quence, les morphismes de transition entre les degrÃ©s au-delÃ&nbsp; du degrÃ©~$\ell$ dans~$\bar M$ sont des isomorphismes, ce qui implique que $\bar M$ est de type fini en tant que module graduÃ© sur l'anneau $\field[x]$. Ce dernier Ã©tant euclidien, on peut dÃ©composer~$\bar M$ en utilisant le thÃ©orÃ¨me des facteurs invariants, ou~plutÃ´t sa version graduÃ©e\footnote{Une preuve constructive classique du thÃ©orÃ¨me des facteurs invariants dans le cas d'un anneau euclidien repose sur la rÃ©duction en forme de Smith de la matrice d'une prÃ©sentation finie du module. Dans le cas graduÃ©, la preuve est identique une fois que l'on a observÃ© que les idÃ©aux impliquÃ©s sont tous homogÃ¨nes.}, qui nous donne la dÃ©composition suivante:\vspace*{-3pt}
\[ \bar M \quad \cong \quad \bigoplus_{j\in \mathcal{J}_{\mathrm{libre}}} x^{a_j}\cdot \field[x] \quad \oplus \quad \bigoplus_{j\in \mathcal{J}_{\mathrm{torsion}}} x^{a_j}\cdot \bigl(\field[x]\ /\ x^{d_j}\cdot \field[x]\bigr). \]
La premiÃ¨re somme directe dans la dÃ©composition est la partie libre de~$\bar M$, qui engendre les intervalles s'Ã©tendant Ã&nbsp; droite indÃ©finiment dans la dÃ©composition du module de persistance~$M$, de la forme $[a_j, +\infty[{}\cap T = \{a_j,\dots, \ell\}$ avec $0\leq a_j\leq \ell$. La deuxiÃ¨me somme directe dans la dÃ©composition ci-dessus est la torsion du module~$\bar M$, qui engendre le reste des intervalles dans la dÃ©composition de~$M$, de la forme $[a_j, a_j+d_j[{} = \{a_j,\dots, a_j+d_j-1\}$ avec $0\leq a_j &lt; a_j+d_j\leq \ell$ -- cette derniÃ¨re inÃ©galitÃ© provient du fait que les morphismes de transition au-delÃ&nbsp; du degrÃ©~$\ell$ dans~$\bar M$ sont des isomorphismes.

Ainsi, le thÃ©orÃ¨me~\ref{thm:decomp} dans le cas particulier oÃ¹ $T$ est fini dÃ©coule directement du thÃ©orÃ¨me des facteurs invariants.
Dans le cas gÃ©nÃ©ral, le rÃ©sultat est beaucoup plus subtile et se prouve avec des outils de thÃ©orie des reprÃ©sentations d'algÃ¨bres dÃ©veloppÃ©s dans les annÃ©es~1970 -- voir par exemple la preuve de~\cite{crawley2015decomposition}.

\section{Calcul des codes-barres}

Pour faire des calculs on se place dans le cadre simplicial, avec en entrÃ©e une filtration simpliciale de longueur finie dont on suppose que chaque complexe simplicial a un nombre fini de simplexes:
\[
\emptyset = X_0 \subseteq X_1\subseteq \cdots \subseteq X_\ell = X
\]
Sans perte de gÃ©nÃ©ralitÃ©, on suppose de plus que chaque inclusion $X_{i-1}\subseteq X_i$ dans la sÃ©quence correspond Ã&nbsp; l'ajout d'un unique simplexe~$\sigma_i$ dans le complexe. Notons que, du fait que les~$X_i$ sont d'honnÃªtes complexes simpliciaux, $\sigma_i$ n'apparaÃ®t dans la filtration qu'une fois que toutes ses faces sont apparues. Ceci ne veut toutefois pas dire que tous les sommets apparaissent en premier, puis toutes les arÃªtes, et ainsi de suite.

Sur cette entrÃ©e nous allons calculer les code-barres des modules de persistance induits en homologie simpliciale par la filtration pour tous les degrÃ©s d'homologie Ã&nbsp; la fois. La mÃ©thode est en fait la mÃªme que celle du calcul de l'homologie simpliciale usuelle (voir la remarque~1.13 du texte~\cite{chap-homologie}), au dÃ©tail important prÃ¨s que l'\emph{on ne peut modifier l'ordre sur les simplexes imposÃ© par la filtration} lors de l'exÃ©cution du pivot de Gauss pour rÃ©duire les matrices des opÃ©rateurs de bord. Voici les Ã©tapes, illustrÃ©es sur un exemple dans la figure~\ref{fig:algo_pers}:

\begin{figure}[t]
\centering
\includegraphics[width=\textwidth]{algo_pers}
\caption{En haut: une fonction rÃ©elle~$f$ sur un complexe simplicial~$X$. En bas: la matrice des opÃ©rateurs de bord de tous les degrÃ©s de~$X$ (gauche), ordonnÃ©e selon les valeurs de~$f$, et sa version rÃ©duite par le pivot de Gauss (droite).}
\label{fig:algo_pers}
\end{figure}

\begin{enumerate}
\item
On construit tout d'abord la matrice $D$ contenant les matrices des opÃ©rateurs de bord de tous les degrÃ©s du complexe simplicial total~$X$. Chaque simplexe $\sigma_i$ donne lieu Ã&nbsp; exactement une ligne et une colonne dans~$D$, et ces derniÃ¨res sont ordonnÃ©es par indices croissants dans la filtration. En notant $d_i$ la dimension du simplexe~$\sigma_i$, l'entrÃ©e $D_{i,j}$ de la matrice est nulle si $d_i\neq d_j-1$, sinon elle est Ã©gale Ã&nbsp; la coordonnÃ©e du vecteur~$\partial_{d_j}(\sigma_j)$ le long de l'axe~$\sigma_i$ dans l'espace des chaÃ®nes~$C_{d_i}(X)$. Quand $\field=\Z/{2\Z}$, cela revient Ã&nbsp; dire que $D_{i,j}$ vaut~$1$ si~$\sigma_i$ est une face de $\sigma_j$ et $0$ sinon.

\item
On rÃ©duit la matrice~$D$ Ã&nbsp; une forme Ã©chelonnÃ©e en colonnes, sans changer l'ordre des lignes et des colonnes. Le \emph{pivot} d'une colonne non nulle est son entrÃ©e non nulle la plus basse (c'est-Ã&nbsp;-dire situÃ©e sur la ligne d'indice le plus Ã©levÃ©), et la forme Ã©chelonnÃ©e a la propriÃ©tÃ© que les pivots se situent tous sur des lignes distinctes. Pour atteindre cet Ã©tat, on applique une version restreinte du pivot de Gauss dÃ©crite dans l'algorithme~\ref{alg:pivot}, oÃ¹ $D_{\cdot, i}$ dÃ©signe la colonne de~$D$ d'indice~$i$, la~fonction $\code{pivligne}(i)$ renvoie l'indice de la ligne sur laquelle se trouve le pivot de $D_{\cdot, i}$ lorsqu'il existe et zÃ©ro sinon, enfin la fonction $\code{piv(i)}$ renvoie la valeur du pivot de $D_{\cdot, i}$ (qui existe lorsque cette fonction est appelÃ©e).

\item
Une fois la matrice~$D$ rÃ©duite en forme Ã©chelonnÃ©e, ses pivots dÃ©finissent un appariement partiel des simplexes de~$X$, Ã&nbsp; partir duquel le code-barres de la filtration peut Ãªtre dÃ©duit. Plus prÃ©cisÃ©ment, Ã&nbsp; tout pivot situÃ© Ã&nbsp; l'intersection d'une ligne~$i$ et d'une colonne~$j$ correspond la paire de simplexes $(\sigma_i, \sigma_j)$, qui engendre l'intervalle $[i,j)$ en degrÃ© $d_i$ dans le code-barres.
Les simplexes impliquÃ©s dans aucune paire, quant Ã&nbsp; eux, engendrent les intervalles infinis du code-barres; plus prÃ©cisÃ©ment, le simplexe~$\sigma_k$ engendre l'intervalle $[k,+\infty)$ en degrÃ©~$d_k$.
\end{enumerate}

\bgroup\smaller
\begin{algorithm}[t]
\KwIn{matrice $D$ de taille $\ell\times \ell$ Ã&nbsp; coefficients dans $\field$}

\For{$j$ allant de $1$ Ã&nbsp; $\ell$}{
\While{$\exists i&lt;j$ tel que $\code{pivligne}(i) = \code{pivligne}(j) \neq 0$}
{$D_{.,j} \longleftarrow D_{\cdot,j} - \frac{\code{piv}(j)}{\code{piv}(i)}\, D_{\cdot, i}$}
}

\KwOut{la matrice $D$ rÃ©duite}
\caption{\label{alg:pivot} \code{Algorithme de rÃ©duction par pivot de Gauss}}
\vspace*{-\baselineskip}
\end{algorithm}
\egroup

\begin{exemple}
Prenons la filtration des sous-niveaux de la fonction de la figure~\ref{fig:algo_pers}. Une fois la matrice des opÃ©rateurs de bord rÃ©duite, il reste~$3$ pivots qui forment les paires de simplexes $(2,4)$, $(3,5)$ et $(6,7)$ -- ici on identifie chaque simplexe avec la valeur de~$f$ correspondante car~$f$ est injective. Ces paires engendrent les intervalles suivants: $[2,4)$ en degrÃ©~$0$, $[3,5)$ en degrÃ©~$0$, et $[6,7)$ en degrÃ©~$1$. Il reste un simplexe non appariÃ© (le~$1$), qui engendre l'intervalle $[1,+\infty)$ en degrÃ©~$0$ dans le code-barres.
\end{exemple}

\subsubsection*{Terminaison et complexitÃ©}
Il est clair que les Ã©tapes~1 et~3 de la mÃ©thode terminent, seule l'Ã©tape~2 requiert un effort d'analyse. Il~n'est en effet pas Ã©vident Ã&nbsp; premiÃ¨re vue que l'algorithme~\ref{alg:pivot} termine, du~fait de la boucle interne \texttt{tant que}. L'observation clÃ© est que, lors de chaque mise Ã&nbsp; jour de la colonne $D_{\cdot,j}$, son pivot est annulÃ© et toutes les entrÃ©es en-dessous dans la matrice restent Ã&nbsp; zÃ©ro car $D_{\cdot, i}$ a son pivot Ã&nbsp; la mÃªme hauteur que $D_{\cdot, j}$ avant la mise Ã&nbsp; jour. Ainsi, le pivot de~$D_{\cdot,j}$ remonte strictement dans sa colonne Ã&nbsp; chaque mise Ã&nbsp; jour de celle-ci, ce qui implique que le nombre d'itÃ©rations de la boucle interne Ã&nbsp; chaque itÃ©ration de la boucle externe est au plus le nombre de lignes, soit~$\ell$. Il y a donc au total $O(\ell^2)$ mises Ã&nbsp; jour de colonnes, chacune en temps $O(\ell)$, ce qui implique la terminaison de l'algorithme~\ref{alg:pivot} avec une complexitÃ© en temps dans le pire cas en $O(\ell^3)$. Cette quantitÃ© domine les complexitÃ©s des Ã©tapes~1 et~3 de la mÃ©thode.

\subsubsection*{Correction}
L'Ã©tape 1 de la mÃ©thode ne prÃ©sente aucun enjeu particulier. Ensuite, que le pivot de Gauss exÃ©cutÃ© Ã&nbsp; l'Ã©tape 2 rÃ©duise bien la matrice~$D$ en forme Ã©chelonnÃ©e est un fait bien connu, dont la preuve est une variante de celle de la factorisation LU -- voir par exemple~\cite[Ch.\,28]{clrs-ia-09}. Il reste donc Ã&nbsp; se convaincre que l'interprÃ©tation de la structure de la matrice~$D$ rÃ©duite en termes de code-barres Ã&nbsp; l'Ã©tape~3 est correcte. Nous ne donnerons pas la preuve de ce fait, qui est technique et sans intÃ©rÃªt particulier -- voir par exemple~\cite[section~3.3]{dey2022computational}. Nous nous contenterons de donner l'intuition derriÃ¨re, que voici.

L'algorithme~\ref{alg:pivot} de rÃ©duction de matrice peut Ãªtre vu comme construisant itÃ©rativement un sous-complexe $Y$ du complexe simplicial total~$X$, en commenÃ§ant par $Y=X_0=\emptyset$ et en terminant par $Y=X_\ell=X$, et en maintenant les groupes d'homologie de~$Y$ tout au long du processus. Ã€ chaque itÃ©ration, $Y$ transitionne de $X_{j-1}$ Ã&nbsp; $X_j$ par l'insertion du simplexe~$\sigma_j$. Au moment de l'insertion, la rÃ©duction de la colonne d'indice~$j$ dans~$D$ dÃ©termine si cette colonne est linÃ©airement dÃ©pendante des colonnes de~$D$ prÃ©cÃ©demment rÃ©duites, ce qui en fait dÃ©termine si le bord de $\sigma_j$ est dÃ©jÃ&nbsp; homologue Ã&nbsp; zÃ©ro dans $X_{j-1}$ on pas: si c'est le cas (colonne $D_{\cdot, j}$ rÃ©duite Ã&nbsp; zÃ©ro), alors l'insertion de $\sigma_j$ crÃ©e un nouveau cycle en homologie de degrÃ©~$d_j$ dans~$Y$; \hbox{sinon} (colonne non rÃ©duite Ã&nbsp; zÃ©ro), l'insertion de $\sigma_j$ dÃ©truit un cycle en homologie de degrÃ©~$d_{j-1}$ dans~$Y$, plus prÃ©cisÃ©ment le cycle crÃ©Ã© prÃ©cÃ©demment par l'insertion du simplexe~$\sigma_i$ dont la ligne correspondante dans la matrice contient le pivot de la colonne $D_{\cdot, j}$ aprÃ¨s sa rÃ©duction. La paire $(\sigma_i, \sigma_j)$ engendre donc l'intervalle de persistance $[i, j)$ de ce cycle dans le code-barres en degrÃ©~$d_i=d_{j-1}$. Ã€~la fin de l'algorithme, tout simplexe $\sigma_k$ non appariÃ© a crÃ©Ã©, lors de son inser\-tion, un cycle en degrÃ©~$d_k$ qui n'a jamais Ã©tÃ© dÃ©truit ensuite; ce~simplexe engendre donc l'intervalle de persistance $[k,+\infty)$ de ce cycle dans le code-barres en degrÃ©~$d_k$.

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

</pre></body></html>