stablefunctions.tex

\chapter{Stable Generalised Density Functions}
\label{chap:stable_functions}

Chapter~\ref{chap:background} reviewed foundational stability results for GDFs.
This chapter examines the central question of this thesis: \emph{for which GDFs
$f(P, x)$ can we guarantee that the sublevel set filtration of $f_P$ is stable?}
We explore several classes of GDFs for which stability can be guaranteed,
ranging from simple cases to more complex constructions. We also highlight
examples of functions that are not stable.

\section{0-stable generalised density functions}

The simplest class of stable GDFs are those whose persistence diagrams are
invariant under changes to the input point cloud $P$.
\begin{definition}[Point cloud independent GDF]
    A GDF $f(P, x)$ is \emph{point cloud independent} if for any two point
    clouds $P, Q \subseteq \R^d$, we have $f(P, x) = f(Q, x)$ for all
    $x \in \R^d$. Equivalently, $f_P = f_Q$ as functions $\R^d \to \R$.
\end{definition}
\begin{theorem}
    \label{thm:independent_stable}
    A point cloud independent GDF $f : \mathcal{P}(\R^d) \times \R^d \to \R$
    is $0$-stable.
\end{theorem}
\begin{proof}
    If $f(P, x)$ is point cloud independent, then for any two finite point clouds
    $P, Q \subseteq \R^d$, we have identical sublevel set filtrations
    $\{f_P^{-1}(-\infty, a]\}_a$ and $\{f_Q^{-1}(-\infty, a]\}_a$.
    This implies that their persistence modules and persistence diagrams are
    also identical. As the bottleneck distance between identical persistence
    diagrams is zero~\cite{edelsbrunner2010computational}, we have
    \begin{equation}
        d_b(\dgm(f_P), \dgm(f_Q)) = 0 \leq 0 \cdot d_H(P, Q),
    \end{equation}
    satisfying the condition for $0$-stability.
\end{proof}

However, point cloud independence is a sufficient, but not necessary, condition
for 0-stability. Some GDFs whose values depend on $P$ can still yield identical
persistence diagrams for all $P$, thus being $0$-stable.
\begin{example}
    \label{ex:x_plus_g}
    Consider the GDF $f : \mathcal{P}(\R) \times \R \to \R$ defined by
    $f(P, x) = x + g(P)$, where $g : \mathcal{P}(\R^d) \to \R$ is an arbitrary
    function.
    The sublevel sets $f_P^{-1}(-\infty, a]$ are exactly the intervals
    $(-\infty, a - g(P)]$, which always have exactly one connected component
    that persists indefinitely. Thus, the dimension $0$ persistence diagram of
    $f_P$ contains a single point born at $-\infty$ that never dies, and the PD
    is empty in higher dimensions. Thus, for any two finite point clouds $P, Q
    \subseteq \R$, the persistence diagrams $\dgm(f_P)$ and $\dgm(f_Q)$ are
    identical, and we have $0$-stability without independence on the point
    cloud. This example also trivially generalises to $\R^d$ where $f$ defines a
    hyperplane.
\end{example}

\section{Unstable generalised density functions}

To form an intuition for stability, we construct a simple GDF that is not $c$-stable
for any $c\in \R^+$, i.e. \emph{unstable}.
\begin{example}
    Consider the GDF $f : \mathcal{P}(\R) \times \R \to \R$ defined by
    \begin{equation}
        \label{eq:unstable_gdf}
        f(P, x) = \begin{cases}
           0, & \text{if } x \in P, \\
           1, & \text{otherwise.} 
        \end{cases}
    \end{equation}
    Consider two point clouds $P = \{\mathbf{0}\}$ and
    $Q = \{\mathbf{0}, \varepsilon \cdot \mathbf{1}\}$, where $\mathbf{0}\in
    \R^d$ denotes the vector of zeros and $\mathbf{1} \in \R^d$ is the vector of
    ones, and $\varepsilon > 0$ is a small positive number. The Hausdorff
    distance between $P$ and $Q$ is $d_H(P, Q) = d(\mathbf{0}, \varepsilon \cdot
    \mathbf{1}) = \varepsilon$. As shown in Figure~\ref{fig:pd_unstable}, the
    persistence diagrams have bottleneck distance of at least
    $\frac{1}{\sqrt{2}}$. As $\varepsilon \to 0$, the bottleneck distance
    remains constant, while the Hausdorff distance tends to zero, which implies
    that $f$ is not $c$-stable for any $c \in \R^+$.
