text:
\begin{document}

\maketitle

\begin{abstract}
Persistence diagrams are important descriptors in Topological Data Analysis.
Due to the nonlinearity of the space of persistence diagrams equipped with their {\em diagram distances},
most of the recent attempts at using persistence diagrams in machine learning have been done through
kernel methods, i.e., embeddings of persistence diagrams into Reproducing Kernel Hilbert Spaces,
in which all computations can be performed easily. Since persistence diagrams enjoy theoretical stability
guarantees for the diagram distances, the {\em metric properties} of the feature map, i.e., the relationship
between the Hilbert distance and the diagram distances, are of central interest for understanding if the
persistence diagram guarantees carry over to the embedding. In this article, we study the possibility of embedding
persistence diagrams into separable Hilbert spaces, with bi-Lipschitz maps. In particular,
we show that for several stable embeddings into infinite-dimensional Hilbert spaces defined in the literature,
any lower bound must depend on the cardinalities of the persistence diagrams,
and that when the Hilbert space is finite dimensional, finding a bi-Lipschitz embedding is impossible, even when restricting
the persistence diagrams to have bounded cardinalities.
\end{abstract}

\section{Introduction}
\label{sec:intro}

The increase of available data in both academia and industry have been exponential over the past few decades,
making data analysis ubiquitous in many different fields of science. Machine learning has proved to be
one of the most prominent field of data science, leading to astounding results in various applications, such as
image and signal processing. Topological Data Analysis (TDA)~\cite{Carlsson09a} is one specific field of machine learning, which
focuses more on {\em complex} rather than big data. The general assumption of TDA is that data is actually sampled
from geometric or low-dimensional domains, whose geometric features are relevant to the analysis.
These geometric features are usually encoded in a mathematical object called {\em persistence diagram},
which is roughly a set of points in the plane, each point representing a topological feature whose size is
contained in the coordinates of the point. Persistence diagrams have been proved to bring complementary
information to other traditional descriptors in many different applications, often leading to large result improvements.
This is also due to the so-called {\em stability properties} of the persistence diagrams, which state that persistence diagrams computed on similar data
are also very close in the diagram distances~\cite{Cohen07,Bauer13b,Chazal16a}.

Unfortunately, the use of persistence diagrams in machine learning methods is not straightforward, since many algorithms expect data to be
Euclidean vectors, while persistence diagrams are sets of points with possibly different cardinalities. Moreover, the {\em diagram distances}
used to compare persistence diagrams are computed with optimal matchings, and thus quite different from Euclidean metrics.
The usual way to cope with such difficult data is to use {\em kernel methods}. A kernel is a symmetric function on the data
whose evaluation on a pair of data points equals the scalar product of the images of these points
under a \emph{feature map} into a Hilbert space, called the {\em Reproducing Kernel Hilbert Space} of the kernel.

Many algorithms can be {\em kernelized}, such as PCA and SVM, allowing one to handle non-Euclidean data as soon as a kernel or a feature map is available.

Hence, the question of defining a feature map into a Hilbert space has been
intensively studied in the past few years, and, as of today, various methods can be implemented,
either into finite or infinite dimensional Hilbert spaces~\cite{Bubenik15, Carriere15a, Reininghaus15, Kusano16, Adams17, Carriere17e, Hofer17}.
Since persistence diagrams are known to enjoy stability properties, it is also natural to ask the same guarantee for their
embeddings. Hence, all feature maps defined in the literature satisfy a stability property stating that the Hilbert
distance between the image of the persistence diagrams is upper bounded by the diagram distances. A more difficult question is to
prove whether a lower bound also holds or not. Even though one attempt has already been made to show such a lower bound
for the so-called Sliced Wasserstein distance in~\cite{Carriere17e}, the question remains open in general.

\paragraph*{Contributions.} In this article, we tackle the general question of defining
bi-Lipschitz embeddings of persistence diagrams into separable Hilbert spaces. More precisely, we show that:

\begin{itemize}
\item For several stable feature maps defined in the literature, if such a bi-Lipschitz embedding exists, then

the lower bound goes to 0 or the upper bound goes to $+\infty$ as the number of points and their coordinates increase in the persistence diagrams
(Theorem~\ref{thm:th1} and Proposition~\ref{prop:fmap}).

\item Such a bi-Lipschitz embedding does not exist if the Hilbert space is finite dimensional (Theorem~\ref{th:nonembedRn}),
\end{itemize}

Finally, we also provide experimental evidence of this behavior by computing the metric distortions of various feature maps for persistence diagrams with increasing cardinalities.

\paragraph*{Related work.}
Feature maps for persistence diagrams can be classified into two different classes, depending whether the corresponding Hilbert space is
finite or infinite dimensional.

In the infinite dimensional case, the first attempt was that proposed in~\cite{Bubenik15}, in which persistence diagrams are turned into
$L^2$ functions, called Landscapes, by computing the homological rank functions given by the persistence diagram points.
Another common way to define a feature map is to see the points of the persistence diagrams as centers
of Gaussians with a fixed bandwidth, weighted by the distance of the point to the diagonal. This is the approach
originally advocated in~\cite{Reininghaus15}, and later generalized in~\cite{Kusano17}, leading to the so-called
{\em Persistence Scale Space} and {\em Persistence Weighted Gaussian} feature maps.
Another possibility is to define a Gaussian-like feature map by using the {\em Sliced Wasserstein distance} between persistence diagrams, which
is conditionnally negative definite. This implicit feature map, called the {\em Sliced Wasserstein} map, was defined in~\cite{Carriere17e}.

In the finite dimensional case, many different possibilities are available. One may consider evaluating a family of tropical polynomials
onto the persistence diagram~\cite{Verovsek16}, taking the sorted vector of the pairwise distances
between the persistence diagram points~\cite{Carriere15a}, or computing the coefficients of a complex polynomial whose roots are given by the persistence diagram points~\cite{diFabio15}.
Another line of work was proposed in~\cite{Adams17} by discretizing the Persistence Scale Space feature map. The idea is to discretize the plane into a fixed grid, and then compute
a value for each pixel by integrating Gaussian functions centered on the persistence diagram points. Finally, persistence diagrams have been incorporated in deep learning
frameworks in~\cite{Hofer17}, in which Gaussian functions (whose means and variances are optimized by the neural network during training)
are integrated against persistence diagrams seen as discrete measures.

\section{Background}
\label{sec:background}

\subsection{Persistence Diagrams}

{\em Persistent homology} is a technique of TDA coming from topological algebra that allows the user to compute and encode topological information
of datasets in a compact descriptor called the {\em persistence diagram}. Given a dataset $X$, often given in the form of a point cloud in $\R^n$,
and a continuous and real-valued function $f:X\rightarrow\R$, the persistence diagram of $f$ can be computed under mild conditions (the function has to be {\em tame},
see~\cite{Chazal16a} for more details), and consists in a finite set of points with multiplicities
in the upper-diagonal half-plane $\Dg(f)=\{(x_i,y_i)\}\subset \{(x,y)\in\R^2:y > x\}$.
This set of points is computed from the family of
{\em sublevel sets} of $f$, that is the sets of the form $f^{-1}((-\infty,\alpha])$, for some $\alpha\in\R$.
More precisely, persistence diagrams encode the different {\em topological events} that occur as $\alpha$ increases from $-\infty$ to $+\infty$.
Such topological events include creation and merging of connected components and cycles in every dimension; see Figure~\ref{fig:examplePersistence}.
Intuitively, persistent homology records, for each topological feature that appears in the family of sublevel sets, the value $\alpha_b$
at which the feature appears, called the {\em birth value}, and the value $\alpha_d$ at which it gets merged or filled in, called the {\em death value}.
These values are then used as coordinates for a corresponding point in the persistence diagram. Note that
several features may have the same birth and death values, so points in the persistence diagram have multiplicities.
Moreover, since $\alpha_d\geq \alpha_b$, these points are always
located above the diagonal $\Delta=\{(x,x):x\in\R\}$. A general intuition about persistence diagrams is that the distance of a point to $\Delta$ is a direct measure of its relevance: if a point is close to $\Delta$, it means that the corresponding cycle got filled in right after its appearance, thus suggesting that
it is likely due to noise in the dataset. On the contrary, points that are far away from $\Delta$ represent cycles with a significant life span, and are more likely to be
relevant for the analysis.
We refer the interested reader to~\cite{Edelsbrunner10,Oudot15} for more details about persistent homology.

\begin{figure}
\centering
\includegraphics[width=14cm]{examplePersistence}
\caption{\label{fig:examplePersistence} Example of persistence diagram computation. The space we consider is a blurry image of a zero, and the function $f$ that we use is the grey level value on each
pixel. We show four different sublevel sets of $f$. For each sublevel set, the corresponding pixels are displayed in pink color.

In the first sublevel set, two connected components are present in the sublevel set, so we start two intervals $I_1$ and $I_2$.
In the second one, one connected component got merged to the other,
so we stop the corresponding interval $I_2$, and a cycle (loop) is created, so we start a third interval $I_3$.
In the third sublevel set, a new small cycle is created, as well as three more connected
components. In the fourth sublevel set, all pixels belong to the set: all cycles are filled in and all connected components are merged together, so we stop all intervals.
Finally, each interval $I_k$ is represented as a point $P_k$ in the plane (using the endpoints as coordinates).
}
\end{figure}

\paragraph*{Notation.} Let $\SpD$ be the space of persistence diagrams with countable number of points.
More formally, $\SpD$ can be equivalently defined as a functional space
$\{m:\R^2\setminus\Delta\rightarrow\N \,:\, {\rm supp}(m) \text{ is countable}\}$, where each point $q\in{\rm supp}(m)$ is a point
in the corresponding persistence diagram with multiplicity $m(q)$.

Let $\SpND$ be the space of persistence diagrams with less than $N$ points, i.e., $\SpND=\{m:\R^2\setminus\Delta\rightarrow\N \,:\, \sum_q m(q) < N\}$.

Let $\SpLD$ be the space of persistence diagrams included in $[-L,L]^2$, i.e., $\SpLD=\{m:\R^2\setminus\Delta\rightarrow\N \,:\,{\rm supp}(m) \subset [-L,L]^2\}$.

Finally, let $\SpNLD$ be the space of persistence diagrams with less than $N$ points included in $[-L,L]^2$, i.e., $\SpNLD=\SpND\cap\SpLD$.

Obviously, we have the following sequences of (strict) inclusions:
$\SpNLD\subset\SpND\subset\SpD$, and
$\SpNLD\subset\SpLD\subset\SpD$.

\paragraph*{Diagram distances.} Persistence diagrams can be efficiently compared using the {\em diagram distances}, which is a family of
distances parametrized by an integer $p$ that rely on the computation of {\em partial matchings}. Recall that two persistence diagrams
$\Dg_1$ and $\Dg_2$ may have different number of points. A {\em partial matching} $\Gamma$ between $\Dg_1$ and $\Dg_2$ is
a subset of $\Dg_1\times\Dg_2$. It comes along with $\Gamma_1$ (resp. $\Gamma_2$), which is the set of points of $\Dg_1$ (resp. $\Dg_2$)
that are not matched to a point of $\Dg_2$ (resp. $\Dg_1$) by $\Gamma$.
The $p$-cost of $\Gamma$ is given as:
\[
c_p(\Gamma) =\sum_{(p,q)\in\Gamma}\|p-q\|_\infty^p + \sum_{p\in\Gamma_1}\|p-\Delta\|_\infty^p + \sum_{q\in\Gamma_2}\|q-\Delta\|_\infty^p.
\]
The $p$-diagram distance is then defined as the cost of the best partial matching:

\begin{defin}
Given two persistence diagrams $\Dg_1$ and $\Dg_2$, the $p$-{\em diagram distance} $d_p$ is defined as:
$$d_p(\Dg_1,\Dg_2)={\rm inf}_{\Gamma}\ \sqrt[\leftroot{-3}\uproot{3}p]{c_p(\Gamma)}.$$
\end{defin}

Note that in the literature, these distances are often called the {\em Wasserstein distances} between persistence diagrams.
Here, we follow the denomination of~\cite{Carriere17e}. In particular, taking a maximum instead of a sum
in the definition of the cost,
\[
c_\infty(\Gamma) =\max_{(p,q)\in\Gamma}\|p-q\|_\infty + \max_{p\in\Gamma_1}\|p-\Delta\|_\infty + \max_{q\in\Gamma_2}\|q-\Delta\|_\infty.
\]
allows to add one more distance in the family, the {\em bottleneck distance} $d_\infty(\Dg_1,\Dg_2)={\rm inf}_\Gamma\ c_\infty(\Gamma)$.

\paragraph*{Stability.} A useful property of persistence diagrams is {\em stability}. Indeed, it is well known in the literature that
persistence diagrams computed from close functions are close themselves in the bottleneck distance:

\begin{thm}[\cite{Cohen07,Chazal16a}]
Given two tame functions $f,g:X\rightarrow\R$, one has the following inequality:
\begin{equation}\label{eq:stab}
d_\infty(\Dg(f),\Dg(g))\leq \|f-g\|_\infty.
\end{equation}
\end{thm}
In other words, the map $\Dg$ is 1-Lipschitz.
Note that stability results exist as well for the other diagram distances,
but these results are weaker than the above Lipschitz condition, and they require more conditions---see~\cite{Oudot15}.

\begin{comment}
\subsection{Kernel Methods}

Kernel methods provide techniques for handling data that does not naturally live in a vectors with a well-defined scalar product (such as persistence diagrams).
The idea is to send the data in a specific Hilbert space called {\em Reproducing Kernel Hilbert Space} (RKHS), and to use its corresponding scalar product.

\begin{defin}
Let $X$ be a set, and $\HS\subset\R^X$ be a Hilbert space.
Then $\HS$ is a RKHS if and only if the mapping $\HS \rightarrow \R$, $f  \mapsto f(x)$ is continuous for any $x\in X$.

\end{defin}

Then, by the Riesz representation theorem, there exists $k_x\in\HS$ such that $f(x)=\langle f,k_x\rangle_\HS$. The
function $\Phi:x\mapsto k_x$ is called the {\em feature map}, and the symmetric function $k(x,y)=k_x(y)=k_y(x)=\langle k_x,k_y\rangle_\HS$
is called the {\em kernel} of $\HS$.
Reciprocally, it can be shown that any symmetric function is the kernel of at most one RKHS, up to isometry.
Scalar products and distances can be easily computed in $\HS$ with
\[\langle k_x,k_y\rangle_\HS=k(x,y)\]
(which is called the reproducing property of $\HS$)
and
\[\|k_x-k_y\|^2_\HS=\langle k_x-k_y,k_x-k_y\rangle_\HS=k(x,x)+k(y,y)-2k(x,y).\]
Moreover, it is easy to characterize the symmetric functions that are actually kernels, thanks to the following result:

\begin{thm}
Let $X$ be a set. Given a symmetric function $k:X\times X\rightarrow\R$,
there exists a corresponding RKHS (i.e., $k$ is a kernel) if and only if $k$ is positive definite:
$\sum_{i,j}a_i a_j k(x_i,x_j)\geq 0$ for any $a_1,\dots,a_n\in\R$ and $x_1,\dots,x_n\in X$.
\end{thm}

Finally, Schönberg's theorem~\cite{Berg84} is very useful to define
Gaussian-like kernels:

\begin{thm}\label{th:Berg}
Let $X$ be a set, and $d:X\times X\rightarrow \R$ a symmetric function.
Then the Gaussian $k(x,x')={\rm exp}\left(-d(x,x')/2\sigma^2\right)$ is a kernel for all $\sigma>0$
if and only if $d$ is {\em conditionally negative definite}, i.e., $\sum_{i,j}a_i a_j d(x_i,x_j)\leq 0$ for any $x_1,\dots,x_n\in X$
and $a_1,\dots,a_n\in\R$ such that $\sum_i a_i = 0$.
\end{thm}

Note that $d$ need not be a metric.
Note also that, given a kernel $k$ on a set $X$, the square of the corresponding RKHS distance
$d_k^2$ is always conditionally negative definite.
Indeed, let $x_1,\dots,x_n\in X$ and $a_1,\dots,a_n\in\R$ whose sum is zero.
Then we have the following equalities:
$$
\sum_{i,j} a_i a_j d_k^2(x_i,x_j)
= \sum_{i,j}a_i a_j (k(x_i,x_i)+k(x_j,x_j)-2k(x_i,x_j))
= -2\sum_{i,j}a_i a_jk(x_i,x_j)\leq 0,
$$
since $\sum_i a_i =0$ and $k$ is positive definite.

We now provide some background about Hilbert spaces.

To begin with, the following theorem characterizes unit balls in Hilbert spaces, which will be useful
for the analysis of a RKHS constructed in Section~\ref{sec:BergRKHS}.

\begin{thm}[Banach-Alaoglu]\label{th:Alaoglu}
The unit ball in a Hilbert space is weakly compact. In other words,
for any sequence $(v_n)$ such that $\|v_n\|\leq 1$ for all $n\in\N$,
there exists $v\in\mathcal H$ and an increasing $\psi:\N\rightarrow\N$ such that $\|v\|\leq 1$, and $\langle u,v_{\psi(n)}\rangle\rightarrow\langle u,v \rangle$
for any $u\in\mathcal H$.
If, in addition, we have $\|v_{\psi(n)}\|\rightarrow\|v\|$, then the convergence is strong: $\|v_{\psi(n)}-v\|\rightarrow 0$.
\end{thm}

Specifically, we use this result
to show that a certain non-compact set of persistence diagrams would have to be mapped to a compact set by any bi-Lipschitz map to a Hilbert space, which is impossible since bi-Lipschitz maps preserve compactness.
In order to carry out the argument, we use the following results, which allow us to work with an orthonormal basis of a RKHS.

\begin{thm}[Mercer, see Theorem~3.a.1 in~\cite{Konig86}]\label{th:Mercer}
Let $(X,\mu)$ be a finite measure space, and
$k:X\times X\rightarrow\R$ be a bounded kernel in $L_\infty(X\times X,\mu\times\mu)$,
with corresponding RKHS $\mathcal H$.

Then there exists
$\{u_i\}_{i\in\N}\subset L^2(X,\mu)$ s.t.

\begin{equation}\label{eq:Mercer}
k(x,x')=\sum_{i=0}^\infty u_i(x)u_i(x'),

\end{equation}
where the convergence is in $L_\infty(X\times X,\mu \times \mu)$.

\end{thm}

More can be said about the family $\{u_i\}_{i\in\N}$ in case (\ref{eq:Mercer}) converges {\em everywhere} (and not only almost everywhere):

\begin{prop}[Theorem~3.1 in~\cite{Steinwart12}]\label{prop:Stein}
If~(\ref{eq:Mercer}) converges pointwise everywhere, then $\{u_i\}_{i\in\N}$ is an orthonormal basis of $\mathcal H$.
\end{prop}

\end{comment}

\subsection{Bi-Lipschitz embeddings.}
The main question that we adress in this article is the one of preserving the persistence diagram metric properties when using embeddings into Hilbert spaces.
For instance, one may ask the images of persistence diagrams under a feature map into a Hilbert space to be stable as well.
A natural question is then whether a lower bound also holds, i.e.,
whether the feature map $\Phi$ is a {\em bi-Lipschitz embedding} between $(\SpD,d_p)$ and $\HS$.