\end{example}
While the example above is discontinuous, discontinuity is not required for
instability. The following example has the same 0-dimensional persistence
diagrams for $P = \{\mathbf{0}\}$ and $Q = \{\mathbf{0}, \varepsilon \cdot \mathbf{1}\}$
as the function in~\eqref{eq:unstable_gdf}, but is continuous:
\begin{equation}
   f(P, x) = 2 \cdot D(P) \cdot \min_{p\in P} d(x, p),
\end{equation}
where $D(P)$ is the diameter of the point cloud $P$.
\begin{figure}
    \centering
    \begin{subfigure}[t]{0.5\textwidth}
        \begin{tikzpicture}
            \small
            % Axes
            \draw[->] (0,0) -- (5,0) node[right] {Birth};
            \draw[->] (0,0) -- (0,5.5) node[above] {Death};
            
            % Grid
            % \draw[gray!30] (0,0) grid (6,6);
            
            % Diagonal
            \draw[dashed] (0,0) -- (5,5);
            
            % Point coords
            \coordinate (p1) at (1,5);
            
            % Lines to axes
            \draw[dashed,gray] (p1) -- (1,0) node[below,black] {$0$};

            \draw[dashed,gray] (5,5) -- (0,5) node[left,black] {$\infty$};

            % Points
            \fill (p1) circle (2pt) node[above right] {$p_1$};
        \end{tikzpicture}
        \caption{The $0$-dimensional PD of $f_P$. The point $p_1$ corresponds to
        the single connected component of the sublevel set $f_P^{-1}(-\infty,
        a]$, which includes only $\mathbf{0}$ for $a \in [0, 1)$ and $\R^d$ for
        $a \geq 1$.}
    \end{subfigure}%
    ~
    \begin{subfigure}[t]{0.5\textwidth}
        \begin{tikzpicture}
            \small
            % Axes
            \draw[->] (0,0) -- (5,0) node[right] {Birth};
            \draw[->] (0,0) -- (0,5.5) node[above] {Death};
            
            % Grid
            % \draw[gray!30] (0,0) grid (6,6);
            
            % Diagonal
            \draw[dashed] (0,0) -- (5,5);
            
            % Point coords
            \coordinate (p1) at (1,5);
            \coordinate (p2) at (1,2.5);
            
            % Lines to axes
            \draw[dashed,gray] (p1) -- (1,0) node[below,black] {$0$};
            \draw[dashed,gray] (p2) -- (0,2.5) node[left,black] {$1$};

            \draw[dashed,gray] (5,5) -- (0,5) node[left,black] {$\infty$};
            
            \draw[dashed,gray] (p2) -- (1.8,1.8) node[near end,above,align=center,black] {$\frac{1}{\sqrt{2}}$};

            % Points
            \fill (p1) circle (2pt) node[above right] {$p_2$};
            \fill (p2) circle (2pt) node[above left] {$p_3$};
        \end{tikzpicture}
        \caption{The $0$-dimensional PD of $f_Q$. The point $p_2$ corresponds to
        a connected component of the sublevel set $f_Q^{-1}(-\infty, a]$, which
        includes only $\mathbf{0}$ for $a \in [0, 1)$ and $\R^d$ for $a \geq
        1$, while the point $p_3$ corresponds to the connected component that
        contains $\varepsilon \cdot \mathbf{1}$ for $a \in [0, 1)$.}
    \end{subfigure}%
    \caption{Persistence diagrams in dimension $0$ of $f_P$ and $f_Q$ for the
    unstable GDF example. When matching points between the diagrams, the optimal
    matching connects $p_1$ to $p_2$ with cost $0$ and $p_3$ to the diagonal
    with cost $\frac{1}{\sqrt{2}}$.}
    \label{fig:pd_unstable}
\end{figure}

\section{Point cloud Lipschitz generalised density functions}

A powerful sufficient condition for stability is a form of Lipschitz continuity
with respect to the point cloud:
\begin{definition}[Point cloud Lipschitz (PC-Lipschitz) GDF]
    A GDF $f$ is \emph{$c$-PC Lipschitz} if, when considered as a map that
    assigns to each finite non-empty point cloud $P \subseteq \R^d$ a function
    $f_P : \R^d \to \R$, it is Lipschitz continuous with constant $c$, where the
    space of finite point clouds is equipped with the Hausdorff distance, and
    the space of real-valued functions $f_P : \R^d \to \R$ is equipped with the
    $L_\infty$-norm. Formally, for any non-empty finite point clouds $P, Q
    \subseteq \R^d$, we have
    \begin{equation}
        \norm{f_P - f_Q}_\infty \leq c \cdot d_H(P, Q).
    \end{equation}
\end{definition}
\begin{lemma}
    \label{lem:pc_lipschitz_stable}
    If $f$ is a $c$-PC Lipschitz GDF and for all finite $P \subseteq \R^d$,
    the induced persistence modules are $q$-tame, then $f$ is $c$-stable.