\begin{defin}
Let $(X,d_X)$ and $(Y,d_Y)$ be two metric spaces. A {\em bi-Lipschitz embedding} between $(X,d_X)$ and $(Y,d_Y)$
is a map $\Phi:X\rightarrow Y$ such that there exist constants $0<A,B<\infty$ such that:
\[ A\,d_X(x,x')\leq d_Y(\Phi(x),\Phi(x'))\leq B\,d_X(x,x'), \]
for any $x,x'\in X$. The metrics $d_X$ and $d_Y$ are called {\em strongly equivalent}, and
the constants $A$ and $B$ are called
the {\em lower} and {\em upper} metric distortion bounds respectively.
If $A=B=1$, $\Phi$ is called an {\em isometric} embedding.
\end{defin}

Note that this definition is equivalent to the commonly used definition that additionally requires $A=\frac1B$.

\begin{rem}
Finding an isometric embedding of persistence diagrams into a Hilbert space
is impossible since geodesics are unique in a Hilbert space while this is not the case for persistence diagrams,
as shown in the proof of Proposition~2.4 in~\cite{Turner14}.
\end{rem}

\begin{rem}
\label{rmk:SW}
For feature maps that are {\em bounded}, i.e., those maps $\Phi$ such that there exists a constant $C>0$
for which $\|\Phi(\Dg)\|\leq C$ for all $\Dg$, it is obviously impossible to find a bi-Lipschitz embedding. This involves for instance the
Sliced Wasserstein (SW) feature map~\cite{Carriere17e}, which is defined implicitly from a Gaussian-like function. However, note that
if the SW feature map is restricted to a set of persistence diagrams which are close to each other with respect to the SW distance,
then the distance in the Hilbert space corresponding to the SW feature map is actually equivalent to the square root of the SW distance. Hence,
we added the square root of the SW distance in our experiment in Section~\ref{sec:expe}.

\end{rem}

\section{Mapping into separable Hilbert spaces}

In our first main result, we use {\em separability} to determine whether a bi-Lipschitz embedding can exist between the space of persistence diagrams and a Hilbert space.

\begin{defin}
A metric space is called {\em separable} if it has a dense countable subset.
\end{defin}

For instance, the following three Hilbert spaces (equipped with their canonical metrics)
are separable: $\R^n$, $\ell_2$ and $L_2(\Omega)$, where $\Omega$ is separable. The two following results
describe well-known properties of separable spaces.

\begin{prop}\label{prop:separsub}
Any subspace of a separable metric space is separable as well.
\end{prop}

\begin{prop}\label{prop:separ}
Let $(X,d_X)$ and $(Y,d_Y)$ be two metric spaces, and assume there is a bi-Lipschitz embedding $\Phi:X\rightarrow Y$,
with Lipschitz constants $A$ and $B$.
Then $X$ is separable if and only if ${\rm im}(\Phi)$ is separable.
\end{prop}

The following lemma shows that for a feature map $\Phi$ which is bi-Lipschitz when restricted to $\SpNLD$,
the limits of the corresponding constants can actually be used to study the general metric distortion in $\SpD$.

\begin{lem}\label{lem:PDs}
Let $p\in\mathbb{N}^*$ and let $d$ be a metric on persistence diagrams such that $d$ is continuous with respect to $d_p$ on $\SpD$.

Let
\begin{align*}
R_N^L&=\left\{\frac{d_p(\Dg,\Dg')}{d(\Dg,\Dg')} : \Dg\neq\Dg'\in\SpNLD\right\}, \\

A_N^L &= \inf\ R_N^L

\quad \text{and} \quad B_N^L = \sup\ R_N^L.
\end{align*}

Since $A_N^L$ is nonincreasing  and $B_N^L$ is nonincreasing with respect to $N$ and $L$, we define:
\begin{align*}
A_N&=

\liminf_{L \to \infty} A_N^L,
\ \ A^L=

\liminf_{N \to \infty} A_N^L,
\ \ A=

\liminf_{N,L \to \infty} A_N^L.\\
B_N&=

\limsup_{L \to \infty} B_N^L,
\ \ B^L=

\limsup_{N \to \infty} B_N^L,
\ \ B=

\limsup_{N,L \to \infty} B_N^L.
\end{align*}
We define $B_N$, $B^L$, $B$ similarly, since $B_N^L$ is nondecreasing with respect to $N$ and $L$.
Then the following inequalities hold:
\begin{align*}
 A^L\, d(\Dg,\Dg') \leq\, & d_p(\Dg,\Dg') \leq B^L\, d(\Dg,\Dg') &\text{ for all }\Dg,\Dg'&\in\SpLD, \\
 A_N\, d(\Dg,\Dg') \leq\, & d_p(\Dg,\Dg') \leq B_N\, d(\Dg,\Dg') &\text{ for all }\Dg,\Dg'&\in\SpND, \\
 A\,   d(\Dg,\Dg') \leq\, & d_p(\Dg,\Dg') \leq B\,   d(\Dg,\Dg') &\text{ for all }\Dg,\Dg'&\in\SpD.
\end{align*}

\end{lem}

Note that $A$, $A_N$, $A^L$, $B$, $B_N$ and $B^L$ may be equal to $0$ or $+\infty$, so it does not necessarily hold that $d$ and $d_p$ are strongly equivalent on $\SpND$, $\SpLD$ or $\SpD$.

\begin{proof}

We only prove the last inequality, since the proof extends verbatim to the other two.
Pick any two persistence diagrams $\Dg,\Dg'\in\SpD$.
Let $\Gamma=\{(p_i,q_i)\}_{i\in\N}$ be an optimal partial matching achieving $d_p(\Dg,\Dg')$,
where $p_i$ (resp. $q_i$) is either in $\Dg$ (resp. $\Dg'$) or in $\pi_\Delta(\Dg')$ (resp. $\pi_\Delta(\Dg)$).

Given $n\in\N$, we define two sequences of persistence diagrams
$\{\Dg_n\}_{n\in\N}$ and $\{\Dg'_n\}_{n\in\N}$ recursively with $\Dg_0=\Dg'_0=\emptyset$ and:
\begin{align*}
\Dg_{n+1}&=\begin{cases} \Dg_n & \text{if }p_{n+1}\in\pi_\Delta(\Dg'), \\
\Dg_n\cup\{p_{n+1}\} &\text{otherwise,}\end{cases}
\\
\Dg'_{n+1}&=\begin{cases} \Dg'_n & \text{if }q_{n+1}\in\pi_\Delta(\Dg), \\
\Dg'_n\cup\{q_{n+1}\} &\text{otherwise.}\end{cases}
\end{align*}

Let us define
\begin{align*}
l_n&=\max\{\max\{\|p\|_\infty:p\in \Dg_n\},\max\{\|q\|_\infty:q\in \Dg'_n\}\}, \\
s_n&=\max\{\card(\Dg_n),\card(\Dg'_n)\},
\end{align*}

Note that both $\{l_n\}_{n\in\N}$ and $\{s_n\}_{n\in\N}$ are nondecreasing. We have $\Dg_n,\Dg'_n\in\mathcal D_{s_n}^{l_n}$ and thus:
\begin{equation}\label{eq:boundnl}

A_{s_n}^{l_n}\,d(\Dg_n,\Dg'_n)\leq d_p(\Dg_n,\Dg'_n)\leq B_{s_n}^{l_n}\,d(\Dg_n,\Dg'_n).
\end{equation}

Assuming $d_p(\Dg_n,\Dg'_n)\rightarrow d_p(\Dg,\Dg')$
\footnote{Note that this is always true if $d_p(\Dg,\Dg')<\infty$.
Even though this is not clear if this assumption also holds in the general case,
it is satisfied for the spaces of persistence diagrams defined in our subsequent results Lemma~\ref{lem:notsepar} and Proposition~\ref{prop:fmap}. },
it follows that $d(\Dg_n,\Dg'_n)\rightarrow d(\Dg,\Dg')$ by continuity of $d$.
We finally obtain the desired inequality

by letting $n\rightarrow+\infty$ in~(\ref{eq:boundnl}).

\end{proof}

A corollary of the previous results is that even if a feature map taking values in a separable Hilbert space might be bi-Lipschitz when restricted to $\SpNLD$,
the corresponding bounds have to go to 0 or $+\infty$ as soon as the domain of the feature map is not separable.

\begin{thm}\label{thm:th1}
Let $\Phi:\mathcal D_{\Phi}\rightarrow \mathcal H$ be a feature map defined on a non-separable subspace $\mathcal D_{\Phi}$ of persistence diagrams
containing every $\SpNLD$, i.e., $\SpNLD\subset\mathcal D_{\Phi}$ for each $N,L$. Assume $\Phi$ takes values in a
separable Hilbert space $\mathcal H$, and that $\Phi$ is bi-Lipschitz on each $\SpNLD$ with constants $A_N^L, B_N^L$.
Then either $A_N^L\rightarrow 0$ or $B_N^L\rightarrow +\infty$ when $N,L\rightarrow+\infty$.
\end{thm}

Many feature maps defined in the literature, such as the Persistence Weighted Gaussian feature map~\cite{Kusano17} or the Landscape feature map~\cite{Bubenik15},
actually take value in the separable function space $L^2(\Omega)$, where $\Omega$ is the upper half-plane $\{(x,y)\,:\,x\leq y\}$.
Hence, to illustrate how Theorem~\ref{thm:th1} applies to these feature maps, we now provide two lemmata. In the first one,
we define a set $\mathcal S$ which is not separable with respect to $d_1$, and in the second one, we show that $\mathcal S$ is actually included in the
domain $\mathcal D_{\Phi}$ of these feature maps.

\begin{lem}\label{lem:notsepar}
Consider the sequence of points $\{p_k=(k, k + \frac 1k)\,:\,k\in\N\}$, and
define the set $\mathcal S = \{\Dg_u\}_{u\in\mathcal U}\subset \SpD$, where $\mathcal U$ is the
set of sequences with values in $\{0,1\}$, with: $\Dg_u=\{p_i\,:\,i\in{\rm supp}(u)\}$.
Then $(\mathcal S, d_1)$ is not separable.

\end{lem}

\begin{proof}
First note that since the sequences $u\in \mathcal U$ can have infinite support, the spaces $\mathcal U$ and $\mathcal S = \{\Dg_u\}_{u\in\mathcal U}$ are not countable.

Let $\sim$ be the equivalence relation on $\mathcal S$ defined with:
\[\Dg_u \sim \Dg_v \Longleftrightarrow {\rm supp}(u)\ \triangle\ {\rm supp}(v) < +\infty,\]
where $\triangle$ denotes the symmetric difference of sets.
Since the set of sequences with finite support is countable, it follows that each equivalence class $[\Dg_u]_{\sim}$ is countable as well.
In particular, this means that the set of equivalence classes $\mathcal S/\sim$ is uncountable, since otherwise $\mathcal S$ would be countable
as a countable union of countable equivalence classes.

We now prove the result by contradiction. Assume that $\mathcal S$ is separable, and let $\mathcal S'\subset\mathcal S$ be the corresponding dense countable subset of $\mathcal S$.
Let $\epsilon > 0$. Then for each $u\in\mathcal U$, there is at least one sequence $u'\in\mathcal U$ such that $\Dg_{u'}\in\mathcal S'$ and
$d_1(\Dg_u,\Dg_{u'})\leq\epsilon$. We now claim that every such $u'$ satisfies $\Dg_{u'}\in[\Dg_u]_{\sim}$.
Indeed, assume $\Dg_{u'}\not\in[\Dg_u]_{\sim}$ and let ${\mathcal I} = {\rm supp}(u')\ \triangle\ {\rm supp}(u)$.
Then, since $|\mathcal I|=+\infty$, we would have \[d_1(\Dg_u,\Dg_{u'})=\sum_{i\in\mathcal I}\frac 1i=+\infty > \epsilon,\] which is not possible.
Hence, this means that $|\mathcal S'| \geq |\mathcal S/\sim|$. However, we showed that $\mathcal S/\sim$ is uncountable, meaning that $\mathcal S'$ is uncountable as well,
which leads to a contradiction since $\mathcal S'$ is countable by assumption.
\end{proof}

We now show that the Persistence Weighted Gaussian and the Landscape feature maps are well-defined on the set $\mathcal S$.
Let us first formally define these feature maps.

\begin{defin}\label{def:landscape}
Given $p =(u,v)\in\R^2$, $u\leq v$, let $\phi_p$ be the triangular function defined with $\phi_p(t)=\frac{v-u}{2}(1-\frac{2}{v-u}|t-\frac{u+v}{2}|)$ if $x\leq t\leq y$ and 0 otherwise.
Then, given a persistence diagram $\Dg$, let $\lambda_k:t\mapsto {\rm kmax}\{\phi_p(t)\}_{p\in\Dg}$, where kmax denotes the $k$-th largest element.
The {\em Landscape} feature map is defined as:
\[
\Phi_{\rm L}:\Dg\mapsto \bar{\lambda},
\quad
\text{where}
\quad
\bar{\lambda}(x,y)=
\begin{cases}
\lambda_{\lceil x \rceil}(y) & x \geq 0,\\
0 & \text{otherwise}.
\end{cases}\]

\end{defin}

\begin{defin}
Let $\omega:\R^2\rightarrow\R$ be a weight function and $\sigma >0$.
The {\em Persistence Weighted Gaussian} feature map is defined as:
\[
\Phi^\omega_{\rm PWG}:\Dg\mapsto \sum_{p\in\Dg} \omega(p){\rm e}^{-\frac{\|\cdot-p\|_2^2}{2\sigma^2}}.
\]

\end{defin}

\begin{prop}\label{prop:fmap}

Let $(x,y)\mapsto (y-x)^2$ be the weight function $(x,y)\mapsto(y-x)^2$.

Let $\mathcal S$ be the set of persistence diagrams defined in Lemma~\ref{lem:notsepar}. Then:
\[
\mathcal S \subset \mathcal D_{\Phi^\omega_{\rm PWG}}\text{ and }\mathcal S \subset \mathcal D_{\Phi_{\rm L}}.
\]
\end{prop}

\begin{proof}
Let $u_k\in\mathcal U$ be the sequence defined with $u_n=1$ if $n\leq k$ and $u_n=0$ otherwise. To show the desired result, it suffices
to show that $\{\Phi^\omega_{\rm PWG}(\Dg_{u_k})\}_{k\in\mathbb N}$ and $\{\Phi_{\rm L}(\Dg_{u_k})\}_{k\in\mathbb N}$ are Cauchy sequences in $L^2(\R^2)$.
Let $q\geq p\geq 1$, and let us study $\|\Phi(\Dg_{u_q})-\Phi(\Dg_{u_p})\|^2_{L^2(\R^2)}$ for each feature map.

\begin{itemize}
\item Case $\Phi^\omega_{\rm PWG}$. We have the following inequalities:

\begin{align*}
\|\Phi^\omega_{\rm PWG}&(\Dg_{u_q})-\Phi^\omega_{\rm PWG}(\Dg_{u_p})\|^2_{L^2(\R^2)}\\
&=\int_{\R^2}\left(\sum_{k=p}^{q}\frac{1}{k^2} {\rm e}^{-\frac{\|x-p_k\|^2_2}{2\sigma^2}}\right)^2{\rm d}x
=\sum_{k=p}^q\sum_{l=p}^q \frac{1}{k^2l^2}\int_{\R^2}{\rm e}^{-\frac{\|x-p_k\|^2_2+\|x-p_l\|^2_2}{2\sigma^2}}{\rm d}x\\
&=\pi\sigma^2\sum_{k=p}^q\sum_{l=p}^q \frac{1}{k^2l^2}{\rm e}^{-\frac{\|p_k-p_l\|^2_2}{4\sigma^2}}\text{ (cf Appendix C in~\cite{Reininghaus14} for a proof of this equality)}\\
&\leq \pi\sigma^2\left(\sum_{k=p}^q \frac{1}{k^2}\right)\left(\sum_{l=p}^q \frac{1}{l^2}\right)
\end{align*}

The result simply follows from the fact that $\{\sum_{k=1}^n\frac{1}{k^2}\}_{n\in\mathbb N}$ is convergent and Cauchy.

\item Case $\Phi_{\rm L}$. Since all triangular functions, as defined in Definition~\ref{def:landscape},
have disjoint support, it follows that
the only non-zero lambda function is
$\lambda_1=\sum_{n=1}^k \phi_n$, where $\phi_n$ is a triangular function defined with
$\phi_n(t)=\frac{1}{2n}(1-|2n(t-(n+\frac{1}{2n}))|)$ if $n\leq t\leq n+\frac 1n$ and 0 otherwise. See Figure~\ref{fig:landscape}.

\begin{figure}[h]\centering
\includegraphics[width=13cm]{landscape.pdf}
\caption{\label{fig:landscape} Image of $\Dg_{u_4}$ under $\Phi_{\rm L}$.}
\end{figure}

Hence, we have the following inequalities:

\begin{align*}
\|\Phi_{\rm L}&(\Dg_{u_q})-\Phi_{\rm L}(\Dg_{u_p})\|^2_{L^2(\R^2)}\\
&=\int_{\R}\left(\sum_{k=p}^{q}\phi_k(x)\right)^2{\rm d}x
=\sum_{k=p}^q\sum_{l=p}^q \int_{\R}\phi_k(x)\phi_l(x){\rm d}x\\
&=\sum_{k=p}^q\int_{\R}\phi_k(x)^2{\rm d}x
\leq\sum_{k=p}^q\int_{\R}\phi_k(x){\rm d}x
=\sum_{k=p}^q\frac{1}{4k^2}
\end{align*}
Again, the result follows from the fact that $\{\sum_{k=1}^n\frac{1}{k^2}\}_{n\in\mathbb N}$ is convergent and Cauchy.
\qedhere
\end{itemize}
\end{proof}

Proposition~\ref{prop:fmap} shows that Theorem~\ref{thm:th1} applies (with the metric $d_1$ between persistence diagrams)
to the Persistence Weighted Gaussian feature map with weight function $(x,y)\mapsto (y-x)^2$---actually, any
weight function that is equivalent to $(y-x)^2$ when $(x,y)$ goes to 0---and the Landscape feature map. In particular,
any lower bound for these maps has to go to 0 when $N,L\rightarrow+\infty$ since an upper bound exists for these maps due to their stability properties---see
Corollary 15 in~\cite{Bubenik15} and Proposition 3.4 in~\cite{Kusano17}.

\begin{comment}
\section{Metric Distortion Bounds}

In this section, we prove our main results -- Theorem~\ref{th:NonEqCnsd} and Theorem~\ref{th:nonembedRn} -- about the embeddings of persistence diagrams into RKHS. Even if these results extend freely to embeddings into general Hilbert spaces, we state them in the framework of RKHS since it is the main application of persistence diagram embeddings in Machine Learning.

\subsection{Infinite dimensional RKHS}
\label{sec:BergRKHS}

In order to show our first main result Theorem~\ref{th:NonEqCnsd}, we first provide the following lemma,
which relates the metric distortion bounds computed on $\SpNLD$, $\SpLD$, $\SpND$ and $\SpD$.

\begin{lem}\label{lem:persistence diagrams}
Let $p\in\N$ and let $d$ be a metric on persistence diagrams such that $d$ is continuous w.r.t.\@ $d_p$ on $\SpD$.

Let $R_N^L=\left\{d_p(\Dg,\Dg')/d(\Dg,\Dg')\,:\,\Dg\neq\Dg'\in\SpNLD\right\}$,
let $A_N^L = {\rm inf}\ R_N^L$

and $B_N^L = {\rm sup}\ R_N^L$.

Since $A_N^L$ is nonincreasing and $B_N^L$ is nondecreasing w.r.t.\@ $N$ and $L$, we define:
$$
A_N=\limitinf{L} A_N^L,\ \
B_N=\limitinf{L} B_N^L,\ \
A^L=\limitinf{N} A_N^L,\ \
B^L=\limitinf{N} B_N^L
$$

Then the following inequalities hold:
$$
 A^L\, d(\Dg,\Dg') \leq\, d_p(\Dg,\Dg') \leq B^L\, d(\Dg,\Dg'),\ \ \ \text{and}\ \ \  A_N\, d(\Dg,\Dg') \leq\, d_p(\Dg,\Dg') \leq B_N\, d(\Dg,\Dg')
$$
where $\Dg,\Dg'$ belong to $\SpLD$, $\SpND$ and $\SpD$ respectively.

Note that
$A_N$, $A^L$,
$B_N$ and $B^L$ may be equal to $0$ or $\infty$,
so these inequalities do not necessarily mean  that $d$ and $d_p$ are strongly equivalent on $\SpND$, $\SpLD$ or $\SpD$.
\end{lem}

We now show our first main result, which states that,

given a kernel $k$ for persistence diagrams,

if the induced distance $d_k$ in its corresponding RKHS
is strongly equivalent to a diagram distance on $\SpNLD$,
then at least one of the two metric distortion bounds depends on the persistence diagrams,
and goes to either $0$ or $\infty$ as $N$ or $L$ increases.

\begin{thm}\label{th:NonEqCnsd}
Let $p\in\N\cup\{\infty\}$ and $d_p$ be the corresponding diagram distance.
Let $k$ be a continuous kernel on persistence diagrams, and let $d_k$ be the corresponding RKHS distance.

Assume that for any $N\in\N$ and $L>0$, there exist $0<A_N^L,B_N^L<\infty$
such that, for any $\Dg,\Dg'\in\SpNLD$:

$$A_N^L\,d_k(\Dg,\Dg')\leq d_p(\Dg,\Dg')\leq B_N^L\,d_k(\Dg,\Dg').$$

Then $\frac{B_N^L}{A_N^L} \rightarrow \infty$ when $L$ is fixed and $N\rightarrow\infty$, or when $N$ is fixed and $L\rightarrow \infty$.
\end{thm}

\begin{proof}

We first prove the result when $N\rightarrow\infty$, and we fix some $L>0$.
According to Lemma~\ref{lem:persistence diagrams}, all we have to show is that $d_k$ and $d_p$ are not strongly equivalent on $\SpLD$.

We proceed by contradiction and assume that they are. In particular, this means that any space which is compact with one metric should also be compact with the other.
Hence, the idea of the proof is to reach a contradiction
by  constructing  a space $X\subset \SpLD$ which is provably compact with $d_k$ but not with $d_p$.

Let us define this space $X$ as follows:
$X=\{\Dg_n\}_{n\in\N}$, where $\Dg_n=\sqcup_{i=1}^n\{q\}$
and $q=(-L,L)\in\R^2$. Hence, $X$ is a discrete metric space for which the distance $d_p$ between any two elements is larger than $L$.
Indeed, this distance is obtained by matching $|j-i|$ replicates of $q$ to the diagonal, so $d_p(\Dg_i,\Dg_j)=L|j-i|^{\frac 1p}\geq L$ and $d_\infty(\Dg_i,\Dg_j) = L$ for all $i \neq j$.
As such, $X$ is complete and not compact when equipped with $d_p$.

We will prove that $X$ is compact w.r.t.\@ $d_k$, contradicting the assumption that $d_k$ and $d_p$ are equivalent. The idea is
to define a Gaussian kernel $G$ on $X$ with Theorem~\ref{th:Berg}, using the fact that $d_k^2$ is conditionally negative definite. Since the image of the feature map of $G$  is in the unit sphere of its RKHS,
we can then use Theorem~\ref{th:Alaoglu} to show that this image is weakly compact with the RKHS distance, which
can then be used to show that $X$ is compact with  $d_k$.

More formally, define $G(\cdot,\cdot)=\exp\left(-d_k^2(\cdot,\cdot)\right)$. Then
$G$ is another kernel on $ X\times X$, with corresponding RKHS $\HS$.
Moreover, $G$ is bounded on $X$ since $G(\cdot,\cdot)\leq 1$.
Hence, according to Theorem~\ref{th:Mercer}, there exists a family $\{u_i\}_{i\in\N}$ such that
$G(\cdot,\cdot)=\sum_{i=0}^\infty u_i(\cdot)u_i(\cdot)$, where the convergence is in $L_\infty(X\times X,\mu\times\mu)$.
We now  equip $X$ with a positive measure $\mu$, defined on each singleton with $\mu(\{\Dg_n\})=\exp(-n)$.

In particular, we have $\mu(X)=\sum_{i=1}^{\infty}\exp(-i)<\infty$.
Moreover, since $\mu(\{\Dg_n\})$ is positive for all $n\in\N$, there is no non empty $S\subseteq X$ with $\mu(S)=0$, and thus
$L_\infty(X\times X,\mu\times\mu)$ convergence means uniform and pointwise convergence on $X\times X$.
Hence, $\{u_i\}_{i\in\N}$ is also an orthonormal basis of $\HS$ by Proposition~\ref{prop:Stein}.

We now show that $X$ is compact w.r.t.\@ $d_k$.
Let $\Phi:X\rightarrow\HS$ be the feature map induced by $G$.
Then $\Phi(X)$ is included in the unit sphere of $\HS$ since
$\|\Phi(\Dg_n)\|^2_{\HS}=G(\Dg_n,\Dg_n)=1$.
According to Theorem~\ref{th:Alaoglu}, there exists an increasing $\psi:\N\rightarrow\N$ such that
the sequence $\Phi(\Dg_{\psi(n)})$ weakly converges to some $v\in\HS$ with $\|v\|_{\HS}\leq 1$.
We have the following equalities:

\begin{align*}
& 1 = \limitinf{n} \|\Phi(\Dg_{\psi(n)})\|^2_{\HS} = \limitinf{n}\sum_{i=0}^{\infty} u_i(\Dg_{\psi(n)})^2 \\
& = \sum_{i=0}^{\infty} \limitinf{n} u_i(\Dg_{\psi(n)})^2 \tag*{(uniform convergence)}\\
& = \sum_{i=0}^{\infty} \limitinf{n} \langle u_i,\Phi(\Dg_{\psi(n)})\rangle_{\HS}^2 \tag*{\text{(reproducing property)}} \\
& = \sum_{i=0}^{\infty} \langle u_i,v\rangle_{\HS}^2 &\tag*{(weak convergence of $\Phi(\Dg_{\psi(n)})$)} \\

& = \|v\|^2_{\HS} &\tag*{($\{u_i\}_{i\in\N}$ is an orthonormal basis)}
\end{align*}

Finally, since $\Phi(\Dg_{\psi(n)})$ weakly converges to $v$ and $\|\Phi(\Dg_{\psi(n)})\|_{\HS}$
converges to $\|v\|_{\HS}$, it follows that $\Phi(\Dg_{\psi(n)})$ strongly converges to $v$ by
Theorem~\ref{th:Alaoglu}, and thus is Cauchy w.r.t.\@ $\|\cdot\|_{\HS}$.
Since $X$ is complete w.r.t.\@ $d_p$, and since $d_k$ is strongly equivalent to $d_p$ by assumption,
it follows that $X$ is also complete w.r.t.\@ $d_k$. This means that $\Phi(X)$ is complete w.r.t.\@ $\|\cdot\|_{\HS}$ by the following equalities:

$$
\|\Phi(\Dg_n)-\Phi(\Dg_m)\|^2_{\HS}
=k(\Dg_n,\Dg_n)+k(\Dg_m,\Dg_m)-2k(\Dg_n,\Dg_m)
=2\left(1-\exp\left(-d^2_k(\Dg_n,\Dg_m)\right)\right).
$$

Hence there exists $\Dg\in X$ such that $v=\Phi(\Dg)$ and $\Dg_{\psi(n)}$
converges to $\Dg$ w.r.t.\@ $d_k$ and $d_p$. In particular, this means that $X$
is compact w.r.t.\@ $d_k$.

\paragraph{} Since the same proof applies when $X$ is replaced by $Y=\{\Dg'_n\}_{n\in\N}$ where
$\Dg'_n=\{(0,n)\}$, it follows that $d_k$ and $d_p$ are also not strongly equivalent on $\SpND$,

and thus that the result also holds when $L\rightarrow \infty$.

\end{proof}
\end{comment}

\section{Mapping into finite-dimensional Hilbert spaces}

In our second main result, we show that more can be said about feature maps into $\R^n$ (equipped with the Euclidean metric),
using the so-called {\em Assouad dimension}. This involves all vectorization methods for persistence diagrams that we described in the related work.

\paragraph*{Assouad dimension.}
The following definition and example are taken from paragraph 10.13 of~\cite{Heinonen01}.

\begin{defin}
Let $(X,d_X)$ be a metric space. Given a subset $E\subset X$ and $r>0$, let $N_r(E)$ be the least number of open balls
of radius less than or equal to $r$ that can cover $E$.
The {\em Assouad dimension} of $X$ is:
$$
\dimA(X,d_X)={\rm inf}\{\alpha>0\,:\,\exists C >0\text{  s.t. }
{\rm sup}_{x\in X}N_{\beta r}(B(x,r))\leq C\beta^{-\alpha},\ \forall r>0,\beta\in(0,1]\}.
$$

\end{defin}
Intuitively, the Assouad dimension measures the number of open balls needed to cover an open ball of larger radius.
For example, the Assouad dimension of $\R^n$ is $n$. Moreover, the Assouad dimension is preserved by bi-Lipschitz embeddings.

\begin{prop}[Lemma 9.6 in~\cite{Robinson10}]\label{prop:Assouadineq}
Let $(X,d_X)$ and $(Y,d_Y)$ be metric spaces with a bi-Lipschitz embedding $\Phi:X\rightarrow Y$.
Then $\dimA(X,d_X) = \dimA({\rm im}(\Phi),d_Y)$.

\end{prop}

\paragraph*{Non-embeddability.}
We now show that $\SpNLD$ cannot be embedded into $\R^n$ with bi-Lipschitz embeddings.
The proof of this fact is a consequence of the following lemma:

\begin{lem}\label{lem:Assouadpersistence diagrams}
Let $p\in\N\cup\{\infty\}$, $N\in\N$, and $L>0$.
Then

$\dimA(\SpNLD,d_p)=+\infty$.
\end{lem}

\begin{proof}
Let $B_p$
denote an open ball with $d_p$.
We want to show that, for any $\alpha>0$ and $C>0$, it is possible to find a persistence diagram $\Dg\in\SpNLD$, a radius $r>0$ and
a factor $\beta\in(0,1]$ such that the number of open balls of radius at most $\beta r$ needed to cover $B_p(\Dg,r)$

is strictly larger than $C\beta^{-\alpha}$.
To this end, we pick arbitrary $\alpha>0$ and $C>0$.
The idea of the proof is to define
$\Dg$ as the empty diagram, and to derive a lower bound on the number of balls with radius $\beta r$ needed to cover $B_p(\Dg,r)$
by considering persistence diagrams with one point evenly distributed on the line $\{(x,x+r):x\in[-L,L]\}$
such that the distance between two consecutive points is $r$ in the $\ell_\infty$-distance. Indeed, the pairwise distance between any two such persistence diagrams is
sufficiently large so that they must belong to different balls.
Then we can control the number of persistence diagrams, and thus the number of balls,
by taking $r$ sufficiently small.

More formally, let $M=1+\lfloor C\beta^{-\alpha}\rfloor> C\beta^{-\alpha}$.
We want to show that we have at least $M$ balls in the cover, meaning that $|\{\Dg_i\}|\geq M$.
Let $r=2L/M$ and $\beta=\frac 12$. We define a cover of $B_p(\Dg,r)$ with open balls of radius less than $\beta r$
centered on a family $\{\Dg_i\}$ as follows:

\begin{equation}\label{eq:cover}
B_p(\Dg,r)\subseteq \bigcup_{i} B_p(\Dg_i,\beta r).
\end{equation}

We now define particular persistence diagrams which all lie in different elements of the cover~(\ref{eq:cover}).
For any $0\leq j \leq M-1$,

we let $\Dg'_j$ denote the persistence diagram containing only the point $(-L+jr,-L+(j+1)r)$. It is clear that each $\Dg'_j$ is in $\SpNLD$.
See Figure~\ref{fig:proofAssouad}.

\begin{figure}
\centering
\includegraphics[width=5cm]{proofAssouad}
\caption{\label{fig:proofAssouad} Persistence diagram used in the proof of Lemma~\ref{lem:Assouadpersistence diagrams}. In this particular example, we have $M=5$.}
\end{figure}

Moreover, since
$d_p(\Dg,\Dg'_j)= \frac r2<r$, it also follows that $\Dg'_j\in B_p(\Dg,r)$.

Hence, according to~(\ref{eq:cover}), for each $j$ there exists an integer $i_j$  such that $\Dg'_j\in B_p(\Dg_{i_j},\beta r)$.
Finally, note that $j\neq j'\Rightarrow i_j\neq i_{j'}$. Indeed, assuming that there are $j\neq j'$ such that
$i_j=i_{j'}$, and since the distance between $\Dg'_j$ and $\Dg'_{j'}$ is always obtained by matching their points to the diagonal,
we reach a contradiction with the following application of the triangle inequality:
$$
d_p(\Dg'_j,\Dg'_{j'})=2^{\frac 1p}\frac  r2
\leq d_p(\Dg'_j,\Dg_{i_j})+d_p(\Dg_{i_j},\Dg_{i_{j'}})+d_p(\Dg_{i_{j'}},\Dg'_{j'})
<2\beta r =r.
$$
This observation shows that there are at least $M$

different open balls in the cover~(\ref{eq:cover}), which concludes the proof.

\end{proof}

The following theorem is then a simple consequence of Lemma~\ref{lem:Assouadpersistence diagrams}  and Proposition~\ref{prop:Assouadineq}:

\begin{thm}\label{th:nonembedRn}
Let $p\in\N\cup\{\infty\}$ and $n\in\N$.
Then, for any $N\in\N$ and $L>0$, there is no bi-Lipschitz embedding between
$(\SpNLD,d_p)$ and $\R^n$.
\end{thm}

Interestingly, the integers $N$ and $n$ are independent in Theorem~\ref{th:nonembedRn}: even if one restricts to persistence diagrams
with only one point, it is still impossible to find a bi-Lipschitz embedding into $\R^n$, whatever $n$ is.

\section{Experiments}
\label{sec:expe}

In this section, we illustrate our main results by computing the lower metric distortion bounds for the main stable feature maps in the literature. We use
persistence diagrams with increasing number of points to experimentally observe the convergence of this bound to 0, as described in Theorem~\ref{thm:th1}.
More precisely, we generate 100 persistence diagrams for each cardinality in a range going from 10 to 1000 by uniformly sampling points in the unit
upper half-square $\{(x,y)\,:\,0\leq x,y \leq 1, x\leq y\}$. See Figure~\ref{fig:exPDs} for an illustration.

\begin{figure}[h]\centering
\includegraphics[width=5cm]{expe/12-PD.pdf}

\includegraphics[width=5cm]{expe/62-PD.pdf}
\includegraphics[width=5cm]{expe/102-PD.pdf}
\caption{\label{fig:exPDs} Example of synthetic persistence diagrams with cardinalities 10 (left), 60 (middle), and 100 (right) generated for the experiment.}
\end{figure}

Then, we consider the following feature maps:

\begin{itemize}
\item the Persistence Weighted Gaussian with unit bandwidth (PWG)~\cite{Kusano17},
\item the Persistence Scale Space with unit bandwidth (PSS)~\cite{Reininghaus15},
\item the Landscape (LS)~\cite{Bubenik15},
\item the Persistence Image with resolution $10 \times 10$ and unit bandwidth (IM)~\cite{Adams17}
\item the Topological Vector with 10 dimensions (TV)~\cite{Carriere15a},
\end{itemize}

Since most of these feature maps enjoy stability properties with respect to the first diagram distance $d_1$, we compute
the ratios between the metrics in the Hilbert spaces corresponding to these feature maps and $d_1$.
Moreover, we also look at the ratio induced by the square root of the Sliced Wasserstein distance (SW)~\cite{Carriere17e}, as suggested by Remark~\ref{rmk:SW}.
All feature maps were computed with the sklearn-tda library\footnote{\url{https://github.com/MathieuCarriere/sklearn_tda}},
which uses Hera\footnote{\url{https://bitbucket.org/grey_narn/hera}}~\cite{Kerber17} as backend
to compute the first diagram distances $d_1$ between pairs of persistence diagrams.
These ratios are then displayed as boxplots in Figure~\ref{fig:boxplots}.

\begin{figure}[h!]\centering
\includegraphics[width=6.75cm]{expe/PW.pdf}
\includegraphics[width=6.75cm]{expe/PS.pdf}
\includegraphics[width=6.75cm]{expe/SW.pdf}
\includegraphics[width=6.75cm]{expe/LS.pdf}
\includegraphics[width=6.75cm]{expe/IM.pdf}
\includegraphics[width=6.75cm]{expe/TV.pdf}
\caption{\label{fig:boxplots} Boxplots of the ratios between distances induced by various feature maps and the first diagram distance $d_1$.}
\end{figure}

It is clear from Figure~\ref{fig:boxplots} that the extreme values of these ratios (the upper tail of the ratio distributions) increase with the
cardinality of the persistence diagrams, as expected from Theorem~\ref{thm:th1}. This is especially interesting in the case of the Sliced
Wasserstein distance since the question whether the lower bound that was proved in~\cite{Carriere17e}, which increases with the number of points
in the diagrams, was tight or not, i.e., if a lower bound which is oblivious to the number of points could be derived, is still open.
Hence, it seems from Figure~\ref{fig:boxplots} that this is not the case empirically.
It is also interesting to notice that  the divergence speed of these ratios differ from a feature map to another. More precisely, it seems like the metric distortion bounds increase linearly
with the cardinalities for the TV and LS feature maps and the Sliced Wasserstein distance, while it is increasing at a much lower speed for the other feature maps.

\section{Conclusion}

In this article, we provided two important theoretical results about the embedding of persistence diagrams in separable Hilbert spaces, which
is a common technique in TDA to feed machine learning algorithms with persistence diagrams. Indeed, most of the recent attempts
have defined  feature maps for persistence diagrams into Hilbert spaces and showed these maps were stable with respect to the first diagram distance,
and conjectured whether a lower bound holds as well or not.
In this work, we proved that this is never the case if the Hilbert space is finite dimensional, and that such a lower bound has to go to zero with
the number of points for most other feature maps in the literature. We also provided experiments that confirm this result, by showing a clear
increase of the metric distortion with the number of points for persistence diagrams generated uniformly in the unit upper half-square.

\bibliography{biblio}
\bibliographystyle{alpha}

\end{document}


TITLE: Formula for Alternating Geometric Series
QUESTION [5 upvotes]: I am aware of the following formula:
$$\sum_{n=0}^{\infty}(-1)^nr^n=\frac{1}{1+r}$$
However, I am having difficulty understanding if there is a simple formula for the following equation:
$$\sum_{n=0}^{\infty}(-1)^nr^{2n}={ }?$$
In addition, what about the following?
$$\sum_{n=0}^{\infty}(-1)^{n+1}r^{2n+1}={ }?$$
I'm not sure how to go about identifying how to modify the original formula to fit the previous two, if that is even possible. Any help would be greatly appreciated.

REPLY [9 votes]: $$\sum_{n=0}^{\infty}(-1)^nr^n=\sum_{n=0}^{\infty}(-r)^n=\cfrac{1}{1-(-r)}=\cfrac{1}{1+r}$$
So you can do the same for two following series :
$$\sum_{n=0}^{\infty}(-1)^nr^{2n}=\sum_{n=0}^{\infty} {(-r^2)}^n $$$$\sum_{n=0}^{\infty}(-1)^{n+1}r^{2n+1}=-r\sum_{n=0}^{\infty}(-1)^nr^{2n}$$


TITLE: Fragment of ZFC to prove first-order completeness theorem
QUESTION [4 upvotes]: If I am not mistaken PRA or an even weaker theory suffices to develop the syntactics of first-order logic (at least for finite or countable languages).
To develop the semantics of first-order logic sets are assumed. I am wondering what fragment of ZFC is necessary to (1) develop the semantics of first-order logic, (2) prove the completeness theorem of first-order logic.

REPLY [3 votes]: Very little.
First of all, an important fragment of the completeness theorem doesn't even need "big" sets at all. Consider the "countable completeness theorem":

$(*)$ If $T$ is a consistent theory in a countable language, then $T$ has a countable model.

This can be appropriately expressed in the language of second-order$^*$ arithmetic, and in fact is quite weak: over the base theory RCA$_0$, which corresponds roughly to "computable mathematics," the principle $(*)$ is equivalent to weak Konig's lemma (wkl) - the statement that every infinite binary tree has an infinite path. One direction - proving $(*)$ from RCA$_0$ + wkl (this latter system is called "WKL$_0$" - note that "WKL" denotes a stronger theory, hence my usage of "wkl" above) because over RCA$_0$ the principle wkl lets us prove (the appropriate form of) Lindenbaum's lemma, and modulo that the usual Henkinization proof is entirely effective.

Now what about the more general completeness theorem?
Well,there's an interesting split: we have on the one hand the "well-ordered completeness theorem"

$(**)$ If $T$ is a consistent theory in a well-orderable language, then $T$ has a well-orderable model,

and the "full" completeness theorem

$(***)$ If $T$ is a consistent theory, then $T$ has a model.

The principle $(***)$ is not provable in ZF - it requires a small amount of choice (see here). The former principle, however, is provable in ZF; looking at the usual Henkinization argument, we see that it consists of:

Pass from $T$ to a complete consistent theory $\hat{T}$ (Lindenbaum's lemma).
Pass from $\hat{T}$ to a larger complete consistent theory $T^+$ in an expanded language, with the witness property (Henkinization).
Argue that the term model of $T^+$ is in fact a model of $T^+$, and hence its reduct to our original language is a model of $T$.

It's not hard to check that this goes through in the theory KP + Inf (the axiom of infinity needed to form sets of finite sequences). This is not optimal, but it's a good first approximation. Meanwhile, by the same reasoning KP + Inf + the well-ordering theorem proves $(***)$.
Incidentally, the development of logic inside KP + Inf and related weak fragments of ZFC has been intensely studied - Barwise has an excellent book which treats these issues (among others). Of particular interest I think is the relationship between weak fragments of ZFC and logics beyond first-order logic, specifically (fragments of) infinitary logic $\mathcal{L}_{\infty\omega}$ - see for example the Barwise compactness theorem.

A minor obnoxiousness: although it's called "second-order arithmetic," everything here is first-order in the sense of the underlying logic. In my opinion, "second-order arithmetic" should really be called "two-sorted arithmetic" (I'd also be happier with "analysis," which has been used this way historically, but not quite as happy since that has connotations of its own) but unfortunately the name has stuck.


TITLE: Nonstandard models of PA with a decidable order relation.
QUESTION [5 upvotes]: There this exercise in Models of Peano Arithmetic (Kaye 1991, p.157), which asks to define a recursive binary relation on $\mathbb{N}^2$, such that $M \upharpoonright < $ is isomorphic to $(\mathbb{N}, \prec)$, where $\prec$ is the relation defined earlier, and $M \vDash PA$ is countable and nonstandard (which means that $+^M$ and $\cdot^M$ are not recursive for Tennenbaum's theorem). Now, I can't understand how I should define this relation. The standard relation obviously doesn't work, because there would be no isomorphism, but I can't find a suitable one.

REPLY [5 votes]: Let $M$ be a countable non-standard model. From an order-theoretic point of view, the model consists of a copy of the natural numbers, followed by an ordered set which is isomorphic to $I\times \mathbb{Z}$. Here $I$ is a densely ordered set with no first or last element, $\mathbb{Z}$ has the natural order, and $I\times Z$ is ordered lexicographically.
But all countable densely ordered sets with no first or last element are order-isomorphic to the rationals.
Added: We give more detail on existence of a recursive ordering. For any natural number $n$ (we are including $0$), let the type of $n$ be the kargest $k$ such that $2^k$ divides $n$. We map the type $0$ numbers bijectively to $\mathbb{N}$, the type $1$ numbers bijectively to a copy of $\mathbb{Z}$, the rype $2$ objects bijectively to a copy of $\mathbb{Z}$, and so on.
It remains to define the order. List the rationals in the interval $(0,1)$ as $r_1,r_2, r_2,\dots$. The set non-zero types (previous paragraph) can be bijectively identified with the rationals. Now on the types, define the order inherited from the rationals.


TITLE: first order logic sentence
QUESTION [1 upvotes]: I'm trying to show that the sentence
$$\forall_x \exists_y P(x,y) \land \forall_x \forall_y (P(x,y) \implies \neg P(y,x)) \land \forall_x \forall_y \forall_z (P(x,y) \implies (P(y,z)\implies P(x,z))$$ (where $P$ is binary predicate) is false in finite structures and true in some infinite structure.
For the second task I took structure $<\mathbb{Z}, < >$ and it seems to work. But i have no idea how to do the first part of the exercise.

REPLY [1 votes]: What it says is that we have an "strict order" (last part says transitive, second says antisymmetric) on the set where every element has a larger element (which is strictly larger as $P(x,x)$ can never hold, due to part 2 of the statement).
So if $F$ is a finite (non-empty) model, take $f_0 \in F$, and by recursion we find $f_n$ with $P(f_n, f_{n+1})$ for all $n \ge 0$. By finiteness some $f_n = f_m$ for $n \neq m$. Find a contradiction with transitivity.

REPLY [1 votes]: Your sentence is basically made up of three statements.
The proof should go something like:

Start with some $x_0$ in your finite structure
Because of the first statement, there exists some $x_1$ such that $P(x_0, x_1)$. And some $x_2$ such that $P(x_1,x_2)$. This way, you can define $x_n$ for each $n\in\mathbb N$.
Obviously, since the structure is finite, there exists some repetition. Take the first $k$ for which $x_k$ appears twice in the sequence $(x_0,x_1,\dots)$, i.e. $x_k=x_{k+m}$ for some $m$
Now, you have a chain $x_k, x_{k+1},\dots x_{k+m}$.
Because of the second statement, you know that $P(x_{k+m-1}, x_{k+m})$.
Because of the third statement, you know that (proove it by induction) $P(x_k, x_{k+m-1})$.


TITLE: Confusion in Discrete Fourier Transform derivation
QUESTION [0 upvotes]: In the book "Digital Image Processing" by R. Gonzalez, section 4.4.1 "Obtaining the OFT from the Continuous Transform of a Sampled Function",
they get $$\tilde{F}(\mu)=\sum^{\infty}_{n=-\infty}f_ne^{-j2\pi\mu n\Delta T}$$
where $f_n$ are the sampled points from a continuous function $f$ and $\tilde{F}$ is the fourier transform of the sampled function.
Now, the book says:
"Suppose that we want to obtain $M$ equally spaced samples of $\tilde{F}(\mu)$ taken
over the period $\mu= 0$ to $\mu=\frac1{\Delta T}$. This is accomplished by taking the samples at the following frequencies:
$$\mu=\frac{m}{M\Delta T} \text{     ,                   } m=0,1,2,...,M-1$$
Substituting this result for $\mu$ into <first equation> and letting $F_m$ denote the result yields" $$F_m=\sum^{M-1}_{n=0}f_ne^{-j2\pi \frac{mn}M}\text{   ,   } m=0,1,2,...,M-1$$
Now what I don't understand is that when we are obtaining samples of $\tilde{F}$, then all we have to do is get values of the function at the given points. So how did doing just that, change the limits of the summation? According to me, $$F_m=\sum^{\infty}_{n=-\infty}f_ne^{-j2\pi \frac{mn}M}\text{   ,   } m=0,1,2,...,M-1$$ this should be the correct expression. So where did I go wrong? Please explain.

REPLY [0 votes]: Perhaps you and the author are confusing the term given samples. I think the author means that $M$ values of $f_n$ are given. In this case the finite sum is correct. However you suppose that $M$ values of $F_m$ are given. Here the infinit sum is correct. Note that in both cases the result is not identical.


TITLE: Approximating polynomials over $\mathbb{C}$ with an entire function
QUESTION [4 upvotes]: Given a series of polynomials $p_{n}$ and a series of non-intersecting balls $B_{n} \subset \mathbb{C}$ show that there exists some function $f \in \mathcal{O}(\mathbb{C})$ such that $lim_{n \rightarrow \infty} sup_{z \in B_{n}} |f(z)-p_{n}(z)|=0$.
Normally approximation is the other way around, so I'm having a little trouble with this.

REPLY [2 votes]: The claimed result is false:
Let $B_n$ be an open disk with center $\frac 1n$ and of radius $r_n$ sufficiently small to ensure that the disks do not contain $0$ and are disjoint, and define $p_n(z)=n$, the  constant polynomial with valiue $n$.
If $f\in \mathcal O(\mathbb C)$ existed  we would have on one hand $f(0)=\lim_{n \rightarrow \infty}f(\frac 1n)$.
On the other hand we would have $lim_{n \rightarrow \infty} \vert f(\frac 1n) -n)\vert =0$ [because of  the hypothesis $lim_{n \rightarrow \infty} sup_{z \in B_{n}} |f(z)-p_{n}(z)|=lim_{n \rightarrow \infty} sup_{z \in B_{n}} |f(z)-n|=0$] and thus in particular $lim_{n \rightarrow \infty} \vert f(\frac 1n) )\vert=\infty$.
Since the two hands cannot agree , the function $f$ does not exist !


text:
\chapter{Steady-state in an arbitrary root system}\label{general_steady}

The objective of this chapter is to derive one of the main results of this work, which is the convergence of Dunkl processes in finite time to a steady state. For this purpose, the precise definition of the steady state of Dunkl processes is given as the steady state of their corresponding \emph{time-scaled} processes. Next, the precise statement of the result is given in Theorem~\ref{TheoremSteadyState}, and the proof of the theorem is given in the final two sections.

\section{Definition of the steady state}

Dunkl processes in general, and interacting Brownian motions and Bessel processes in particular, are diffusion processes without restoring forces. This means that their evolution is such that their probability density spreads out in space without stopping. Consequently, these processes do not have a steady state in the strict sense. However, as mentioned in the previous chapter, if the distribution function of the Dunkl process is scaled suitably, then it has a limit form (in time) given by Eq.~\eqref{SteadyStateDistributionPreliminary}, and the underlying scaled process has a steady state.

The concrete form of these statements is as follows. The SDE of a radial Dunkl process is given by \cite{demni09A}
\begin{equation}\label{RadialDunklSDE}
\ud \bX_t=\ud \bB_t+\frac{\beta}{2}\sum_{\balpha\in R_+}\frac{\kappa(\balpha)\balpha}{\balpha\cdot\bX_t}\ud t.
\end{equation}
This is a semi-martingale in $N$ dimensions with a drift term that forces the process away from the origin in the directions $\balpha\in R$. Clearly, this process does not achieve a steady state, as it diffuses without bounds. Its corresponding time-scaled process is defined by $\bY_t=\bX_t/\sqrt{\beta t}$. Using It{\^o}'s formula \cite{protter05}, the SDE for $\bY_t$ is
\begin{equation}
\ud \bY_t=\frac{\ud \bB_t}{\sqrt{\beta t}}+\frac{1}{2t}\sum_{\balpha\in R_+}\frac{\kappa(\balpha)\balpha}{\balpha\cdot\bY_t}\ud t-\frac{\bY_t}{2t}\ud t.
\end{equation}
The last term is a restoring force term, which restrains the diffusion of the process. If, furthermore, the time variable is redefined as $\tau=(\log t)/\beta$, then $\ud t=\beta t\ud \tau$ and
\begin{equation}
\ud \bY_\tau=\ud \bB_\tau+\frac{\beta}{2}\Big[\sum_{\balpha\in R_+}\frac{\kappa(\balpha)\balpha}{\balpha\cdot\bY_\tau}-\bY_\tau\Big]\ud \tau.
\end{equation}
This is a process with a harmonic restoring force, which is very similar to an Ornstein-Uhlenbeck processes. It is known that these generalized Ornstein-Uhlenbeck processes are stationary \cite[Sec.~10]{roslervoit98}, so it is clear that a properly scaled radial Dunkl process achieves a steady state. Furthermore, because the jumps of non-radial Dunkl processes preserve the distance of the process to the origin just before and after the jump (because $\sigma_{\balpha}$ is an isometry), then non-radial Dunkl processes scaled by a factor $\sqrt{\beta t}$ are stationary as well.

From the point of view of the process distribution $f(t,\by)$, the procedure is as follows. According to Eq.~\eqref{SteadyStateDistributionPreliminary}, if the probability distribution $f(t,\by)$ of a Dunkl process is scaled as
\begin{equation}
f_t(\bv):=f(t,\sqrt{\beta t}\bv)(\beta t)^{N/2},
\end{equation}
then the steady-state distribution is proportional to
\begin{equation}
f_{\text{ss}}(\bv):=\exp\Big[-\beta\Big(\frac{v^2}{2}-\sum_{\balpha\in R_+}\kappa(\balpha)\log |\balpha\cdot\bv|\Big)\Big].
\end{equation}
Let us verify this claim. Because the Dunkl process density $f(t,\by)$ obeys the FKE \eqref{DunklForward}, then the scaled distribution obeys the following FKE:
\begin{multline}\label{ScaledDunklFKE}
2t\frac{\partial}{\partial t}f_t(\bv)=\frac{1}{\beta}\Delta f_t(\bv)-\sum_{\balpha\in R_+}\kappa(\balpha)\Big[\frac{\balpha\cdot\bnabla f_t(\bv)}{\balpha\cdot\bv}-\frac{\alpha^2}{2}\frac{(1+\sigma_{\balpha})f_t(\bv)}{(\balpha\cdot\bv)^2}\Big]\\
+\bv\cdot\bnabla f_t(\bv)+Nf_t(\bv).
\end{multline}
This is because Dunkl operators behave like partial derivatives under uniform scalings, i.e., if an arbitrary function $g(\by)$ is scaled as $\tilde{g}(\bv)=g(\sqrt{\beta t}\bv)$, then
\begin{equation}
T_i^{(y)}g(\by)=\frac{1}{\sqrt{\beta t}}T_i^{(v)}\tilde{g}(\bv),
\end{equation}
and also because the time derivative of $f_t(\bv)$ is given by
\begin{multline}
\frac{\partial}{\partial t}f_t(\bv)=\frac{\partial}{\partial t}\Big[f(t,\sqrt{\beta t}\bv)(\beta t)^{N/2}\Big]\\
=\frac{N}{2t}f_t(\bv)+(\beta t)^{N/2}\frac{\partial}{\partial t}f(t,\by)\Big|_{\by=\sqrt{\beta t}\bv}+\frac{1}{2t}\bv\cdot\bnabla f_t(\bv),
\end{multline}
meaning that
\begin{equation}
\frac{\partial}{\partial t}f_t(\bv)=\frac{N}{2t}f_t(\bv)+\frac{1}{2t}\bv\cdot\bnabla f_t(\bv)+\frac{1}{2\beta t}\sum_{i=1}^NT_i^2f_t(\bv).
\end{equation}
Inserting the explicit form of the Dunkl Laplacian into the r.h.s. and moving the factor $2t$ to the l.h.s. gives Eq.~\eqref{ScaledDunklFKE}.

Let us show that $f_\text{ss}(\bv)$ is the steady-state solution of Eq.~\eqref{ScaledDunklFKE}, which amounts to showing that the r.h.s. of Eq.~\eqref{ScaledDunklFKE} vanishes when $f_t(\bv)$ is replaced by $f_\text{ss}(\bv)$. A series of straightforward calculations yield the following expressions:
\begin{IEEEeqnarray}{rCl}
\bv\cdot\bnabla f_\text{ss}(\bv)&=&-\beta(v^2-\gamma)f_\text{ss}(\bv),\\
\balpha\cdot\bnabla f_\text{ss}(\bv)&=&-\beta\Big[\balpha\cdot\bv-\sum_{\bzeta\in R_+}\frac{\kappa(\bzeta)\bzeta\cdot\balpha}{\bzeta\cdot\bv}\Big]f_\text{ss}(\bv),\\
\frac{\partial^2 f_\text{ss}}{\partial v_j^2}&=&\beta^2\Big[v_j-\sum_{\balpha\in R_+}\frac{\kappa(\balpha)\alpha_j }{\balpha\cdot\bv}\Big]^2f_\text{ss}(\bv)\nonumber\\
&&\qquad-\beta\Big[1+\sum_{\balpha\in R_+}\frac{\kappa(\balpha)\alpha_j^2 }{(\balpha\cdot\bv)^2}\Big]f_\text{ss}(\bv).
\end{IEEEeqnarray}
Then, the r.h.s. of Eq.~\eqref{ScaledDunklFKE} for $f_\text{ss}(\bv)$ is equal to
\begin{multline}
\beta\Big[v^2-2\gamma+\sum_{\balpha,\bzeta\in R_+}\frac{\kappa(\balpha)\kappa(\bzeta)\balpha\cdot\bzeta}{(\balpha\cdot\bv)(\bzeta\cdot\bv)}\Big]f_\text{ss}(\bv)-\Big[N+\sum_{\balpha\in R_+}\frac{\kappa(\balpha)\alpha^2 }{(\balpha\cdot\bv)^2}\Big]f_\text{ss}(\bv)\\
-\sum_{\balpha\in R_+}\kappa(\balpha)\Big[-\beta+\beta\sum_{\bzeta\in R_+}\frac{\kappa(\bzeta)\bzeta\cdot\balpha}{(\balpha\cdot\bv)(\bzeta\cdot\bv)}-\frac{\alpha^2}{(\balpha\cdot\bv)^2}\Big]f_\text{ss}(\bv)\\
-\beta(v^2-\gamma)f_\text{ss}(\bv) +Nf_\text{ss}(\bv).
\end{multline}
A close inspection of this expression reveals that, indeed, all terms cancel, meaning that the steady-state distribution of the process is obtained from normalizing $f_\text{ss}(\bv)$.

\section{Setting}

With the initial condition $\mu(\bx)$, the probability distribution of a Dunkl process using the Dunkl transform representation~\eqref{TransitionDensityTransform} is given by
\begin{equation}\label{ProbabilityDensityTransform}
f(t,\by)\ud\by=\frac{w_\beta(\by)}{c_\beta^2}\int_{\RR^N}\rme^{-t\xi^2/2}[V_\beta \rme^{\rmi \by\cdot\bxi}]\Big[\int_{\RR^N}[V_\beta \rme^{-\rmi \bx\cdot\bxi}]\mu(\bx)\ud\bx\Big] w_\beta(\bxi)\ud\bxi\ud\by.
\end{equation}
The main advantage of this expression is that all the integrals are well behaved due to the fact that $V_\beta \rme^{\rmi \bx\cdot\by}$ is bounded (see Eq.~\eqref{DunklKernelInTheTransform}). Recall the function
\begin{equation}\label{PotentialR}
F_R(\bv,\kappa)=\frac{v^2}{2}-\sum_{\balpha\in R_+} \kappa(\balpha)\log |\balpha\cdot\bv|,
\end{equation}
so that
\begin{equation}
f_\text{ss}(\bv)=\rme^{-\beta F_R(\bv,\kappa)}=\rme^{-\beta v^2/2}w_\beta(\bv)
\end{equation}
and
\begin{equation}\label{PartitionR}
z_\beta=\int_{\RR^N}\rme^{-\beta F_R(\bzeta,\kappa)}\ud\bzeta=\int_{\RR^N}f_\text{ss}(\bzeta)\ud\bzeta.
\end{equation}
With these expressions, we define the steady-state distribution by
\begin{equation}
f_R(\bv):=\frac{1}{z_\beta}f_\text{ss}(\bv)=\frac{1}{z_\beta}\rme^{-\beta F_R(\bv,\kappa)}.
\end{equation}
Also, assume that $\mu(\bx)$ is a probability distribution with finite second-order moments, i.e.,
\begin{equation}
\Big|\int_{\RR^N}x_i x_j \mu(\bx)\ud\bx\Big|<\infty.
\end{equation}
The mean and variance of $\mu(\bx)$ are defined by
\begin{IEEEeqnarray}{rCl}
\bar{\bx}_\mu&:=&\int_{\RR^N}\bx\mu(\bx)\ud\bx,\label{MuFirstMoments}\\
s_\mu^2&:=&\int_{\RR^N}|\bx-\bar{\bx}_\mu|^2\mu(\bx)\ud\bx\label{MuSecondMoment}
\end{IEEEeqnarray}
respectively. In this chapter, the main goal is to prove the following.
\begin{theorem}\label{TheoremSteadyState}
Dunkl processes relax to the scaled steady state distribution
\begin{equation}
f(t,\sqrt{\beta t}\bv)(\beta t)^{N/2}\ud\bv=f_R(\bv,\beta)\ud\bv[1+O(\eta\sqrt{\beta})+O(\epsilon^2)]
\end{equation}
whenever
\begin{equation}\label{GeneralRelaxationTime}
t\gg (s_\mu^2+\bar{x}_\mu^2)\max[1,\beta]
\end{equation}
with positive numbers $\eta$ and $\epsilon$ such that
\begin{equation}\label{EquationFinalConditionsEpsilonEta}
\epsilon^2t\gg1\quad\text{and}\quad\eta^2 t \min[1,\beta]\gg 1.
\end{equation}
\end{theorem}

In Sec.~\ref{ProofTheoremSteadyState} we prove Thm.~\ref{TheoremSteadyState}, in which the evaluation of the integrals in Eq.~\eqref{ProbabilityDensityTransform} is important. The derivations given in Sec.~\ref{IntegralOverU} are used for the calculations in the proof.

\section{Setup for the proof of Theorem~\ref{TheoremSteadyState}}\label{IntegralOverU}

With the substitutions $\by=\sqrt{\beta t}\bv$, $\bxi=\bzeta/\sqrt{t}$ and $\bx=\bu\sqrt{t}$, Eq.~\eqref{ProbabilityDensityTransform} reads
\begin{multline}\label{ScaledProbabilityDensityTransform}
f(t,\sqrt{\beta t}\bv)(\beta t)^{N/2}\ud\bv=\frac{w_\beta(\bv)}{z_\beta c_\beta}\int_{\RR^N}\rme^{-\zeta^2/2}[V_\beta \rme^{\rmi \sqrt{\beta}\bv\cdot\bzeta}]\\
\times\Big[\int_{\RR^N}[V_\beta \rme^{-\rmi \bu\cdot\bzeta}]t^{N/2}\mu(\sqrt{t}\bu)\ud\bu\Big] w_\beta(\bzeta)\ud\bzeta\ud\bv.
\end{multline}
The first quantity that must be considered is the integral over $\bu$, which is given the following notation,
\begin{equation}
\mathcal{I}(t,\bzeta):=\int_{\RR^N}[V_\beta \rme^{-\rmi \bu\cdot\bzeta}]t^{N/2}\mu(\sqrt{t}\bu)\ud\bu.
\end{equation}
By the mean value theorem, there exist vectors $\bu_\text{r}$ and $\bu_\text{i}$ such that
\begin{equation}\label{FirstApproximationI1}
\mathcal{I}(t,\bzeta)=V_\beta[\cos(\bu_\text{r}\cdot\bzeta)-\rmi\sin(\bu_\text{i}\cdot\bzeta)].
\end{equation}
In general, $\bu_\text{r}$ and $\bu_\text{i}$ are functions of $\bzeta$. From the relations
\begin{IEEEeqnarray}{rCl}
&\int_{\RR^N}\bu t^{N/2}\mu(\sqrt{t}\bu)\ud\bu=\bar{\bx}_\mu/\sqrt{t},&\\
&\int_{\RR^N}(\bu-\bar{\bx}_\mu/\sqrt{t})^2t^{N/2}\mu(\sqrt{t}\bu)\ud\bu=s_\mu^2/t,&
\end{IEEEeqnarray}
it follows that $\mathcal{I}(t,\bzeta)$ satisfies the following equations when $\bzeta=\bzero$,
\begin{IEEEeqnarray}{rCl}
T_j\mathcal{I}(t,\bzero)&=&-\rmi\frac{\bar{x}_{\mu,j}}{\sqrt{t}},\\
\sum_{j=1}^NT_j^2\mathcal{I}(t,\bzero)&=&-\frac{1}{t}(s_\mu^2+\bar{x}_\mu^2).
\end{IEEEeqnarray}
Inserting Eq.~\eqref{FirstApproximationI1} in these two equations gives
\begin{IEEEeqnarray}{rCl}
T_jV_\beta[\cos(\bu_\text{r}\cdot\bzeta)-\rmi\sin(\bu_\text{i}\cdot\bzeta)]|_{\bzeta=\bzero}&=&-\rmi (\bu_\text{i})_j|_{\bzeta=\bzero},\\
\sum_{j=1}^NT_j^2V_\beta[\cos(\bu_\text{r}\cdot\bzeta)-\rmi\sin(\bu_\text{i}\cdot\bzeta)]|_{\bzeta=\bzero}&=&-u_\text{r}^2|_{\bzeta=\bzero}.
\end{IEEEeqnarray}
Therefore, one has
\begin{IEEEeqnarray}{rCl}
\bu_\text{I}&:=&\bu_\text{i}|_{\bzeta=\bzero}=\bar{\bx}_\mu/\sqrt{t},\label{EquationForUI}\\
u_\text{R}^2&:=&u_\text{r}^2|_{\bzeta=\bzero}=(s_\mu^2+\bar{x}_\mu^2)/t.\label{EquationForUR}
\end{IEEEeqnarray}
Thus, for $\zeta^2\ll t/(s_\mu^2+\bar{x}_\mu^2)$, the integral $\mathcal{I}(t,\bzeta)$ is approximated by
\begin{equation}\label{EquationApproximationForI}
V_\beta[\cos(\bu_\text{R}\cdot\bzeta)-\rmi\sin(\bu_\text{I}\cdot\bzeta)]+O(\zeta^2/t).
\end{equation}
The term of $O[\zeta^2/t]$ is included because this approximation is obtained from the behavior of $\mathcal{I}(t,\bzeta)$ near $\bzeta=\bzero$, and only the action of first-order Dunkl operators is reproduced exactly (only the norm of $\bu_\text{R}$ is specified).

For the estimation of the relaxation time $t_\epsilon$, it will be necessary to consider the linear approximation of the function $V_\beta \sinh(\bx\cdot\by)$. The effect of the intertwining operator on linear functions is given in the following lemma. Here, an orthonormal basis $\{\bphi_i\}_{i=1}^N$ of $\RR^N$ is defined such that the first $d_R$ vectors belong to the linear envelope of $R$ and the last $N-d_R$ vectors are orthogonal to it.
\begin{lemma}\label{LemmaFirstOrderV}
For linear polynomials, $V_\beta$ is given by
\begin{equation}
V_\beta\bx\cdot\by=\frac{1}{1+\beta\gamma/d_R}\Big[\bx\cdot\by+\frac{\beta\gamma}{d_R}\sum_{i=d_R+1}^{N}(\bx\cdot\bphi_i)(\by\cdot\bphi_i)\Big].\label{FirstOrderVNotFullRank}
\end{equation}
\end{lemma}

\begin{proof}
Let $V_\beta$ be represented in the linear case by a matrix, $[M_\beta]_{ij}=m_{ij}$, such that
\begin{equation}
V_\beta\bx\cdot\by=\sum_{1\leq i,j\leq N}x_im_{ij}y_j.
\end{equation}
By the defining property of $V_\beta$, Eq.~\eqref{EquationVDefinition}, the relationship
\begin{equation}
y_i=\sum_{j=1}^N m_{ij}y_j+\frac{\beta}{2}\sum_{\balpha\in R_+}\alpha_i\frac{\kappa(\balpha)}{\balpha\cdot\bx}(1-\sigma_{\balpha})\sum_{1\leq i,j\leq N}x_lm_{lj}y_j
\end{equation}
holds. Rewritten in terms of vector and matrices, this equation is equivalent to
\begin{equation}
(1-\sigma_{\balpha})\bx^TM_\beta \by=\Big(2\frac{\balpha\cdot\bx}{\alpha^2}\balpha\Big)^T M_\beta \by=2\frac{\balpha\cdot\bx}{\alpha^2}\balpha^TM_\beta\by,
\end{equation}
which yields
\begin{equation}
\by=M_\beta\by+\beta\sum_{\balpha\in R_+}\kappa(\balpha)\frac{\balpha\balpha^T}{\alpha^2}M_\beta\by=\Bigg[I+\beta\sum_{\balpha\in R_+}\kappa(\balpha)\frac{\balpha\balpha^T}{\alpha^2}\Bigg]M_\beta \by.\label{FirstOrderV}
\end{equation}
The problem is reduced, then to calculating
\begin{equation}\label{AlmostTheMWeWant}
M_\beta=\Bigg[I+\beta\sum_{\balpha\in R_+}\kappa(\balpha)\frac{\balpha\balpha^T}{\alpha^2}\Bigg]^{-1}.
\end{equation}

To calculate $M_\beta$, we need to calculate the sum over $\balpha$, a task that can be accomplished easily once the sum is rewritten as a sum over a group. If $\by$ is orthogonal to $\spn (R)$, then the sum over $\balpha$ is equal to zero and the result is trivial; therefore, we assume that $\by\in\spn(R)$. First, we separate terms with different multiplicities: let $n_R$ denote the number of different multiplicities assigned to the root system R, and denote by $\{\bxi_i\}_{i=1}^{n_R}$ a collection of roots such that $\kappa(\bxi_i)\neq\kappa(\bxi_j)$ for $i\neq j$. Then, the following holds:
\begin{equation}
\sum_{\balpha\in R_+}\kappa(\balpha)\frac{\balpha\balpha^T}{\alpha^2}=\sum_{i=1}^{n_R}\frac{\kappa(\bxi_i)}{|\bxi_i|^2}\sum_{\balpha\in R_+\cap W\bxi_i}\balpha\balpha^T.
\end{equation}
Here, $W\bxi_i=\{\rho\bxi_i: \rho\in W\}$ denotes the orbit of $\bxi_i$ on $W$. To obtain this equality it suffices to note that the terms in the sum with equal multiplicities must belong to the same orbit in $W$. Because $W$ is a reflection group, all of its elements are isometries, meaning that the roots of $R$ in the orbit of $\bxi_i$ must have the same norm. Then, the squared norm of $\alpha$ can be taken out of the second sum as the term $|\bxi_i|^2$. Because the vectors $\balpha$ in the second sum are elements of $W\bxi_i$, we can rewrite the sum as
\begin{equation}
\sum_{\balpha\in R_+}\kappa(\balpha)\frac{\balpha\balpha^T}{\alpha^2}=\sum_{i=1}^{n_R}\frac{\kappa(\bxi_i)}{|\bxi_i|^2}\frac{|R_+\cap W\bxi_i|}{|W|}\sum_{\rho\in W}(\rho\bxi_i)(\rho\bxi_i)^T,\label{ProjectorSumUnsolved}
\end{equation}
where the coefficient $|R_+\cap W\bxi_i|/|W|$ is included to account for double counting in the sum over $\rho$. Denote by $[\rho]_{ij}$ the $ij$th component of a faithful and reduced representation of the reflection group $W$. Then, the $jl$th component of the matrix representation of the sum over $\rho$ is
\begin{equation}
\sum_{\rho\in W}[\rho\bxi_i]_j[\rho\bxi_i]_l=\sum_{\rho\in W}\sum_{n,n^\prime=1}^{d_R}[\rho]_{jn}[\bxi_i]_n[\rho]_{ln^\prime}[\bxi_i]_{n^\prime}=\sum_{n,n^\prime=1}^{d_R}[\bxi_i]_{n^\prime}[\bxi_i]_n\sum_{\rho\in W}[\rho]_{jn}[\rho]_{ln^\prime}.
\end{equation}
By the great orthogonality theorem \cite{inuitanabeonodera96},
the sum over $\rho$ is given by
\begin{equation}
\sum_{\rho\in W}[\rho]_{jn}[\rho]_{ln^\prime}=\frac{|W|}{d_R}\delta_{jl}\delta_{nn^\prime},
\end{equation}
which in turn yields
\begin{equation}
\sum_{\rho\in W}[\rho\bxi_i]_j[\rho\bxi_i]_l=\sum_{n,n^\prime=1}^{d_R}[\bxi_i]_{n^\prime}[\bxi_i]_n\frac{|W|}{d_R}\delta_{jl}\delta_{nn^\prime}=\frac{|W||\bxi_i|^2}{d_R}\delta_{jl}.
\end{equation}
Inserting in \eqref{ProjectorSumUnsolved} gives
\begin{equation}
\sum_{\balpha\in R_+}\kappa(\balpha)\frac{\balpha\balpha^T}{\alpha^2}=\sum_{i=1}^{n_R}\kappa(\bxi_i)\frac{|R_+\cap W\bxi_i|}{d_R}I=\frac{I}{d_R}\sum_{\balpha\in R_+}\kappa(\balpha)=\frac{\gamma}{d_R}I.
\end{equation}
This result implies that, for $\by\in\spn(R)$,
\begin{equation}
M_\beta=I/(1+\beta\gamma/d_R).
\end{equation}

The complete form of $M_\beta$ is obtained by noticing that all vectors can be decomposed into the component that belongs to $\spn(R)$ and its orthogonal component:
\begin{equation}
\by=\Big[\by-\sum_{i=d_R+1}^{N}(\bphi_i\cdot\by)\bphi_i\Big]+\sum_{i=d_R+1}^{N}(\bphi_i\cdot\by)\bphi_i.
\end{equation}
Then, one has
\begin{IEEEeqnarray}{rCl}
&&\Big[I+\beta\sum_{\balpha\in R_+}\kappa(\balpha)\frac{\balpha \balpha^T}{\alpha^2}\Big]\Big[\Big(\by-\sum_{i=d_R+1}^{N}(\bphi_i\cdot\by)\bphi_i\Big)+\sum_{i=d_R+1}^{N}(\bphi_i\cdot\by)\bphi_i\Big]\nonumber\\
&&=\Big[\Big(1+\frac{\beta\gamma}{d_R}\Big)I-\frac{\beta\gamma}{d_R}\sum_{i=d_R+1}^{N}\bphi_i\bphi_i^T\Big]\by=M_\beta^{-1}\by,
\end{IEEEeqnarray}
and $M_\beta$ is given by
\begin{equation}
M_\beta=\frac{1}{1+\beta\gamma/d_R}\Big[I+\frac{\beta\gamma}{d_R}\sum_{i=d_R+1}^{N}\bphi_i\bphi_i^T\Big]
\end{equation}
because
\begin{equation}
\Big[\Big(1+\frac{\beta\gamma}{d_R}\Big)I-\frac{\beta\gamma}{d_R}\sum_{i=1+d_R}^{N}\bphi_i\bphi_i^T\Big]\frac{1}{1+\beta\gamma/d_R}\Big[I+\frac{\beta\gamma}{d_R}\sum_{i=d_R+1}^{N}\bphi_i\bphi_i^T\Big]=I,
\end{equation}
which completes the proof.
\end{proof}
Denoting by $\bx_\perp$ the component of $\bx$ that is orthogonal to $\spn(R)$ and by $\bx_\parallel$ the component of $\bx$ which belongs to $\spn(R)$, one may write
\begin{equation}\label{LinearApproximationVSin}
V_\beta \bx\cdot\by = \frac{\bx_{\parallel}\cdot\by_\parallel}{1+\beta\gamma/d_R}+\bx_{\perp}\cdot\by_\perp.
\end{equation}
Unless otherwise noted, the subscripts $\perp$ and $\parallel$ in this equation will carry the meaning described here for the rest of the text. This last equation implies that the intertwining operator has no effect on linear functions of vectors that are orthogonal to the root system.

\section{Proof of Theorem~\ref{TheoremSteadyState}}\label{ProofTheoremSteadyState}

The first objective is to calculate the approximate value of the integral
\begin{equation}
\mathcal{J}(t,\bv):=\frac{1}{c_\beta}\int_{\RR^N}\rme^{-\zeta^2/2} \mathcal{I}(t,\bzeta) [V_\beta \rme^{\rmi \sqrt{\beta}\bv\cdot\bzeta}] w_\beta(\bzeta)\ud\bzeta,
\end{equation}
for large values of $t$. This expression is the inverse Dunkl transform of $\rme^{-\zeta^2/2} \mathcal{I}(t,\bzeta)$ evaluated at $\sqrt{\beta}\bv$ (see Eq.~\eqref{InverseDunklTransform}). In order to use the approximated form of $ \mathcal{I}(t,\bzeta) $, the positive variable $\epsilon$ is chosen with the assumption that $\sqrt{t}\epsilon\gg 1$. Then, $\mathcal{J}(t,\bv)$ is divided into two integrals. The first one, denoted $\mathcal{J}_1$, is taken over $\zeta<\sqrt{t}\epsilon$, while the second one, denoted $\mathcal{J}_2$ is taken over  $\zeta\geq\sqrt{t}\epsilon$. For $\mathcal{J}_2$, one has the following behavior:
\begin{multline}\label{EquationBoundForOuterIntegral}
|\mathcal{J}_2|\leq\frac{1}{c_\beta}\int_{\zeta\geq\sqrt{t}\epsilon}\rme^{-\zeta^2/2}  w_\beta(\bzeta)\ud\bzeta=\frac{C_\mathcal{J}}{c_\beta}\int_{\sqrt{t}\epsilon}^\infty\rme^{-\zeta^2/2} \zeta^{\beta\gamma+N-1}\ud\zeta\\
=\frac{C_\mathcal{J}2^{(\beta\gamma+N-2)/2)}}{c_\beta}\int_{t\epsilon^2/2}^\infty\rme^{-z} z^{(\beta\gamma+N-2)/2}\ud z=O(\rme^{-t\epsilon^2/2}(t\epsilon^2)^{(\beta\gamma+N-2)/2}).
\end{multline}
Here, $C_\mathcal{J}$ denotes the angular part of the integral, the substitution $z=\zeta^2/2$ was carried out in the second line, and the final step is obtained from integration by parts. Note that the first inequality follows from the fact that $\mathcal{I}(t,\bzeta)$ is bounded,
\begin{equation}
|\mathcal{I}(t,\bzeta)|\leq\int_{\RR^N}|V_\beta \rme^{-\rmi \bu\cdot\bzeta}|t^{N/2}\mu(\sqrt{t}\bu)\ud\bu\leq\int_{\RR^N}\mu(\bx)\ud\bx=1.
\end{equation}

Integrals of this form appear repeatedly in this derivation. Thus, it is convenient to have the general expression
\begin{equation}\label{EquationIntegralOutside}
\frac{1}{c_\beta}\int_{\zeta\geq\sqrt{t}\epsilon}\rme^{-\zeta^2/2} g(\bzeta) w_\beta(\bzeta)\ud\bzeta=O(\rme^{-t\epsilon^2/2}(t\epsilon^2)^{(\beta\gamma+N+r-2)/2})
\end{equation}
provided that $g(\bzeta)\sim \zeta^r$ for large $\zeta$, which is derived using the procedure that leads to Eq.~\eqref{EquationBoundForOuterIntegral}.

Using Eq.~\eqref{EquationApproximationForI}, one may separate the integral over the region $\zeta<\epsilon\sqrt{t}$, $\mathcal{J}_1$, into the part that corresponds to the cosine ($\mathcal{J}_{\cos}$), the part that corresponds to the sine ($\mathcal{J}_{\sin}$), and the part that corresponds to the lower-order terms ($\mathcal{J}_\text{o}$). After extending the domain of integration to $\RR^N$ at the expense of the error term from Eq.~\eqref{EquationIntegralOutside} with $r=0$, the first integral reads
\begin{multline}
\mathcal{J}_{\cos}=\frac{1}{2c_\beta}\int_{\RR^N}\rme^{-\zeta^2/2}V_\beta(\rme^{\rmi \bu_\text{R}\cdot\bzeta}+\rme^{-\rmi\bu_\text{R}\cdot\bzeta})V_\beta\rme^{\rmi\sqrt{\beta}\bv\cdot\bzeta}w_\beta(\bzeta)\ud\bzeta\\
+O(\rme^{-t\epsilon^2/2}(t\epsilon^2)^{(\beta\gamma+N-2)/2}).
\end{multline}
Using Eq.~\eqref{GaussianIntegralDunklKernel}, this integral can be evaluated immediately, yielding
\begin{equation}
\mathcal{J}_{\cos}=\rme^{-(u_\text{R}^2+\beta v^2)/2}V_\beta\cosh(\sqrt{\beta} \bu_\text{R}\cdot\bv)
+O(\rme^{-t\epsilon^2/2}(t\epsilon^2)^{(\beta\gamma+N-2)/2}).
\end{equation}
The integral $\mathcal{J}_{\sin}$ can be evaluated in a similar manner as
\begin{equation}
\mathcal{J}_{\sin}=\rme^{-(u_\text{I}^2+\beta v^2)/2}V_\beta\sinh(\sqrt{\beta} \bu_\text{I}\cdot\bv)
+O(\rme^{-t\epsilon^2/2}(t\epsilon^2)^{(\beta\gamma+N-2)/2}).
\end{equation}
The final integral $\mathcal{J}_\text{o}$ is also calculated using Eq.~\eqref{EquationIntegralOutside}:
\begin{multline}
\mathcal{J}_\text{o}=\frac{O[\epsilon^2]}{c_\beta}\int_{\zeta<\sqrt{t}\epsilon}\rme^{-\zeta^2/2}V_\beta\rme^{\rmi\sqrt{\beta}\bv\cdot\bzeta}w_\beta(\bzeta)\ud\bzeta\\
=O[\epsilon^2]\Big[\frac{1}{c_\beta}\int_{\RR^N}\rme^{-\zeta^2/2}V_\beta\rme^{\rmi\sqrt{\beta}\bv\cdot\bzeta}w_\beta(\bzeta)\ud\bzeta+O(\rme^{-t\epsilon^2/2}(t\epsilon^2)^{(\beta\gamma+N-2)/2})\Big]\\
=O[\epsilon^2][\rme^{-\beta v^2/2}+O(\rme^{-t\epsilon^2/2}(t\epsilon^2)^{(\beta\gamma+N-2)/2})].
\end{multline}

For a very large value of $t\epsilon^2$, the term $O(\rme^{-t\epsilon^2/2}(t\epsilon^2)^{(\beta\gamma+N-2)/2})$ can be neglected. For this regime, the result is
\begin{multline}\label{EquationApproximationForJ}
\mathcal{J}(t,\bv)=\rme^{-\beta v^2/2}\{\rme^{-u_\text{R}^2/2}V_\beta\cosh(\sqrt{\beta} \bu_\text{R}\cdot\bv)\\
+\rme^{-u_\text{I}^2/2}V_\beta\sinh(\sqrt{\beta} \bu_\text{I}\cdot\bv)+O[\epsilon^2]\}.
\end{multline}
Let us recall from Eq.~\eqref{EquationApproximationForI} that this result holds only when the conditions
\begin{equation}\label{EquationFirstIntegralConditionForT}
t\epsilon^{2}\gg 1\quad\text{and}\quad t u_\text{R}^2\epsilon^{2}=\epsilon^{2}(s_\mu^2+\bar{x}_\mu^2)\ll1
\end{equation}
are satisfied. From Eqs.~\eqref{EquationForUI}, \eqref{EquationForUR}, and \eqref{EquationApproximationForJ}, it is clear that
\begin{equation}
\mathcal{J}(t,\bv)\stackrel{t\to\infty}{\longrightarrow}\rme^{-\beta v^2/2},
\end{equation}
as expected.

The second objective of this derivation is, then, to find a lower bound on the time required to reach the steady state. Because $t$ is required to be large in the previous result, additional approximations can be made. The expression $V_\beta\cosh(\bu_\text{R}\cdot\bv)$ for $u_\text{R}v\ll 1$ is approximated by noticing that the function
\begin{equation}\label{ApproximationVCosine}
g(\bv,\bu_\text{R})=\exp\Big[\frac{v^2u_\text{R}^2}{2(N+\beta\gamma)}\Big]
\end{equation}
behaves roughly like $V_\beta\cosh(\bu_\text{R}\cdot\bv)$ in the following sense. Consider the expression
\begin{equation}
\sum_{j=1}^N T_j^2 V_\beta\cosh(\bu_\text{R}\cdot\bv)|_{\bzeta=\bzero}=u_\text{R}^2,
\end{equation}
where the Dunkl operators act on $\bv$. A straightforward calculation gives
\begin{equation}
\Delta_v g(\bv,\bu_\text{R})=\frac{u_\text{R}^2}{N+\beta\gamma}\Big[\frac{v^2u_\text{R}^2}{N+\beta\gamma}+N\Big]g(\bzeta,\bu_\text{R})
\end{equation}
and
\begin{equation}
\beta\sum_{\balpha\in R_+}\kappa(\balpha)\frac{\balpha\cdot\bnabla_v g(\bv,\bu_\text{R})}{\balpha\cdot\bv}=\frac{\beta\gamma u_\text{R}^2}{N+\beta\gamma}g(\bv,\bu_\text{R}),
\end{equation}
which yields
\begin{equation}
\sum_{j=1}^N T_j^2 g(\bv,\bu_\text{R})|_{\bv=\bzero}=u_\text{R}^2.
\end{equation}
It follows that $g(\bv,\bu_\text{R})$ reproduces the isotropic part of the second-order term of $V_\beta\cosh(\bu_\text{R}\cdot\bv)$ at $\bv=\bzero$. Consequently, the combination of $g(\bzeta,\bu_\text{R})$ and Eq.~\eqref{LinearApproximationVSin} gives an approximation of the hyperbolic sine and cosine terms that is only accurate up to first order, but which is still better than a simple first-order approximation:
\begin{multline}\label{EquationDoubleApproximationForJ}
\rme^{\beta v^2/2}\mathcal{J}(t,\bv)-O(\epsilon^2)=\rme^{-u_\text{R}^2/2}V_\beta\cosh( \sqrt{\beta}\bu_\text{R}\cdot\bv)
+\rme^{-u_\text{I}^2/2}V_\beta\sinh( \sqrt{\beta}\bu_\text{I}\cdot\bv)\\
=\exp\Big[-\frac{u_\text{R}^2}{2}\Big(1-\frac{\beta v^2}{N+\beta\gamma}\Big)\Big] + \rme^{-u_\text{I}^2/2}\Big[\frac{\sqrt{\beta}\bu_{\text{I}\parallel}\cdot\bv_\parallel}{1+\beta\gamma/d_R}+\sqrt{\beta}\bu_{\text{I}\perp}\cdot\bv_\perp  \Big] +O(\beta v^2/t).
\end{multline}

The choice of the function $g(\bv,\bu_\text{R})$ is motivated by the fact that if the approximation is carried out up to first order, the information concerning the second moments of $\mu(\bx)$ is lost. Approximating the function $V_\beta\cosh(\bu_\text{R}\cdot\bv)$ using an isotropic function such as $g(\bv,\bu_\text{R})$ neglects the anisotropies that correspond to the vector $\bu_\text{R}$ as well as those that correspond to the intertwining operator, but it also allows one to have an approximate form of the hyperbolic functions which carries additional information about the initial distribution.

To estimate the relaxation time, consider a test function $h(\bv)$ with a power-law asymptotic behavior $h(\bv)\sim v^r$ when $v$ is very large. Define the expectation of $h$ over the steady-state distribution by
\begin{equation}
\langle h \rangle:=\int_{\RR^N}h(\bv)f_R(\beta,\bv)\ud\bv.
\end{equation}
Then, the expectation of $h$ before the steady-state is achieved is given by
\begin{equation}\label{EquationAverageBeforeRelaxation}
\langle h \rangle_t:=\frac{1}{z_\beta}\int_{\RR^N}h(\bv)w_\beta(\bv)\mathcal{J}(t,\bv)\ud\bv.
\end{equation}
Equation~\eqref{EquationDoubleApproximationForJ} can only be used if the inequality
\begin{equation}
\frac{(s_\mu^2+\bar{x}_\mu^2)\beta v^2}{t}\ll 1
\end{equation}
is satisfied. Therefore, the integral \eqref{EquationAverageBeforeRelaxation} can be divided into the region where $v<\eta\sqrt{t}$ and the region where $v\geq\eta\sqrt{t}$, where it is assumed that $\eta\sqrt{t}\gg 1$.

Denote the integral over the former region by $\mathcal{K}_1$ and the latter by $\mathcal{K}_2$. After making the substitution $\bv^\prime=\sqrt{\beta}\bv$, the integral over the outer region is given by
\begin{multline}
|\mathcal{K}_2|\leq\frac{1}{c_\beta}\int_{v^\prime\geq\eta\sqrt{\beta t}}|h(\bv^\prime/\sqrt{\beta})|w_\beta(\bv^\prime)\rme^{- (v^\prime)^2/2}|\{\rme^{-u_\text{R}^2/2}V_\beta\cosh(\bu_\text{R}\cdot\bv^\prime)\\
+\rme^{-u_\text{I}^2/2}V_\beta\sinh(\bu_\text{I}\cdot\bv^\prime)+O[\epsilon^2]\}|\ud\bv^\prime\\
\leq \frac{C_\mathcal{K}}{c_\beta}
\int_{\eta\sqrt{\beta t}}^\infty
(v^\prime)^{\beta\gamma+N-1}
(v^\prime/\sqrt{\beta})^r
\{\rme^{- (v^\prime-u_\text{R})^2/2}/2
+\rme^{-(v^\prime-u_\text{I})^2/2}/2\\
+\rme^{-(v^\prime)^2/2}O[\epsilon^2]\}\ud\bv^\prime.
\end{multline}
For the final expression, the asymptotic form of $h(\bv)$ was used, as well as the bounds and asymptotic forms for $v^\prime\gg 1$
\begin{IEEEeqnarray}{rCl}
|V_\beta\cosh(\bu_\text{R}\cdot\bv^\prime)|\leq \cosh(u_\text{R}v^\prime)\sim \exp(u_\text{R}v^\prime)/2,\\
|V_\beta\sinh(\bu_\text{I}\cdot\bv^\prime)|\leq \sinh(u_\text{I}v^\prime)\sim \exp(u_\text{I}v^\prime)/2.
\end{IEEEeqnarray}
The coefficient $C_\mathcal{K}$ represents the value of the angular integral. By Eq.~\eqref{EquationIntegralOutside}, one obtains
\begin{equation}\label{EquationNonSteadyStateExpectationOuterIntegral}
\mathcal{K}_2= O[\rme^{-\eta^2\beta t/2}(\eta^2 \beta t)^{(\beta\gamma+N+r-2)/2}\beta^{-r/2}(1+\epsilon^2)].
\end{equation}
Therefore, one must assume that $\eta\sqrt{\beta t}\gg 1$ in order to neglect the terms with exponential decay.

The inner integral is divided into the lower-order ($\mathcal{K}_o$), sine ($\mathcal{K}_{\sinh}$) and cosine ($\mathcal{K}_{\cosh}$) terms. Unless otherwise noted, exponentially decreasing correction terms (e.g., the correction in Eq.~\eqref{EquationNonSteadyStateExpectationOuterIntegral}) will be implicit in each of the expressions that follow. The lower-order integral is immediate,
\begin{multline}
\mathcal{K}_o=\frac{O(\epsilon^2)+O(\beta\eta^2)}{c_\beta}\int_{v^\prime<\eta\sqrt{\beta t}}h(\bv^\prime/\sqrt{\beta})w_\beta(\bv^\prime)\rme^{- (v^\prime)^2/2}\ud\bv^\prime\\
=\langle h \rangle [O(\epsilon^2)+O(\beta\eta^2)].
\end{multline}
The sine term becomes, assuming that $\eta\ll1/\sqrt{\beta \bar{x}_\mu^2}$,
\begin{multline}\label{EquationRelaxationSinh}
\mathcal{K}_{\sinh} = \frac{1}{c_\beta}\int_{v^\prime<\eta\sqrt{\beta t}}h(\bv^\prime/\sqrt{\beta})w_\beta(\bv^\prime)\rme^{- (v^\prime)^2/2}\\
\times\rme^{-u_\text{I}^2/2}\Big[\frac{\bu_{\text{I}\parallel}\cdot\bv^\prime_\parallel}{1+\beta\gamma/d_R}+\bu_{\text{I}\perp}\cdot\bv^\prime_\perp\Big]\ud\bv^\prime.
\end{multline}
Within this region of integration, the bound
\begin{equation}\label{AttentionSlowRelaxation}
\Big|\frac{\bu_{\text{I}\parallel}\cdot\bv^\prime_\parallel}{1+\beta\gamma/d_R}+\bu_{\text{I}\perp}\cdot\bv^\prime_\perp\Big|\leq \frac{\eta\sqrt{\beta}}{\bar{x}_\mu}\Big[\frac{\bar{x}_{\mu\parallel}^2}{1+\beta\gamma/d_R}+\bar{x}_{\mu\perp}^2\Big]
\end{equation}
is satisfied. This means that
\begin{equation}
\mathcal{K}_{\sinh}=\langle h\rangle O(\eta\sqrt{\beta}),
\end{equation}
where the correction term comes from Eq.~\eqref{AttentionSlowRelaxation}, and $\langle h \rangle$ comes from Eq.~\eqref{EquationRelaxationSinh} after taking $u_\text{I}\to 0$ due to the inequality \eqref{EquationFirstIntegralConditionForT}. The cosine term becomes, after using Eq.~\eqref{ApproximationVCosine},
\begin{multline}
\mathcal{K}_{\cosh}=\frac{1}{c_\beta}\int_{v^\prime<\eta\sqrt{\beta t}}h(\bv^\prime/\sqrt{\beta})w_\beta(\bv^\prime)\exp\Big[-\frac{(v^\prime)^2}{2} \Big(1-\frac{s_\mu^2+\bar{x}_\mu^2}{t(\beta\gamma+N)}\Big)\Big]\ud\bv^\prime\\
\times\rme^{-(s_\mu^2+\bar{x}_\mu^2)/(2t)}=\langle h \rangle.
\end{multline}
For the last equality, Eq.~\eqref{EquationFirstIntegralConditionForT} has been used. Finally, adding all the terms and discarding higher orders of $\epsilon$ and $\eta$ yields
\begin{equation}
\langle h\rangle_t=\langle h \rangle [1+O(\eta\sqrt{\beta})+O(\epsilon^2)],
\end{equation}
provided that all of the following assumptions are satisfied,
\begin{multline}\label{EquationSecondIntegralConditionForT}
t\gg s_\mu^2 +\bar{x}_\mu^2,\quad \epsilon^2t\gg1,\quad \epsilon^{-2}\gg s_\mu^2+\bar{x}_\mu^2,\quad \\
\eta^2 \beta t\gg 1,\quad \eta^2 t\gg 1,\quad \eta^{-2}\gg \beta(s_\mu^2+\bar{x}_\mu^2).
\end{multline}
Therefore, the distribution must be relaxed to the steady state for $t\gg(s_\mu^2+\bar{x}_\mu^2)\max[1,\beta]$. The statement follows. \qquad\ \qquad\ \qquad\ \qquad \qquad\ \qquad\ \qquad $\square$

While the time bound in Theorem~\ref{TheoremSteadyState} guarantees the relaxation of the system to the steady state, it is not a true estimation of the relaxation time. The time bound estimated here implies that as $\beta$ grows, a longer time is required for the system to relax in general. This is not true at least in the freezing limit, where the system achieves the steady state instantaneously. This property of Dunkl processes in the freezing limit will be proved in Chapter~\ref{general_freezing}. If one assumes a smooth change of behavior from a Dunkl process as $\beta$ changes, then it seems reasonable to believe that Dunkl processes reach the steady state in a small time for large values of $\beta$. This means that there exists an estimation of the relaxation time that can be achieved by making some assumptions on the initial distribution, e.g. compact support, exponential decay at large $\bx$, etc. The result presented here, however, only requires $\mu(\bx)$ to have finite second moments, and in consequence gives a time bound that seems to exceed the actual relaxation time of the system.

It is also worth noting that  Eq.~\eqref{AttentionSlowRelaxation} is responsible for the highest-order correction. Because $1+\beta\gamma/d_R>1$, the largest correction is caused by the component of $\bar{\bx}_\mu$ that is orthogonal to the root system. This means that if the mean of $\mu(\bx)$ has a large component in the space that is orthogonal to $\spn(R)$, the Dunkl process will take a long time to reach the steady state. This fact will be illustrated using numerical simulations of the interacting Brownian motions in Chapter~\ref{ParticularCases}. In addition, if $\bar{\bx}_{\mu\perp}=\bzero$, the correction due to Eq.~\eqref{AttentionSlowRelaxation} decreases in magnitude as $\beta$ grows. Therefore, Dunkl processes on a root system of full rank converge more rapidly to the steady state at large $\beta$ than on a root system with $d_R<N$ in general.

config: arxiv