\end{lemma}
\begin{proof}
    Let $f$ be a $c$-PC Lipschitz GDF. By definition, for any non-empty two
    finite point clouds $P, Q \subseteq \R^d$, we have
    \begin{equation}
        \norm{f_P - f_Q}_\infty \leq c \cdot d_H(P, Q).
    \end{equation}
    Since the persistence modules induced by $f_P$ and $f_Q$ are $q$-tame, by
    Theorem~\ref{thm:stability_sup_norm}, the bottleneck distance between their
    persistence diagrams is bounded by the $L_\infty$-norm of the difference
    $f_P - f_Q$. Combining these two inequalities, we obtain:
    \begin{equation}
        d_b(\dgm(f_P), \dgm(f_Q)) \leq \norm{f_P - f_Q}_\infty \leq c \cdot d_H(P, Q),
    \end{equation}
    which shows that $f$ is $c$-stable.
\end{proof}
While this lemma is a straightforward consequence of
Theorem~\ref{thm:stability_sup_norm}, it provides a versatile tool for
establishing stability, as demonstrated in the following sections.

\section{Weighted \v{C}ech filtration revisited}

The stability of the weighted \v{C}ech filtration (and thus DTM-filtrations) was
stated in Theorem~\ref{thm:weighted_cech_stability}. We provide a more direct
proof of this result than in the original paper~\cite{anai2020dtm} by showing
that the corresponding GDF is PC-Lipschitz.

\begin{theorem}
    The GDF
    \begin{equation}
        f_{g, q}(P, x) = \min_{p \in P} (d(x, p)^{q} + g(p)^{q})^{1/q}
    \end{equation}
    for the weighted \v{C}ech filtration is $d$-stable with
    $d = (1 + c^q)^{1/q}$, where $c$ is the Lipschitz constant of the
    weight function $g : \R^d \to \R^+$.
\end{theorem}
\begin{proof}
    Let $P, Q \subseteq \R^d$ be two finite point clouds with Hausdorff distance
    $d_H(P, Q)$. Similarly to the proof of \v{C}ech stability using
    Theorem~\ref{thm:stability_sup_norm}, fix $x \in \R^d$ and let $p \in P$ be
    the point where the minimum for $(d(x, p)^q + g(p)^q)^{1/q}$ is attained.
    This implies that
    \begin{equation}
        \label{eq:stable_gdf_min}
        f_{g, q}(P, x) = (d(x, p)^q + g(p)^q)^{1/q}.
    \end{equation}
    By the definition of Hausdorff distance, there exists a point $q' \in Q$
    such that $d(p, q') \leq d_H(P, Q)$, which implies that
    \begin{equation}
        d(x, q') \leq d(x, p) + d(p, q') \leq d(x, p) + d_H(P, Q).
    \end{equation}
    By monotonicity of~\eqref{eq:stable_gdf_min} with respect to $d(x, p)$ and
    $g(p)$, we have
    \begin{align}
        f_{g, q}(Q, x)
        & = \min_{q'' \in Q} (d(x, q'')^q + g(q'')^q)^{1/q} \\
        & \leq (d(x, q')^q + g(q')^q)^{1/q} \\
        & \leq ((d(x, p) + d_H(P, Q))^q + (g(p) + c \cdot d_H(P, Q))^q)^{1/q} \\
        & = \norm{(d(x, p) + d_H(P, Q), g(p) + c \cdot d_H(P, Q))}_q.
    \end{align}
    Comparing the values of $f_{g, q}(P, x)$ and $f_{g, q}(Q, x)$, we have
    \begin{align}
        & f_{g, q}(Q, x) - f_{g, q}(P, x) \notag \\
        & \leq \norm{(d(x, p) + d_H(P, Q), g(p) + c \cdot d_H(P, Q))}_q - \norm{(d(x, p), g(p))}_q \\
        & \leq \norm{(d(x, p) + d_H(P, Q) - d(x, p), g(p) + c \cdot d_H(P, Q) - g(p))}_q \\
        & = \norm{(d_H(P, Q), c \cdot d_H(P, Q))}_q,
    \end{align}
    and by the same reasoning with $P$ and $Q$ swapped, we have
    \begin{equation}
        f_{g, q}(P, x) - f_{g, q}(Q, x) \leq \norm{(d_H(P, Q), c \cdot d_H(P, Q))}_q,
    \end{equation}
    which combined gives us
    \begin{align}
        \norm{f_{g, q}(P, \cdot) - f_{g, q}(Q, \cdot)}_\infty
        & = \sup_{x \in \R^d} |f_{g, q}(P, x) - f_{g, q}(Q, x)| \\
        & \leq \norm{(d_H(P, Q), c \cdot d_H(P, Q))}_q \\
        & = d_H(P, Q) \cdot \norm{(1, c)}_q \\
        & = d_H(P, Q) \cdot (1 + c^q)^{1/q},
    \end{align}
    which is exactly the condition for $d$-PC Lipschitz continuity with $d = (1 + c^q)^{1/q}$.

    For finite point clouds $P$, the weighted \v{C}ech filtration induces 
    pointwise finite-dimensional persistence modules~(\cite{anai2020dtm},
    Proposition~3.1), which are by Lemma~\ref{lem:tameness_pfd} $q$-tame.
    By Lemma~\ref{lem:pc_lipschitz_stable}, the
    weighted \v{C}ech filtration is $d$-stable with $d = (1 + c^q)^{1/q}$.
\end{proof}

\section{Generalised \v{C}ech filtrations}

The nearest-neighbour distance function
$f_{\mathrm{dist}}(P, x) = \min_{p \in P} d(x, p)$ can be
seen as taking a minimum over a set of functions $h_p(x) = d(x, p)$, each
centered around a point $p \in P$. We can generalise this to
$f(P, x) = \min_{p \in P} h(x, p)$, where $h(x, p) : \R^d \times \R^d \to \R$ is
a more general ``kernel'' function. We refer to GDFs of this form as defining
\emph{generalised \v{C}ech filtrations}. The stability of such GDFs depends on
the properties of the kernel $h$.

\subsection{Isotropic, monotone and Lipschitz kernels}

Borrowing terminology from kernel methods, we call a kernel \emph{isotropic}
if it depends only on the distance between its
arguments~\cite{genton2001classes}.
\begin{definition}[Isotropic kernel]
    A kernel $h : \R^d \times \R^d \to \R$ is \emph{isotropic} if there exists a
    function $k : \R_+ \to \R$ such that $h(x, p) = k(d(x, p))$ for all
    $x, p \in \R^d$.
\end{definition}
Such kernels correspond to generalised \v{C}ech filtrations where the radius of
the balls grows with the same rate for each point $p \in P$, but that
rate may not be uniform.

A generalised \v{C}ech filtration is stable if the kernel $h$ is isotropic,
monotone and Lipschitz continuous:
\begin{theorem}
    \label{thm:stable_isotropic}
    Let $h : \R^d \times \R^d \to \R$ be a kernel that is isotropic, such that
    $k$ is monotone increasing and $c$-Lipschitz continuous. Then the
    generalised \v{C}ech filtration using $h$ is $c$-stable.
\end{theorem}
\begin{proof}
    We want to show that the corresponding GDF $f$ is $c$-PC Lipschitz. Let $P,
    Q \subseteq \R^d$ be two finite point clouds. Fix a point $x \in \R^d$ and
    $p \in P$ be such that $f(P, x) = k(d(x, p))$. There exists $q' \in Q$ such
    that $d(p, q') \leq d_H(P, Q)$ and
    \begin{equation}
        d(x, q') \leq d(x, p) + d(p, q') \leq d(x, p) + d_H(P, Q).
    \end{equation}
    Since $k$ is monotone and $c$-Lipschitz, we have:
    \begin{align}
        f(Q, x) & = \min_{q \in Q} k(d(x, q)) \\
        & \leq k(d(x, q')) \\
        & \leq k(d(x, p) + d_H(P, Q)) \\
        & \leq k(d(x, p)) + c \cdot d_H(P, Q) \\
        & = f(P, x) + c \cdot d_H(P, Q),
    \end{align}
    and by the same reasoning with $P$ and $Q$ swapped, we have
    \begin{equation}
        f(P, x) \leq f(Q, x) + c \cdot d_H(P, Q).
    \end{equation}
    Combining these inequalities, we obtain
    \begin{align}
        \norm{f(P, \cdot) - f(Q, \cdot)}_\infty
        & = \sup_{x \in \R^d} |f(P, x) - f(Q, x)| \\
        & \leq c \cdot d_H(P, Q).
    \end{align}

    The induced persistence modules of $f(P, x)$ are $q$-tame by the same
    reasoning as in the proof of Lemma~\ref{lem:tameness_pfd}. Therefore, by
    Lemma~\ref{lem:pc_lipschitz_stable}, the generalised \v{C}ech
    filtration using $h$ is $c$-stable.
\end{proof}

\subsection{Kernels Lipschitz in $p$}

We generalise further by considering $f(P, x) = \min_{p \in P} h(x, p)$
where the kernel $h(x, p)$ is $c$-Lipschitz with respect to its second argument
$p$, for any fixed $x$:
\begin{equation}
    |h(x, p_1) - h(x, p_2)| \leq c \cdot d(p_1, p_2).
\end{equation}
Such kernels correspond to generalised \v{C}ech filtrations where the standard
process of growing balls around points $p \in P$ is modified significantly;
the sublevel sets $f_P^{-1}(-\infty, a]$ may not be symmetric, connected, grow
at the same rate for different $p \in P$ or even include the point $p$ itself.
The only restriction imposed by Lipschitzness of the kernel is that as a point
$p$ moves, the shape changes in a controlled manner. Somewhat surprisingly, even
this weak condition coupled with $q$-tameness is sufficient for stability.
\begin{theorem}
    Let $h : \R^d \times \R^d \to \R$ be a kernel that is $c$-Lipschitz
    continuous with respect to its second argument. Then the generalised
    \v{C}ech filtration using $h$ is $c$-stable if the induced persistence
    modules are $q$-tame.
\end{theorem}
\begin{proof}
    Fix $x \in \R^d$ and $p \in P$. Then we have $q' \in Q$ such that $d(p, q')
    \leq d_H(P, Q)$. By Lipschitzness of $h$, we have
    \begin{align}
        |h(x, q') - h(x, p)| & \leq c \cdot d(q', p) \leq c \cdot d_H(P, Q) \\
        f(Q, x) \leq h(x, q') & \leq c \cdot d_H(P, Q) + h(x, p),
    \end{align}
    and as this holds for any $p \in P$, we have
    \begin{align}
        f(Q, x) & \leq c \cdot d_H(P, Q) + f(P, x) \\
        f(Q, x) - f(P, x) & \leq c \cdot d_H(P, Q).
    \end{align}
    By the same reasoning, we have the same with $P$ and $Q$ swapped,
    and combining the two inequalities, we obtain
    \begin{equation}
        |f(P, x) - f(Q, x)| \leq c \cdot d_H(P, Q)
    \end{equation}
    for any $x$, which by Lemma~\ref{lem:pc_lipschitz_stable} implies that
    $f$ is $c$-stable.
\end{proof}
This theorem generalises Theorem~\ref{thm:stable_isotropic},
as any isotropic kernel $h(x, p) = k(d(x, p))$ with $k$ being $c$-Lipschitz
automatically is $c$-Lipschitz with respect to $p$. This follows because the
distance function is 1-Lipschitz, and composing it with a $c$-Lipschitz function
yields a $c$-Lipschitz function~\cite{weaver2018lipschitz}.
Nonetheless, we included the less general case of
Theorem~\ref{thm:stable_isotropic}, as many common kernels fit these conditions.

The $q$-tameness condition for the induced persistence modules, while crucial,
is not always straightforward to verify directly for a given kernel $h$. In the
following lemma, we provide sufficient conditions for this.
\begin{lemma}
    \label{lem:tameness_kernels}
    Let $f(P, x) = \min_{p \in P} h(x, p)$. If, for every $p \in P$,
    the function $h_p(x) \coloneqq h(x, p)$ is continuous in $x$,
    bounded below and proper (i.e., $h_p^{-1}(K)$ is compact for every compact
    $K \subseteq \R$), then $f_P(x)$ is continuous, bounded below and proper.
    Consequently, by Theorem~\ref{thm:tameness_condition}, the induced
    persistence modules are $q$-tame.
\end{lemma}
\begin{proof}
    To use Theorem~\ref{thm:tameness_condition}, we need to show for $f_P$:
    \begin{enumerate}
        \item Continuity: $f_P(x)$ is the minimum of a finite set of continuous
            functions $h_p(x)$, thus $f_P$ is continuous.
        \item Bounded below: If each $h_p(x) \geq M_p$ for some $M_p$,
            then $f_P(x) = \min_p h_p(x) \geq \min_p M_p$, so $f_P$ is bounded
            below.
        \item Properness: A function $g$ is proper if and only if for every
            sequence $\{x_i\}$ such that $x_i \to \infty$, we have
            $g(x_i) \to \infty$~(\cite{lee2003smooth}, Proposition~2.17).
            As every $h_p(x)$ is proper, then $p\in P$, we have
            $h_p(x_i) \to \infty$. Since $f_P(x_i) = \min_p h_p(x_i)$, it follows
            that $f_P(x_i) \to \infty$ as well. Thus, $f_P$ is proper.
    \end{enumerate}
    With $f_P$ continuous, bounded below, and proper,
    Theorem~\ref{thm:tameness_condition} guarantees that the induced persistence
    modules are $q$-tame.
\end{proof}

\subsection{Kernels depending on the point cloud}

We further generalise by allowing the kernel itself to depend on the point cloud
$P$:
\begin{equation}
    f(P, x) = \min_{p \in P} h(x, p, P).
\end{equation}
\begin{example}
    \label{ex:mahalanobis}
    Consider $h(x, p, P)$ that is the pairwise Mahalanobis distance between $x$
    and $p$, defined by locally estimated covariance of the point cloud
    $P$~\cite{mclachlan1999mahalanobis}.
    Let $N_k(p, P)$ be the set of $k$ nearest neighbours of $p$ in $P$. The
    covariance estimate $\Sigma_p$ using $k$ nearest neighbours of $p$ is given
    by
    \begin{equation}
        \Sigma_p = \frac{1}{k} \sum_{q \in N_k(p, P)} (q - p)(q - p)^\top.
    \end{equation}
    We would like to invert $\Sigma_p$, but it may be numerically unstable or
    not invertible if $k$ is too small or if some points in $N_k(p, P)$ are
    close to each other. To avoid this, we add a small positive
    regularisation term $\varepsilon I$, where $I$ is the identity matrix.
    The Mahalanobis distance is then defined as
    \begin{equation}
        h(x, p, P) = \sqrt{(x - p)^\top (\Sigma_p + \varepsilon I)^{-1} (x - p)}.
    \end{equation}
    Geometrically, this GDF defines a generalised \v{C}ech filtration where the
    sublevel sets $f_P^{-1}(-\infty, a]$ are unions of ellipsoids centered at
    $p$ with each ellipsoid having axes aligned with the eigenvectors of
    $\Sigma_p + \varepsilon I$ and lengths proportional to the square roots of
    the eigenvalues of $\Sigma_p + \varepsilon I$. The regularisation term
    ensures that the ellipsoids are not degenerate. The standard \v{C}ech
    filtration can be seen as a special case of this GDF with
    $(\Sigma_p + \varepsilon I)$ replaced by the identity matrix.
\end{example}
We prove two theorems that guarantee stability of such GDFs.
\begin{theorem}
    \label{thm:pc_kernel_stability}
    Let $h : \R^d \times \R^d \times \mathcal{P}(\R^d) \to \R$ be a kernel that
    is $c$-Lipschitz continuous with respect to its second argument (the point
    $P$) and $d$-Lipschitz continuous with respect to its third argument (the
    point cloud $P$, using $d_H$ on $\mathcal{P}(\R^d)$):
    \begin{align}
        |h(x, p_1, P) - h(x, p_2, P)| & \leq c \cdot d(p_1, p_2), \\
        |h(x, p, P_1) - h(x, p, P_2)| & \leq d \cdot d_H(P_1, P_2).
    \end{align}
    Then the GDF $f(P, x) = \min_{p\in P} h(x, p, P)$ is $(c + d)$-stable if
    the induced persistence modules are $q$-tame.
\end{theorem}
\begin{proof}
    Fix $x \in \R^d$ and $p \in P$. Then we have $q' \in Q$ such that $d(p, q')
    \leq d_H(P, Q)$. By Lipschitzness of $h$, we have
    \begin{align}
        & |h(x, p, P) - h(x, q', Q)| \\
        & \leq |h(x, p, P) - h(x, p, Q)| + |h(x, p, Q) - h(x, q', Q)| \\
        & \leq d \cdot d_H(P, Q) + c \cdot d(p, q'),
    \end{align}
    and as this holds for any $p \in P$, we have
    \begin{align}
        f(Q, x) - f(P, x) & \leq h(x, q', Q) - f(P, x) \\
        & \leq h(x, q', Q) - h(x, p, P) \\
        & \leq (c + d) \cdot d_H(P, Q).
    \end{align}
    By the same reasoning, we have the same inequality with $P$ and $Q$ swapped,
    and combining the two inequalities, we obtain
    \begin{equation}
        |f(P, x) - f(Q, x)| \leq (c + d) \cdot d_H(P, Q).
    \end{equation}
    By Lemma~\ref{lem:pc_lipschitz_stable}, this implies that $f$ is
    $(c + d)$-PC Lipschitz.
\end{proof}
Using this theorem, we show in Appendix~\ref{app:mahalanobis} that the GDF from
Example~\ref{ex:mahalanobis} is stable.
\begin{theorem}
    Let $h : \R^d \times \R^d \times \mathcal{P}(\R^d) \to \R$ be a kernel that
    is $c$-Lipschitz continuous with respect to its second argument and
    $d$-Lipschitz continuous with respect to every element in $P$, i.e.:
    \begin{align}
        |h(x, p_1, P) - h(x, p_2, P)| & \leq c \cdot d(p_1, p_2), \\
        |h(x, p, P \cup \{p_1\}) - h(x, p, P \cup \{p_2\})| & \leq d \cdot d(p_1, p_2) \\
        |h(x, p, \{p_1\}) - h(x, p, \{p_2\})| & \leq d \cdot d(p_1, p_2). 
    \end{align}
    Then the
    generalised \v{C}ech filtration using $h$ is
    $(c + d \cdot \max(|P|, |Q|))$-stable if the induced persistence modules are
    $q$-tame.
\end{theorem}
\begin{proof}
    If $|P| = |Q|$, we can match every point $p_i \in P$ with a point
    $q_i \in Q$ such that $d(p_i, q_i) \leq d_H(P, Q)$, and thus we have
    \begin{align}
        & |h(x, p, \{p_i\}_{i = 1}^n) - h(x, p, \{q_i\}_{i = 1}^n)| \\
        & = |h(x, p, \{p_i\}_{i = 1}^{n-1} \cup \{p_n\}) - h(x, p, \{p_i\}_{i = 1}^{n-1} \cup \{q_n\})| \\
        & \leq |h(x, p, \{p_i\}_{i = 1}^{n-1}) - h(x, p, \{q_i\}_{i = 1}^{n-1})| + d \cdot d_H(P, Q) \\
        & \leq |h(x, p, \{p_i\}_{i = 1}^{n-2}) - h(x, p, \{q_i\}_{i = 1}^{n-2})| + 2 \cdot d \cdot d_H(P, Q) \\
        & \leq \ldots \\
        & \leq |P| \cdot d \cdot d_H(P, Q).
    \end{align}
    If $|P| < |Q|$, we can add points to $P$ that are arbitrarily close to
    existing points in $P$ such that the Hausdorff distance
    $d_H(P, Q)$ changes arbitrarily little, and $f(P, x)$ also changes
    arbitrarily little. The same is true with $P$ and $Q$ swapped. Thus, we can
    assume that $|P| = |Q|$ without loss of generality. This means that
    \begin{equation}
        |h(x, p, P) - h(x, p, Q)| \leq d \cdot \max(|P|, |Q|) \cdot d_H(P, Q).
    \end{equation}
    Following the same reasoning as in the previous proof, we have
    \begin{align}
        & |h(x, p, P) - h(x, q', Q)| \\
        & \leq |h(x, p, P) - h(x, p, Q)| + |h(x, p, Q) - h(x, q', Q)| \\
        & \leq d \cdot \max(|P|, |Q|) \cdot d_H(P, Q) + c \cdot d_H(P, Q).
    \end{align}
\end{proof}

The conditions on the kernel for the induced persistence modules to be
$q$-tame are exactly the same as the ones in Lemma~\ref{lem:tameness_kernels}.

\section{Morse functions}
The PC-Lipschitz condition is a strong global condition, which may not always
hold for some stable GDFs.
\begin{example}
    Consider a \v{C}ech-like GDF
    \begin{equation}
        f_P(x) = \min_{p \in P} d(x, p)^2,
    \end{equation}
    where the balls grow faster the larger they are. While this function is not
    Lipschitz continuous on the whole space $\R^d$, it is Lipschitz continuous
    on some subset of $\R^d$ that covers the point cloud $P$. We can intuit that
    Lipschitz continuity everywhere is too strong of a condition, as it does not
    matter how the function behaves far away from $P$.
\end{example}
\begin{example}
    Consider a GDF of the form
    \begin{equation}
        f_P(x) = \norm{x - g(P)},
    \end{equation}
    where $g : \mathcal{P}(\R^d) \to \R^d$ is an arbitrary function of the point
    cloud $P$. This GDF is not Lipschitz continuous for many choices of $g$,
    but it is stable for any $g$, as it only has a single critical value at zero,
    which results in a single point $(0, \infty)$ in the 0-dimensional persistence
    diagram and no points in higher dimensions.
\end{example}

Motivated by the two examples above, we can relax the PC-Lipschitz condition by
restricting ourselves to \emph{Morse functions}, that is, smooth functions $f_P
: \R^d \to \R$ whose critical points $x \in \crit(f_P)$ (where the gradient
vanishes) are non-degenerate, i.e., the Hessian matrix $H(f_P)(x)$ is
non-singular~\cite{matsumoto2002introduction}.
\begin{theorem}
    Let $f : \mathcal{P}(\R^d) \times \R^d \to \R$ be a GDF such that for any
    finite point clouds $P, Q \subseteq \R^d$, the functions $f_P$ and $f_Q$ are
    Morse, and all sublevel sets $f_P^{-1}(-\infty, a]$ and $f_Q^{-1}(-\infty, a]$
    are compact. Furthermore, let there exist a bijection
    $\pi: \crit(f_P) \to \crit(f_Q)$ of critical points of $f_P$ and $f_Q$
    such that the index of $x$ is equal to the index of $\pi(x)$ for all
    $x \in \crit(f_P) \cup \crit(f_Q)$, and the following condition holds:
    \begin{equation}
        \label{eq:morse_crit}
        \forall x \in \crit(f_P):
        |f_P(x) - f_Q(\pi(x))| \leq c \cdot d_H(P, Q).
    \end{equation}
    Then the GDF $f$ is $c$-stable, if the induced persistence modules are
    $q$-tame.
\end{theorem}
\begin{proof}
    As $f_P$ is Morse and its sublevel sets are compact, each sublevel set
    $f_P^{-1}(-\infty, a]$ has the homotopy type of a finite CW-complex, with
    one cell of dimension $\lambda$ for each critical point of index $\lambda$
    in $f_P^{-1}(-\infty, a]$~(\cite{milnor1963morse},~Theorem~3.5 and the
    remark following it). Let us denote such a CW-complex by $C_P(a)$. The
    previous statement can be written concisely as
    \begin{equation}
        \forall a \in \R \ \  C_P(a) \simeq f_P^{-1}(-\infty, a].
    \end{equation}
    Let $d = c \cdot d_H(P, Q)$.
    We now show that $C_P(a)$ as a set is included in $C_Q(a + d)$.
    Consider a cell $e^\lambda$ in $C_P(a)$. This cell corresponds to a critical
    point $x \in \crit(f_P)$ of index $\lambda$ such that $f_P(x) \leq a$.
    By the condition~\eqref{eq:morse_crit}, we have
    \begin{equation}
        f_Q(\pi(x)) \leq f_P(x) + d \leq a + d.
    \end{equation}
    Thus, we have a critical point $\pi(x) \in \crit(f_Q)$ also of index
    $\lambda$ such that $f_Q(\pi(x)) \leq a + d$. This means that
    the cell $e^\lambda$ in $C_P(a)$ corresponds to a cell of the same dimensionality in
    $C_Q(a + d)$. Since this holds for any cell in $C_P(a)$, we
    have \begin{equation}
        C_P(a) \subseteq C_Q(a + d).
    \end{equation}
    By the same reasoning, we can show that $C_Q(a)$ is included in
    $C_P(a + d)$. We also trivially have that
    $C_P(a) \subseteq C_P(a')$ for any $a' \geq a$ and the same for $C_Q$.

    Similarly to the proof of stability of the \v{C}ech filtration using
    interleaving, the following diagram commutes up to homotopy, as all maps are
    either inclusions or homotopies:
    \begin{equation}
        \begin{tikzcd}
            f^{-1}_P(-\infty, a] \arrow[hook]{r} \arrow[leftrightarrow]{d}{\simeq}
            & f^{-1}_P(-\infty, a + d] \arrow[hook]{r} \arrow[leftrightarrow]{d}{\simeq}
            & f^{-1}_P(-\infty, a + 2d] \arrow[leftrightarrow]{d}{\simeq} \\
            C_P(a) \arrow[hook]{r} \arrow[hook]{dr}
            & C_P(a + d) \arrow[hook]{r} \arrow[hook]{dr}
            & C_P(a + 2d) \\
            C_Q(a) \arrow[hook]{r} \arrow[hook]{ur}
            & C_Q(a + d) \arrow[hook]{r} \arrow[hook]{ur}
            & C_Q(a + 2d) \\
            f^{-1}_Q(-\infty, a] \arrow[hook]{r} \arrow[leftrightarrow]{u}{\simeq}
            & f^{-1}_Q(-\infty, a + d] \arrow[hook]{r} \arrow[leftrightarrow]{u}{\simeq}
            & f^{-1}_Q(-\infty, a + 2d] \arrow[leftrightarrow]{u}{\simeq}
        \end{tikzcd}
    \end{equation}
    Thus we have
    \begin{equation}
        d_i(\{f^{-1}_P(-\infty, a]\}_a, \{f^{-1}_Q(-\infty, a]\}_a) \leq d,
    \end{equation}
    and similarly to the proof of stability of the \v{C}ech filtration, we have
    that the bottleneck distance between the persistence diagrams is bounded by
    $d$ from above.
\end{proof}
It should be noted that this theorem is not a strict generalisation of previous
theorems, as there are GDFs that are PC-Lipschitz but which are not Morse.

For conditions that guarantee $q$-tameness of induced persistence modules
of Morse functions, we refer the reader to Theorem~8.1.4 and Corollary~8.1.12 of
Maximilian Schmahl's PhD thesis~\cite{schmahl2023topics}.