text:
\section{Introduction}\label{sec:intro}
Over the last decades, the acquisition of geometrically complex data in various fields of application has increased drastically. For the digital organization and analysis of such data it is important to have meaningful notions of \textit{similarity} between datasets as well as between shapes. This most certainly holds true for the area of 3-D object matching, which has many relevant applications, for example in computer vision \citep{viola2001rapid, TorralbaContextbasedvisionsystem2003}, mechanical engineering \citep{AuFeaturebasedreverseengineering1999, El-Mehalawidatabasesystemmechanical2003} or molecular biology \cite{NussinovEfficientdetectionthreedimensional1991, Sandakautomatedcomputervision1995,KrissinelSecondarystructurematchingSSM2004}. In most of these applications, an important challenge is to distinguish between shapes while regarding identical objects in different spatial orientations as equal. A prominent example is the comparison of 3-D protein structures, which is important for understanding structural, functional and evolutionary relationships among proteins \cite{kolodny2005comprehensive,srivastava2016efficient}. Most known protein structures are published as coordinate files, where for every atom a 3-D coordinate is estimated based on an indirect observation of the protein's electron density (see \citet{rhodes2010crystallography} for further details), and stored e.g. in the protein database \textbf{PDB} \cite{proteindatabase}. These coordinate files lack any kind of orientation and any meaningful comparison has to take this into account. \Cref{fig: pose invariant protein matching} (created with \text{PyMOL} \cite{PyMol}) shows two cartoon representations of the backbone of the protein structure 5D0U in two different poses. These two representations obtained from the same coordinate file highlight the difficulty to identify them from noisy measurements.

\begin{figure}
	\centering
	\begin{subfigure}[c]{0.49\textwidth}
		\centering
		\includegraphics[ height=0.85\textwidth,trim=.01cm .01cm .01cm .01cm, clip]{Graphics/5d0u.png}
	\end{subfigure}
	\begin{subfigure}[c]{0.49\textwidth}
				\centering
		\includegraphics[ height=0.85\textwidth,trim=.01cm .01cm .01cm .01cm, clip]{Graphics/5d0u_3.png}
	\end{subfigure}
	\caption{\textbf{Illustration of the proteins to be compared:} Cartoon representation of the DEAH-box RNA-helicase Prp43 from chaetomium thermophilum bound to ADP (PDB ID: 5D0U \cite{tauchert2016structural}) in two different poses. The DEAH-box helicase Prp43 unwinds double stranded RNA and rearranges RNA/protein complexes. It has essential roles in pre-mRNA splicing and ribosome biogenesis \cite{arenas1997prp43,lebaron2005splicing}.}
	\label{fig: pose invariant protein matching}
\end{figure}

\noindent Consequently, many approaches to pose invariant shape matching, classification and recognition have been suggested and studied in the literature. The majority of these methods computes and compares certain invariants or signatures in order to decide whether the considered objects are \textit{equal} up to a previously defined notion of invariance. In the literature, these methods are often called \textit{feature} (or \textit{signature}) based methods, see \citet{CardenasFeaturebasedSimilaritySearch2005} for a comprehensive survey. Some examples for features are the \textit{shape distributions} \citep{OsadaShapedistributions2002}, that are connected to the distributions of lengths, areas and volumes of an object, the \textit{shape contexts} \citep{BelongieShapematchingobject2002}, that rely in a sense on a local distribution of inter-point distances of the considered object, and \textit{reduced size functions} \citep{dAmicoNaturalpseudodistanceoptimal2008}, which count the connected components of certain lower level sets.\\
As noted by \citet{ MemoliuseGromovHausdorffDistances2007, Memoli2011}, several signatures describe different aspects of a metric between objects.

In these and subsequent papers, the author develops a unifying view point by representing an object as \textit{metric measure space} $\mmspaceX$, where $\left( \mathcal{X},\dX\right)$ is a compact metric space and $\muX$ denotes a Borel probability measure on $\mathcal{X}$. The additional probability measure, whose support is assumed to be $\mathcal{X}$, can be thought of as signaling the importance of different regions of the modeled object. Based on the original work of \citet{gromov1999metric}, \citet{Memoli2011} introduced the \textit{Gromov-Wasserstein distance} of order $p\in[1,\infty)$ between two (compact) metric measure spaces $\mmspaceX$ and $\mmspaceY$ which will be fundamental to this paper. We allow ourselves to rename it to \textit{Gromov-Kantorovich distance} to give credit to Kantorovich's initial work \cite{kantorovich1942translocation} underlying this concept (see \citet{vershik2007lv}). It is defined as	\begin{equation}
{\mathcal{GK}_p}(\mathcal{X},\mathcal{Y})=\inf_{\pi\in\mathcal{M}(\mu_\mathcal{X},\mu_\mathcal{Y})}J_p(\pi),\label{eq:GKdist}\end{equation}
where
\begin{align*}
J_p(\pi)\coloneqq&\frac{1}{2}\left(\int_{\mathcal{X}\times\mathcal{Y}}\int_{\mathcal{X}\times\mathcal{Y}} \! \left|d_\mathcal{X}(x,x')-d_\mathcal{Y}(y,y') \right|^p \,\pi(dx\times dy)\,\pi(dx'\times dy')\right)^{\frac{1}{p}}. \end{align*}
Here, $\mathcal{M}(\mu_\mathcal{X},\mu_\mathcal{Y})$ stands for the set of all couplings of $\mu_\mathcal{X}$ and $\mu_\mathcal{Y}$, i.e., the set of all measures $\pi$ on the product space $\mathcal{X}\times\mathcal{Y}$ such that
\[\pi\left(A\times\mathcal{Y}\right)=\muX\left(A\right)~\mathrm{and}~\pi\left(\mathcal{X}\times B\right)=\muY\left(B\right)\]
for all measurable sets $A\subset\mathcal{X}$ and $B\subset\mathcal{Y}$. In Section 5 of \citet{Memoli2011} it is ensured that the Gromov-Kantorovich distance ${\mathcal{GK}_p}$ is suitable for pose invariant object matching by proving that it is a metric on the collection of all isomorphism classes of metric measure spaces.\footnote{Two metric measure spaces $\mmspaceX$ and $\mmspaceY$ are isomorphic (denoted as $\mmspaceX\cong\mmspaceY$) if and only if there exists an isometry $\phi:\mathcal{X}\to\mathcal{Y}$ such that $\phi\#\mu_\mathcal{X}=\mu_\mathcal{Y}$. Here, $\phi\#\mu_\mathcal{X}$ denotes the pushforward measure.} Hence, objects are considered to be the same if they can be transformed into each other without changing the distances between their points and such that the corresponding measures are preserved. For example, if the distance is Euclidean, this leads to identifying objects up to translations, rotations and reflections \cite{lomont2014applications}.

\noindent The definition of the Gromov-Kantorovich distance extends the \textit{Gromov-Hausdorff distance}, which is a metric between compact metric spaces \cite{MemoliComparingPointClouds2004,MemoliTheoreticalComputationalFramework2005,MemoliuseGromovHausdorffDistances2007}. The additional measure structure of metric measure spaces allows to replace the Hausdorff distance component in the definition of the Gromov-Hausdorff distance by a relaxed notion of proximity, namely the \textit{Kantorovich distance} \citep{kantorovich1942translocation}. This distance is fundamental to a variety of mathematical developments and is also known in different communities as the Wasserstein distance \cite{vaserstein1969markov}, Kantorovich-Rubinstein distance \citep{kantorovich1958space}, Mallows distance \citep{mallows1972note} or as the Earth Mover's distance \citep{rubner2000earth}.
The Kantorovich distance of order $p$ ($p\geq 1$) between two probability measures $\mu_\mathcal{X}$ and $\nu_\mathcal{X}$ on the compact metric space $\left(\mathcal{X},d_\mathcal{X}\right) $ is defined as
\begin{equation}
{\mathcal{K}_p}(\mu_\mathcal{X},\nu_\mathcal{X})=\left\lbrace\inf_{\pi\in\mathcal{M}(\mu_\mathcal{X},\nu_\mathcal{X})}\int_{\mathcal{X}\times\mathcal{X}}\! \,d^p_\mathcal{X}(x,y)\,d\pi(x,y) \right\rbrace^{\frac{1}{p}}, \label{eq:Wasserstein}
\end{equation}
where $\mathcal{M}(\mu_\mathcal{X},\nu_\mathcal{X})$ denotes the set of all
couplings of $\mu_\mathcal{X}$ and $\nu_\mathcal{X}$. Let $\mathcal{P}(\mathcal{X})$ be the space of all probability measures on $\mathcal{X}$. Then, as compact metric spaces are in particular Polish, the Kantorovich distance defines a metric on
\[\mathcal{P}_p\left(\mathcal{X}\right)=\bigg\{\mu\in \mathcal{P}(\mathcal{X})~\bigg|~\int_\mathcal{X}d^p_\mathcal{X}(x_0,x)\,d\mu(x)<\infty,~x_0\in\mathcal{X}~\mathrm{arbitrary}\bigg\} \]
and it metrizes weak convergence together with convergence of moments of order $p$ \citep{villani2008optimal}.

\noindent Due to its measure preserving metric invariance, the Gromov-Kantorovich distance is conceptually well suited for pose invariant object discrimination. Heuristically speaking, the Gromov-Kantorovich point of view suggests to regard a data cloud as a metric measure space by itself, which  takes into account its internal metric structure (encoded in its pairwise distances), and provides a transportation between metric spaces without loss of mass. In particular, it does not rely on the embedding in an external space. For the above described protein comparison problem, the coordinate system in which the atoms are represented does not matter. Hence, the Gromov-Kantorovich distance is only influenced by the internal relations between the backbone atoms - which matches the physical understanding of structural similarity in this context. However, the practical usage of the Gromov-Kantorovich approach is severely hindered by its computational complexity: For two finite metric measure spaces $\mathcal{X}=\left\lbrace x_1,\dots,x_n\right\rbrace$ and $\mathcal{Y}=\left\lbrace y_1,\dots,y_m\right\rbrace$ with metrics $d_\mathcal{X}$ and $d_\mathcal{Y}$ and probability measures $\mu_{\mathcal{X}}$ and $\mu_\mathcal{Y}$, respectively, the computation of ${\mathcal{GK}_p}\left(\mathcal{X},\mathcal{Y}\right)$ boils down to solving a (non-convex) quadratic program \citep[Sec. 7]{Memoli2011}. This is in general NP-hard \citep{pardalos1991quadratic}. To circumvent the precise determination of the Gromov-Kantorovich distance, it has been suggested to approximate it via gradient descent \cite{Memoli2011} or to relax the corresponding optimization problem. For example, \citet{solomon2016entropic} proposed the \textit{entropic Gromov-Kantorovich distance}, which has been applied to find correspondences between word embedding spaces, an important task for machine translation \cite{alvarez2018gromov}. In this paper, we take a different route and investigate the potential of a lower bound for $\mathcal{GK}_p$, which is on the one hand extremely simple to compute in $O(n^2)$ elementary operations and on the other hand statistically accessible and useful for inference tasks, in particular for object discrimination when the data are randomly sampled or the data set is massive and subsampling becomes necessary. As this bound quantifies the optimal transport distance between the \textit{distributions of pairwise distances} (see \Cref{subsec:proposed approach}), we believe that our analysis is of quite general statistical interest beyond the described scenario.
\subsection{The Proposed Approach}\label{subsec:proposed approach}
Given two metric measure spaces, denoted as $\mmspaceX$ and $\mmspaceY$, we aim to construct an (asymptotic) test for the hypothesis that these spaces are isomorphic, viz.
\begin{align}H_0:~\mmspaceX\cong\mmspaceY,\label{eq:nullhypothesis}
\end{align}
against the alternative
\begin{align}\label{eq:alternative}H_1:~\mmspaceX\ncong\mmspaceY.
\end{align}
This test will be based on an efficiently computable empirical version of a lower bound of the Gromov-Kantorovich distance.

\noindent Let $\muU$ be the probability measure of the random variable $d_{\mathcal{X}}(X,X')$, where $X,X'\overset{i.i.d.}{\sim}\mu_\mathcal{X}$, and let $\mu^V$ be the one of $d_{\mathcal{Y}}(Y,Y')$, with $Y,Y'\overset{i.i.d.}{\sim}\mu_\mathcal{Y}$. Then, we call $\muU$ and $\mu^V$ the \textit{distribution of the (pairwise) distances} of $\mmspaceX$ and $\mmspaceY$, respectively. Fundamental to our approach is the fact that the Gromov-Kantorovich distance between two metric measure spaces $\mmspaceX$ and $\mmspaceY$ of order $p\in[1,\infty)$ is lower bounded by
\begin{equation}
{\mathcal{GK}_p}(\mathcal{X}, \mathcal{Y})\geq\frac{1}{2}\!\left(\ptruedodstat\left(\mathcal{X},\mathcal{Y}\right)\right)^{\frac{1}{p}} \coloneqq\frac{1}{2}\left(\int_{0}^{1}\!\left| U^{-1}(t)-V^{-1}(t)\right| ^p dt \right)^{\frac{1}{p}}\label{eq:introlowerbound},
\end{equation}
where $U^{-1}$ and $V^{-1}$ are the quantile functions of $\muU$ and $\mu^V$, respectively \cite{Memoli2011}. If the right hand side of \eqref{eq:introlowerbound} is positive, so is ${\mathcal{GK}_p}$ and it is thus possible to base a statistical test for $H_0$ on an empirical version of this quantity. Furthermore, the above lower bound possesses several theoretical and practical features that make it worthy of study:

\noindent 1.) Reformulating \eqref{eq:introlowerbound} yields that the Gromov-Kantorovich distance between two metric measure spaces is lower bounded by the Kantorovich distance of the respective distributions of distances (one dimensional quantities), i.e.,
\[\ptruedodstat(\X,\Y)=\mathcal{K}_p^p\left(\muU,\mu^V\right)=\inf_{\pi\in\mathcal{M}\left(\muU,\mu^V\right)}\int_{\mathbb{R}\times\mathbb{R}}\! \,|x-y|^p\,d\pi(x,y). \]
Interestingly, there is another reformulation of $\ptruedodstat$ in terms of an optimal transport problem between the product measures $\muX\otimes\muX$ and $\muY\otimes\muY$. It is shown in \cite[Thm. 24]{chowdhury2019gromov} that
\begin{equation}\label{eq:SLB OT-form}
\ptruedodstat\left(\mathcal{X},\mathcal{Y}\right)\!=\!\inf_{\pi\in\widetilde{\mathcal{M}}}\,\int_{\X\times\X\times\Y\times\Y}\left|\dX(x,x')-\dY(y,y') \right|^pd\pi(x,x'y,y'),\end{equation}
where $\widetilde{\mathcal{M}}\coloneqq\mathcal{M}(\mu_\mathcal{X}\otimes\mu_\mathcal{X},\mu_\mathcal{Y}\otimes\muY)$.

This representation emphasizes the relation between $\ptruedodstat$ and the Gromov-Kantorovich distance defined in \eqref{eq:GKdist}, as clearly $\pi\otimes\pi\in\widetilde{\mathcal{M}}$ for all $\pi\in\mathcal{M}(\muX,\muY)$.

\noindent 2.) Although it is known that the distribution of distances does not uniquely characterize a metric measure space \cite{Memoli2011}, it was proposed as a feature itself for feature based object matching and was shown to work well in practice in various examples \cite{OsadaShapedistributions2002,brinkman2012invariant,berrendero2016shape,gellert2019substrate}. In fact, \citet{gellert2019substrate} applied several lower bounds of the Gromov-Kantorovich distance stated in \cite{Memoli2011} for the comparison of the isosurfaces of various proteins. The authors empirically found that $\ptruedodstat$ defined in \eqref{eq:introlowerbound} has high discriminative abilities for this task.

\noindent 3.) Generally, $\ptruedodstat$ is a simple and natural measure to compare distance matrices. Such distance matrices underlie many methods of data analysis, e.g. various multidimensional scaling techniques (see \citet{dokmanic2015euclidean}).

\noindent 4.) The representation \eqref{eq:introlowerbound} admits an empirical version which is computable in effectively $O\left((m\vee n)^2\right)$ operations, if the computation of one distance is considered as $O(1)$. To this end, let $X_1,\dots,X_n\overset{i.i.d.}{\sim}\mu_\mathcal{X}$ and $Y_1,\dots,Y_m\overset{i.i.d.}{\sim}\mu_\mathcal{Y}$ be two independent samples and let $\mathcal{X}_n=\left\lbrace X_1,\dots,X_n\right\rbrace $ and $\mathcal{Y}_m=\left\lbrace Y_1,\dots,Y_m\right\rbrace $. The sample analog to \eqref{eq:introlowerbound} is to be defined with respect to the empirical measures and we obtain as empirical counterpart to \eqref{eq:introlowerbound} the \textit{DoD-statistic} as
\begin{equation}
 \untruncateddodstat_p=\untruncateddodstat_{p}\left(\mathcal{X}_n,\mathcal{Y}_m\right) \coloneqq\int_{0}^{1}\!\left| U^{-1}_n(t)-V^{-1}_{m}(t)\right| ^p \, dt \label{eq:introlowerboundempversion},\end{equation}
where, for $t\in\R$, $U_n$ is defined as the empirical c.d.f. of all pairwise distances of the sample $\X_{n}$,
\begin{equation}\label{eq:def of U_n}U_n(t)\coloneqq\frac{2}{n(n-1)}\sum_{1\leq i<j\leq n}\mathds{1}_{\left\lbrace d_\mathcal{X}(X_i,X_j)\leq t\right\rbrace }.\end{equation}
Analogously, we define for the sample $\Y_n$
\begin{equation}\label{eq:def of V_m}V_m(t)\coloneqq\frac{2}{m(m-1)}\sum_{1\leq k<l\leq m}\mathds{1}_{\left\lbrace d_\mathcal{Y}(Y_k,Y_l)\leq t\right\rbrace }.\end{equation}
Besides, $U^{-1}_n$ and $V^{-1}_m$ denote the corresponding empirical quantile functions. We stress that the evaluation of $\untruncateddodstat_p$ boils down to the calculation of a sum and no formal integration is required. For $n=m$ it holds
\[\untruncateddodstat_p=\frac{2}{n(n-1)}\sum_{i=1}^{n(n-1)/2}\left|d^\X_{(i)}-d^\Y_{(i)} \right|^p ,\]
 where $ d^\X_{(i)}$ denotes the $i$-th order statistic of the sample $\left\lbrace\dX(X_i,X_j) \right\rbrace_{1\leq i < j\leq n} $ and $d^\Y_{(i)}$ is defined analogously. For $n\neq m$ we obtain that
\[\untruncateddodstat_p=\sum_{i=1}^{\frac{n(n-1)}{2}}\sum_{j=1}^{\frac{m(m-1)}{2}}\lambda_{ij}\left|d^\X_{(i)}-d^\Y_{(j)} \right|^p ,\]
 where
 \[\lambda_{ij}=\left( \frac{i}{n}\wedge\frac{j}{m}-\frac{i-1}{n}\vee\frac{j-1}{m}\right)\indifunc{{i}{m}\wedge{j}{n}>{(i-1)}{m}\vee{(j-1)}{n}}. \]
 Here, and in the following, $a\wedge b$ denotes the minimum and $a\vee b$ the maximum of two real numbers $a$ and $b$.

\subsection{Main Results}\label{subsec:main results}
The main contributions of the paper are various upper bounds and distributional limits for the statistic defined in \eqref{eq:introlowerboundempversion} (as well as trimmed variants). Based on these, we design an asymptotic test that compares two distributions of distances and thus obtain an asymptotic test for the hypothesis $H_0$ defined in \eqref{eq:nullhypothesis}. In the course of this, we focus, for ease of notation, on the case $p=2$, i.e., we derive for $\beta\in[0,1/2)$ the limit behavior of the statistic
\[\dodstat\coloneqq\int_{\beta}^{1-\beta}\!\left(U_n^{-1}(t)-V_m^{-1}(t)\right)^2 \, dt\]
under the hypothesis \eqref{eq:nullhypothesis} as well as under the alternative in \eqref{eq:alternative}. The introduced trimming parameter $\beta$ can be used to robustify the proposed method \cite{czado1998assessing,alvarez2008trimmed}. Most of our findings can easily be transferred to the case of $p\in[1,\infty)$, which is readdressed in \Cref{subsec:secondcase}. Next, we briefly summarize the setting in which we are working and introduce the conditions required.
\begin{set}\label{cond:setting}
	Let $\mmspaceX$ and $\mmspaceY$ be two metric measure spaces and let $\mu^U$ and $\mu^V$ denote the distributions of (pairwise) distances of the spaces $\mmspaceX$ and $\mmspaceY$, respectively. Let $U$ denote the c.d.f. of $\mu^U$, assume that $U$ is differentiable with derivative $u$ and let $U^{-1}$ be the quantile function of $U$. Let $V$, $V^{-1}$ and $v$ be defined analogously. Further, let the samples $X_1,\dots,X_n\iid \muX$ and $Y_1,\dots,Y_m\iid \muY$ be independent of each other and let $U^{-1}_n$ and $V^{-1}_m$ denote the empirical quantile functions of $U_n$ defined in \eqref{eq:def of U_n} and $V_m$ defined in \eqref{eq:def of V_m}.
\end{set}
Since the statistic $\dodstat$ is based on empirical quantile functions, or more precisely empirical $U$-quantile functions, we have to ensure that the corresponding $U$-distribution functions are well-behaved. In the course of this, we distinguish the cases $\beta\in(0,1/2)$ and $\beta=0$. The subsequent condition guarantees that the inversion functional $\phi_{inv}:F\mapsto F^{-1}$ is Hadamard differentiable as a map from the set of restricted distribution functions into the space of all bounded functions on $[\beta,1-\beta]$, in the following denoted as $\ell^\infty[\beta,1-\beta]$.
\begin{cond}\label{cond:firstcondition} Let $\beta\in(0,1/2)$ and let $U$ be continuously differentiable on an interval \[[C_1,C_2]=[U^{-1}(\beta)-\epsilon,U^{-1}(1-\beta)+\epsilon]\] for some $\epsilon>0$ with strictly positive derivative $u$ and let the analogue assumption hold for $V$ and its derivative $v$.
\end{cond}
When the densities of $\muU$ and $\mu^V$ vanish at the boundaries of their support, which commonly happens (see \Cref{ex:dod3}), we can no longer rely on Hadamard differentiability to derive the limit distribution of $\dodstat$ under $H_0$ for $\beta=0$. In order to deal with this case we require stronger assumptions. The following ones resemble those of \citet{mason1984weak}.
\begin{cond}\label{cond:secondcondition} Let $U$ be continuously differentiable on its support. Further, assume there exist constants $-1<\gamma_1,\gamma_2<\infty$ and $c_U>0$ such that
	\[\left| (U^{-1})'(t)\right| \leq c_Ut^{\gamma_1}(1-t)^{\gamma_2}\]
	for $t\in(0,1)$ and let the analogue assumptions hold for $V$ and $(V^{-1})'$.
\end{cond}
Both, \Cref{cond:firstcondition} and \Cref{cond:secondcondition} are comprehensively discussed in \Cref{subsec:conditions} and various illustrative examples are given there.

\noindent With the main assumptions stated we can now specify the results derived under the hypothesis $H_0$ and afterwards those under the alternative $H_1$.
Under $H_0$ we have that the distributions of distances of the considered metric measure spaces, $\muU$ and $\mu^V$, are equal, i.e., $U(t)=V(t)$ for $t\in\R$. Given \Cref{cond:firstcondition} we find that for $\beta\in(0,1/2)$ (resp. given \Cref{cond:secondcondition} for $\beta=0$) and $n,m\to\infty$
\begin{align}
\frac{nm}{n+m}\dodstat\rightsquigarrow\Xi=\Xi(\beta) \coloneqq\int_{\beta}^{1-\beta}\!\left(\mathbb{G}(t)\right) ^2 \, dt,\label{eq:defofXi}
\end{align}
where $\mathbb{G}$ is a centered Gaussian process with covariance depending on $U$ (under $H_0$ we have $U=V$) in an explicit but complicated way, see \Cref{thm:main2}.
Further, ``$\rightsquigarrow$'' denotes weak convergence in the sense of Hoffman-J{\o}rgensen (see \citet[Part 1]{vaartWeakConvergenceEmpirical1996}).

Additionally, we establish in \Cref{sec:Limit distribution} a simple concentration bound for $\dodstat$

and demonstrate that for $\beta\in(0,1/2)$ and $\alpha\in(0,1)$ the corresponding $\alpha$-quantile of $\Xi$, which is required for testing, can be obtained by a bootstrap scheme, see \Cref{sec:bootsrapping the quantiles}.

\noindent Next, we summarize our findings under $H_1$. As we work with a lower bound, the limit behavior under the alternative is a little more complex.

Under the additional assumption that \[\truetruncateddod\coloneqq\int_{\beta}^{1-\beta}\!\left(U^{-1}(t)-V^{-1}(t)\right)^2 \, dt > 0,\] we can prove (cf. \Cref{thm:main}) that given \Cref{cond:firstcondition} it holds for $n,m\to\infty$ and $\beta\in(0,1/2)$ (resp. given \Cref{cond:secondcondition} for $\beta=0$) that
\begin{equation}\sqrt{\frac{nm}{n+m}}\left(\dodstat-\truetruncateddod \right)\rightsquigarrow N(0,\sigma_{U,V,\lambda}^2),\label{eq:statement2}\end{equation}
where $N(0,\sigma_{U,V,\lambda}^2)$ denotes a normal distribution with mean 0 and variance $\sigma_{U,V,\lambda}^2$ depending on $U$, $V$, $\beta$ and $\lambda=\lim_{n,m\to\infty}\frac{n}{m+n}$.

\subsection{Applications}\label{subsec:applications}
From our theory it follows that for $\beta\in[0,1/2)$ a (robust) asymptotic level-$\alpha$-test for $H_0$ against $H_1$ is given by rejecting $H_0$ in \eqref{eq:nullhypothesis} if
\begin{equation}\label{eq:decision rule}
	\frac{nm}{n+m}\dodstat> \xi_{1-\alpha},
\end{equation}
where $\xi_{1-\alpha}$ denotes the $(1-\alpha)$-quantile of $\Xi$. The simulations in \Cref{sec:simulations} demonstrate that, although it is based on a lower bound of the Gromov-Kantorovich distance $\mathcal{GK}_p$ between the metric measure spaces, the proposed test (as well as its bootstrap version) represents a powerful method to detect deviations between metric measure spaces in the sense of \eqref{eq:nullhypothesis}. This has many possible applications.

\begin{figure}
	\centering
	\begin{subfigure}[c]{0.49\textwidth}
			\centering
		\includegraphics[ height=0.8\textwidth,trim=.01cm .01cm .01cm .01cm, clip]{Graphics/5d0uvs5jpt.png}
	\end{subfigure}
	\begin{subfigure}[c]{0.49\textwidth}
			\centering
		\includegraphics[ height=0.8\textwidth,trim=.01cm .01cm .01cm .01cm, clip]{Graphics/5d0uvs6faa.png}
	\end{subfigure}
	\caption{\textbf{Illustration of the proteins to be compared:} Cartoon representation of the DEAH-box RNA-helicase Prp43 from chaetomium thermophilum bound to ADP (purple, PDB ID: 5D0U \cite{tauchert2016structural}) in alignment with Prp43 from saccharomyces cerevisiae in complex with CDP (cyan, PDB ID: 5JPT \cite{robert2016functional}, left) and in alignment with the DEAH-box RNA helicase Prp2 in complex with ADP (orange, PDB ID: 6FAA \cite{schmitt2018crystal}, right). Prp2 is closely related to Prp43 and is necessary for the catalytic activation of the spliceosome in pre-mRNA splicing \cite{kim1996spliceosome}.}
	\label{fig: protein visiualization}
\end{figure}
\noindent

Exemplarily, in \Cref{sec:application}, we model proteins as such metric measure spaces by assuming that the coordinate files are samples from (unknown) distributions (see \cite{rhodes2010crystallography}) and apply the theory developed to compare the protein structures depicted in \Cref{fig: protein visiualization}. Our major findings can be summarized as follows:

\noindent\textbf{5D0U vs 5JPT:} 5D0U and 5JPT are two structures of the same protein extracted from different organisms. Consequently, their secondary structure elements can almost be aligned perfectly (see \Cref{fig: protein visiualization}, left). Only small parts of the structures are slightly shifted and do not overlap in the alignment. Applying \eqref{eq:decision rule} for this comparison generally yields no discrimination between these two protein structures, as $\truetruncateddod$ is robust with respect to these kinds of differences. This robustness indeed makes the proposed method particularly suitable for protein structure comparison.

\noindent\textbf{5D0U vs 6FAA:} 5D0U and 6FAA are structures from closely related proteins and thus they are rather similar. Their alignment (\Cref{fig: protein visiualization}, right) shows minor differences in the orientation of some secondary structure elements and that 5D0U contains an $\alpha$-helix that is not present in 6FAA. We find that $\truetruncateddod$ is highly sensitive to such a deviation from $H_0$, as the proposed procedure discriminates very well between both structures already for small sample sizes.

\noindent Besides of testing, we mention that our theory also justifies subsampling (possibly in combination with bootstrapping) as an effective scheme to reduce the computational costs of $O\left((m\vee n)^2\right)$ further to evaluate $\dodstat$ for large scale applications.
\subsection{Related Work}
 First, we note that $U_n$ and $V_m$ can be viewed as empirical c.d.f.'s of the $N\coloneqq n(n-1)/2$ and $M\coloneqq m(m-1)/2$ random variables $d_\mathcal{X}(X_i,X_j)$ , $1\leq i<j\leq n$, and $d_\mathcal{Y}(Y_k,Y_l)$, $1\leq k<l\leq m$, respectively. Hence, \eqref{eq:introlowerboundempversion} can be viewed as the one dimensional empirical Kantorovich distance with $N$ and $M$ data, respectively. There is a long standing interest in distributional limits for the one dimensional empirical Kantorovich distance \citep{MunkNonparametricvalidationsimilar1998,BarrioTestsgoodnessfit1999,BarrioAsymptoticsL2functionals2005, bobkov2016one,sommerfeld2018inference,tameling2019empirical} as well as for empirical Kantorovich type distances with more general cost functions \cite{berthet2017central, berthet2019weak}. Apparently, the major difficulty in our setting arises from the dependency of the random variables $\{\dX(X_i,X_j)\}$ and the random variables $\{\dY(Y_k,Y_l)\}$, respectively.

 Compared to the techniques available for stationary and $\alpha$-dependent sequences \cite{dede2009empirical,dedecker2017behavior}, the statistic $\dodstat$ admits an intrinsic structure related to $U$- and $U$-quantile processes \cite{NolanProcessesRatesConvergence1987,nolan1988functional,arcones1993limit,arcones1994u,wendler2012u}.
 Note that for $\beta>0$ we could have used the results of \citet{wendler2012u} to derive the asymptotics of $\dodstat$ as well, as they provide almost sure approximations of the empirical $U$-quantile processes $\mathbb{U}_n^{-1}\coloneqq\sqrt{n}\left(U_n^{-1}-U^{-1}\right)$ and $\mathbb{V}_m^{-1}\coloneqq\sqrt{m}\left(V_m^{-1}-V^{-1}\right)$ in $\ell^\infty[\beta,1-\beta]$, however at the expense of slightly stronger smoothness requirements on $U$ and $V$. In contrast, the case $\beta=0$ is much more involved as the processes $\mathbb{U}_n^{-1}$ and $\mathbb{V}_m^{-1}$ do in general not converge in $\ell^\infty(0,1)$ under \Cref{cond:secondcondition} and the technique in \cite{wendler2012u} fails. Under the hypothesis, we circumvent this difficulty by targeting our statistic for $\beta=0$ directly, viewed as a process indexed in $\beta$. Under the alternative, we show the Hadamard differentiability of the inversion functional $\phi_{inv}$ onto the space $\ell^1(0,1)$ and verify that this is sufficient to derive \eqref{eq:statement2}.\\

 Notice that tests based on distance matrices appear naturally in several applications, see, e.g., the recent works \cite{baringhaus2004new,sejdinovic2013equivalence,montero2019two}, where the two sample homogeneity problem, i.e., testing whether two probability measures $\mu,\nu\in\mathcal{P}(\R^d)$ are equal, is considered for high dimensions. Most similar in spirit to our work is \citet{brecheteau2019statistical} who also considers an asymptotic statistical test for the hypothesis defined in \eqref{eq:nullhypothesis}. However, the latter method is based on a nearest neighbor-type approach and subsampling, which relates to a different lower bound of the Gromov-Kantorovich distance. Moreover, the subsampling scheme is such that asymptotically all distances considered are independent, while we explicitly deal with the dependency structures present in the entire sample of the $n(n-1)/2$ distances. In \Cref{subsec:bootstrap test} and \Cref{subsec:comparisontoBrecheteau} we empirically demonstrate that this leads to an increase of power and compare our test with the one proposed by \citet{brecheteau2019statistical} in more detail.

 \noindent Due to its exponential computational complexity the practical potential of the Gromov-Kantorovich distance has rarely been explored. Notable exceptions are very recent. We mention  \citet{liebscher2018new}, who suggested a poly-time algorithm for a Gromov-Hausdorff type metric on the space of phylogenetic trees, \citet{chowdhury2019gromovaveraging}, who applied the Gromov-Kantorovich distance to develop new tools for network analysis, and \citet{gellert2019substrate}, who used and empirically compared several lower bounds for the Gromov-Kantorovich distance for clustering of various redoxins, including our lower bound in \eqref{eq:introlowerbound}. In fact, to reduce the computational complexity they employed a bootstrap scheme related to the one investigated in this paper and reported empirically good results. Finally, we mention that permutation based testing for $U$-statistics (see e.g. \citet{berrett2020optimal}) is an interesting alternative to our bootstrap test and worth to be investigated further in our context.

\subsection{Organization of the Paper}
\Cref{sec:Limit distribution} states the main results and is concerned with the derivation of \eqref{eq:defofXi}, a simple finite sample bound for the expectation of $\dodstat$ as well as the proof of \eqref{eq:statement2}. In \Cref{sec:bootsrapping the quantiles} we propose for $\beta\in(0,1/2)$ a bootstrapping scheme to approximate the quantiles of $\Xi$ defined in \eqref{eq:defofXi}. Afterwards in \Cref{sec:simulations} we investigate the speed of convergence of $\dodstat$ to its limit distribution under $H_0$ as well as its behavior under the alternative in a Monte Carlo study. In this section we further study the introduced bootstrap approximation and investigate what kind of differences are detectable employing $\dodstat$ by means of various examples. We apply the proposed test for the discrimination of 3-D protein structures in \Cref{sec:application} and compare our results to the ones obtained by the method of \citet{brecheteau2019statistical}. Our simulations and data analysis of the example introduced previously (see \Cref{fig: protein visiualization}) suggest that the proposed $\dodstat$ based test
 outperforms the one proposed by \citet{brecheteau2019statistical} for protein structure comparisons.\\
As the proofs of our main results are quite technical and involved, the key ideas are stated in \Cref{appendix:proofs} and the full proofs are given in Part I of the supplement \cite{supplement}. Part II of the supplement \cite{supplement} contains several technical auxiliary results that seem to be folklore, but have not been written down explicitly in the literature, to the best of our knowledge.

\textbf{Notation} Throughout this paper, $\borelsetsR$ denotes the Borel sets on $\R$ and ``$\Rightarrow$'' stands for the classical weak convergence of measures (see \citet{billingsley2008probability}). Let $T$ be an arbitrary set. Then, the space $\ell^\infty(T)$ denotes the usual space of all uniformly bounded, $\R$-valued functions on $T$ and $\ell^p(T)$, $p\in[1,\infty)$, the space of all $p$-integrable, $\R$-valued functions on $T$. Given an interval $[a,b]$, let $D[a,b]$ be the c\`{a}dl\`{a}g functions on $[a,b]$ (see \citet{BillingsleyConvergenceProbabilityMeasures2013}) and $\mathbb{D}_2\subset D[a,b]$ the set of distribution functions of measures concentrated on $(a,b]$.


text:
The Gaussian free field is a generalization of Brownian motion
where the indexing set has dimension greater than one.
Physicists have long been interested in the GFF because of its importance
in quantum field theory. Mathematicians have come to the GFF more recently,
as it it became clear that it was the limit of a variety
of discrete random surfaces and height functions
\cite{NS,GOS,Kenyon1,RV,Kenyon2,BorFer,JLS,Bor1,Kuan,Duits,Petrov}
and was closely related to Schramm-Loewner evolution
\cite{Dubedat,SS1,SS2,MS1,MS2,MS3,MS4}.

At its most basic level, the GFF on the upper half-plane
with zero Dirichlet boundary conditions
can be thought of as a centered Gaussian field $(h(z),\,z\in\HH)$ with covariances given by
\begin{align*}
  \E \bigl[ h(z) h(w) \bigr] = -\frac{1}{2\pi}\log\biggl\lvert\frac{z-w}{z-\overline{w}}\biggr\rvert.
\end{align*}
The problem with this definition is that no such random function $h$ exists.
If it did exist, then the collection of random variables
$\int_{\HH} f(z) h(z)\,dz$ indexed by smooth
compactly supported functions $f$ would also be a Gaussian field.
This field does truly exist, and we will use it to define
the GFF.

We start by giving a bare-bones treatment of the GFF that gives only the very few
properties we need. After this, we give a more languorous account based on
\cite{Sheffield}, \cite{HMP}, and \cite{Dubedat}.

\subsection{Bare-bones background on the Gaussian free field}
\label{sec:GFFbackground1}
Let $h$ denote the GFF on $\HH$ (with zero Dirichlet boundary conditions, the only kind
we will consider).
The only property we use in this thesis is that
if $f(z)$ is a smooth function defined on a smooth path~$\gamma$ satisfying
\eqref{eq:finitepath}, one can define a collection of random variables denoted
$\int_\gamma f(z)h(z)\,dz$ that form a centered Gaussian field.
(Again, $h$ is not really a function, and we are not really integrating against it.
The notation is from \cite{Bor1}, \cite{BG}, and other papers. In Section~\ref{sec:GFFbackground2}, we explain
the real definitions.)
The covariances are given by the following proposition:
\begin{prop}[{\cite[Lemma~4.6]{BG}}]\thlabel{prop:BG2}
  Let $f_1,f_2$ be smooth functions defined on the image of a smooth curve~$\gamma$ such that
  \begin{align}
    \int_\gamma\int_\gamma f_i(z)\biggl(-\frac{1}{2\pi}\log\Bigl\lvert\frac{z-w}{z-\overline{w}}
      \Bigr\rvert\biggr)f_i(w)\,dz\,dw < \infty\label{eq:finitepath}
  \end{align}
  for $i=1,2$.
  Then
  \begin{align*}
    \E\biggl[\biggl(\int_{\gamma}f_1(z)h(z)\,dz\biggr)\biggl(\int_{\gamma}f_2(z)h(z)\,dz\biggr)\biggr]
      &=\int_{\gamma}\int_{\gamma}f_1(z)\biggl(-\frac{1}{2\pi}\log\Bigl\lvert\frac{z-w}{z-\overline{w}}
      \Bigr\rvert\biggr)f_2(w)\,dz\,dw.
  \end{align*}
\end{prop}

\subsection{More background on the Gaussian free field}
\label{sec:GFFbackground2}
We will build up the GFF from scratch, mostly following \cite{Sheffield} with a sprinkling
of \cite{HMP} and \cite{Dubedat}.
Our goal will be to present it in as simply as possible and explain how it meshes
with the more concrete information from the previous section.
To make this account friendlier without bogging it down too much, we present background material
on partial differential equations and Sobolev spaces in italics.
For a proper introduction, see \cite{Evans}, \cite{Hunter}, and \cite{Brezis}.

\newenvironment{pde}{\par\noindent\begin{adjustwidth}{2.5em}{}\textit\bgroup\small\ignorespaces}{\egroup\end{adjustwidth}}
\newcommand{\grad}{\nabla}
\newcommand{\Hloc}{H_{\text{loc}}}
\newcommand{\laplace}{\Delta}
\renewcommand{\ip}[1]{\langle #1 \rangle}
\newcommand{\ipd}[1]{\langle #1 \rangle_\grad}
\newcommand{\norm}[1]{\lVert #1 \rVert}
\newcommand{\normd}[1]{\lVert #1 \rVert_\grad}
{\renewcommand{\H}{H}
\subsubsection{Definition and construction of the Gaussian free field}
Let $D\subset\RR^d$ be a domain (that is, a connected open set).
We define $H_s(D)$ as the space of all smooth, compactly supported, real-valued functions
on $D$, and we endow this space with the \emph{Dirichlet inner product}, given by
$\ipd{f,g}=\int_D\grad f(x)\cdot\grad g(x)\,dx$.
When $d=2$, this inner product is conformally invariant, meaning
that $\ipd{f\circ\varphi,g\circ\varphi}=\ipd{f,g}$ for any conformal map $\varphi$.
We denote the Hilbert space closure of $H_s(D)$ by $\H(D)$.
When $D$ is bounded, $H(D)$ is the subspace $H^1_0(D)$
of the Sobolev space $H^1(D)=W^{1,2}(D)$.
\begin{pde}
The Sobolev space $H^1(D)$ is a Hilbert space consisting of all functions
in $L^2(D)$ whose (weak or distributional) first-order derivatives are also in $L^2$.
When $D$ is bounded,
the Dirichlet inner product on $H_s(D)$ gives a norm equivalent to the standard one in $H^1(D)$
by the Poincar\'e inequality \cite[Section~5.6.1, Theorem~3]{Evans}.
The Hilbert space completion of $H_s(D)$ is then the closure of $C_c^{\infty}(D)$
in $H^1(D)$, with an inner product equivalent to the usual Sobolev one.
This closure is denoted as $H^{1}_0(D)$, and it consists of the elements
of $H^1(D)$ that are zero on the boundary in the sense of traces \cite[Section~5.5]{Evans}.

\noindent
When $D$ is unbounded, the situation is slightly messier, but we need to address it so that
we can talk about the GFF on regions like the upper half-plane.
To take advantage of the conformal invariance of the Dirichlet inner product,
we will assume that $D$ is an unbounded domain in $\RR^2$ that admits a conformal map
$\varphi$ onto a bounded domain $D'$.
The space $\Hloc^1(D)$ consists of all functions on $D$ whose restrictions belong to $H^1(U)$
for all open sets $U$
with compact closure in $D$. A sequence converges in $\Hloc^1(D)$ if its restrictions
converge in $H^1(U)$ for all such $U$, which makes this a Fr\'echet space.
We will show that $H(D)\subset\Hloc^1(D)$.

\noindent
Suppose that $f_n$ forms a Cauchy sequence in $H_s(D)$.
Then $f_n\circ\varphi^{-1}$ is a Cauchy sequence in $H_s(D')$, and it converges
to a limit $g\in H^1_0(D')$. Let $f=g\circ\varphi$.
By the local invariance of Sobolev spaces under smooth
coordinate changes, $f\in\Hloc^1(D)$ and $f_n\to f$ in that space
\cite[Theorem~6.24, Corollary~6.25]{FolPDE}. By conformal invariance,
$f_n\to f$ in the Dirichlet inner product. Thus $H(D)\subset\Hloc^1(D)$.
In particular, elements of $H(D)$ are locally $L^2$-integrable.
\end{pde}
Note that by integration by parts,
the Dirichlet inner product on $H_s(D)$ can be expressed in terms of the usual
inner product in $L^2$ by
\begin{align}
  \ipd{f,g} = \ip{f,-\laplace g}. \label{eq:ips}
\end{align}

Suppose we have a probability space $(\Omega, \Ff, P)$.
A closed subspace of $L^2(\Omega, \Ff, P)$ consisting
of centered Gaussian random variables is called
a \emph{Gaussian Hilbert space}.
We will assume throughout that $\Ff$ is the $\sigma$-algebra
generated by these random variables.
A trivial example of a Gaussian Hilbert space is the one-dimensional space
$\{t\xi,\, t\in\RR\}$, where $\xi$ is a centered Gaussian.
A non-trivial one is the closed linear span of the collection of random
variables $\{B_t,\,t\geq 0\}$, where $B_t$ is a standard Brownian motion.
The definition and both examples can be found in much more detail in
\cite{JanGH}.

We are now ready to define the GFF, though it will take some work afterwards
to make sense of it. In the following definition, $h$ has no meaning on its own.
For each $f\in \H(D)$, the notation $\ipd{h,f}$ indicates a random variable,
with no assumptions at all on the map $f\mapsto\ip{h,f}$.
\begin{definition}\thlabel{def:GFF}
  The Gaussian free field on a domain $D$ (with zero Dirichlet boundary conditions)
  is the Gaussian Hilbert space of random variables
  $\bigl\{\ipd{h, f},\,f\in \H(D)\bigr\}$ with covariances given by
  \begin{align}
    \E\bigl[ \ipd{h,f}\ipd{h,g}\bigr] = \ipd{f,g}.\label{eq:ippreserving}
  \end{align}
\end{definition}
The notation $\ipd{h,f}$ suggests that the map $f\mapsto\ipd{h,f}$ should be linear,
and this definition implies that it is: By applying \eqref{eq:ippreserving}, we can show
 that the variance of $\ipd{h,af+bg}-\bigl(a\ipd{h,f}+b\ipd{h,g}\bigr)$ is zero.

By the monotone class lemma, the law of $\bigl\{\ipd{h, f},\,f\in \H(D)\bigr\}$ is determined by
the finite-dimensional distributions; see \cite[Example~A.3]{JanGH}.
This is where we use the assumption that the $\sigma$-algebra associated with a Gaussian Hilbert
space is the smallest one that makes $\ipd{h,f}$ measurable for all $f\in \H(D)$.
Thus the definition
determines at most one family $\{\ipd{h,f},\,f\in \H(D)\}$ in law.
It is not clear, however, that there even exists such a Gaussian Hilbert space at all.
We resolve this by constructing one:
\begin{prop}\thlabel{prop:GFFexists}
  There exists a Gaussian Hilbert space satisfying \thref{def:GFF}.
\end{prop}
\begin{proof}
  Let $\{f_i,\,i\in\NN\}$ be an ordered orthonormal basis for $\H(D)$ (this space
   is separable and hence has a countable orthonormal
  basis). Let $\{\alpha_i,\,i\in\NN\}$ be independent standard Gaussians.
  For any $f\in \H(D)$ with expansion $f=\sum\beta_i f_i$, we define
  \begin{align}
    \ipd{h,f} = \lim_{k\to\infty}\sum_{i=1}^{k} \beta_i\alpha_i.\label{eq:hfdef}
  \end{align}
  The sum is a martingale bounded in $L^2$ by Parseval's equality and hence converges~a.s.\
  and in $L^2$.
  Note that it was necessary to fix an order for the sum, as the sequence need not be absolutely
  summable.
  Thus we have constructed a Gaussian field $\bigl\{\ipd{h,f},\,f\in \H(D)\bigr\}$.
  If $f=\sum\beta_if_i$ and $g=\sum\gamma_if_i$, then it follows from the $L^2$ convergence
  of \eqref{eq:hfdef} that
  \begin{align*}
    \lim_{n\to\infty}\E\biggl[\biggl(\sum_{i=1}^n \beta_i \alpha_i\biggr)
  \biggl(\sum_{i=1}^n \gamma_i \alpha_i\biggr)\biggr]=
    \E\bigl[ \ipd{h,f}\ipd{h,g}\bigr]
  \end{align*}
  Thus
  \begin{align*}
    \E\bigl[ \ipd{h,f}\ipd{h,g}\bigr]
     &= \sum_{i=1}^{\infty}\beta_i\gamma_i = \ipd{f,g}
  \end{align*}
  as desired.
\end{proof}

\subsubsection{An example}
We have defined and constructed the GFF without developing much of an intuition for it.
We show now that the GFF on $D=(0,\infty)$ is Brownian motion.
More precisely, let $B_t$ be a standard Brownian motion and define
$\ip{h, f}=\int_0^{\infty} f(t)B_t\,dt$
for $f\in H_s(D)$.
Then define $\ipd{h,f}=-\ip{h, f''}$ in analogy with \eqref{eq:ips}.
We confirm that this (or rather, its extension to all $f\in\H(D)$)
is the GFF according to \thref{def:GFF}.
For $f,g\in H_s(D)$,
\begin{align*}
  \E\bigl[\ipd{h,f}\ipd{h,g}\bigr] &=
    \E \int_0^{\infty}\int_0^{\infty} B_t f''(t)B_u g''(u)\,du\,dt\\
    &= \int_0^{\infty}\int_0^{\infty}f''(t)g''(u)\min(u,t)\,du\,dt\\
    &= \int_0^{\infty}\biggl( f''(t)\int_0^tug''(u)\,du
      + tf''(t)\int_t^{\infty}g''(u)\,du\biggr)dt\\
    &= \int_0^{\infty} \Bigl(f''(t)\bigl(tg'(t)-g(t)\bigr) - f''(t)tg'(t)\Bigr)dt\\
    &= -\int_0^{\infty}f''(t)g(t) = \ipd{f,g}.
\end{align*}

\subsubsection{Green's functions and an alternate form of the GFF}

The GFF can be written in an alternate form inspired by \eqref{eq:ips}.
Let $H(D)^*$ denote the dual space of $H(D)$, considered as a space of distributions,
and denote the action of $f\in H(D)^*$ on $g\in H(D)$ by $\ip{f,g}$.
\begin{pde}
  When $D$ is bounded and hence $H(D)=H^1_0(D)$, the space $H(D)^*$
  has a well-known characterization.
  Though Hilbert spaces are self-dual, we can instead view the dual space of
  $H^1_0(D)$ as a space of distributions. Viewed in this way, the dual space
  is denoted $H^{-1}(D)$. It consists of all sums of $L^2$-functions (viewed as distributions)
  and first-order distributional derivatives of $L^2$-functions \cite[Proposition~9.20]{Brezis}.
  When $f\in H^{-1}(D)\cap L^2(D)$, the distributional action of $f$ coincides with the $L^2$
  inner product; that is, for $\phi\in H^1_0(D)$,
  we have
    $\ip{f,\phi}=\int_D f\phi$.

\end{pde}
\begin{definition}[The GFF indexed by $H(D)^*$]
  Let $f\in H(D)^*$. By the self-duality of Hilbert spaces,
  there exists $u\in H(D)$ such that $\ip{f,\phi}=\ipd{u,\phi}$
  for all $\phi\in H(D)$.
  We define $\ip{h, f}=\ipd{h,u}$.
\end{definition}
The significance of this definition is as follows.
Suppose $f\in C^{\infty}_c(D)$, and we view it as an element of $H(D)^*$.
Then the function $u\in H(D)$ associated with it solves the partial differential
equation $-\laplace u = f$,
and we have
\begin{align*}
  \ip{h,-\laplace u} = \ipd{h,u},
\end{align*}
as in \eqref{eq:ips}.

This version of the GFF also lends some insight on why the GFF in dimensions two and higher
cannot be represented as a random function. Dirac~$\delta$-measures are elements
of $H^{-1}(D)$ when $d=1$ but not when $d\geq 2$. Thus it makes sense to evaluate
$h$ at a single point~$x$ by $\ip{h,\delta_x}$ only in the one-dimensional case.

\begin{rmk}
  The GFF can also be constructed as a random element of $H^{-\eps}(D)$ for any
  $\eps>0$;
  see \cite[p.~7]{HMP} and \cite[Proposition~2.7, Remark~2.8]{Sheffield} for more details.
  The basic idea is to take
  $\{f_i\}$ and $\{\alpha_i\}$ as in \thref{prop:GFFexists}
  and define
  \begin{align*}
    h = \sum_{i=1}^{\infty} \alpha_i f_i,
  \end{align*}
  which converges a.s.\ in $H^{-\eps}(D)$.
  This defines $\ip{h,f}$ for $f\in C_c^{\infty}(D)$ and
   coincides with our definition of $\ip{h,f}$.
\end{rmk}

The covariances of the Gaussian field $\{\ip{h,f},\,f\in H(D)^*\}$ have a nice
expression in terms of the \emph{Green's function} for the Laplacian operator
on $D$.

\begin{pde}
  The Green's function $G(x,y)$ for the operator $-\laplace$
  on a region~$D$ with Dirichlet boundary conditions
  is a solution to
  $-\laplace G(x,\cdot)=\delta_x$ (in the distributional sense)
  that satisfies $G(x,y)=0$ if $x\in\partial D$
  or $y\in\partial D$. The Green's function in general exists and is unique when $D$
  is bounded with $C^1$ boundary. The Green's function for the upper half-plane
  also exists and can be given explicitly:
  \begin{align*}
    G(x,y) &= -\frac{1}{2\pi}\log\biggl\lvert\frac{x - y}{x-\overline{y}}\biggr\rvert,
  \end{align*}
  thinking of $x$ and $y$ as complex.
  If $f\in H_s(D)$, then $u(x) = \int_D G(x,y)f(y)\,dy$
  is in $H(D)$ and
  satisfies $-\laplace u = f$. The equivalent statement holds
  for $u(x) = \int_D G(x,y)\mu(dy)$   if $\mu\in H(D)^*$
  is a locally finite measure with compact support in $D$.
  See \cite[Chapter~2]{FolPDE} for a reference on Green's functions and related ideas.
\end{pde}
Let $G$ be the Green's function for $-\laplace$ on $D$ with Dirichlet boundary conditions,
and
let $\laplace^{-1}f(x)\defeq -\int_d G(x,y)f(y)\,dy$.

For $f,g\in H_s(D)$,
\begin{align}
  \E\bigl[\ip{h,f}\ip{h,g}\bigr]
    &= \E\bigl[\ipd{h,-\laplace^{-1}f}\ipd{h,-\laplace^{-1}g}\bigr]\nonumber\\
    &= \ipd{-\laplace^{-1}f,-\laplace^{-1}g}\nonumber\\
    &=\ip{f, -\laplace^{-1}g} = \int_D\int_D f(x)G(x,y)g(y)\,dy\,dx.
\end{align}
Similarly, if $\mu,\nu\in H(D)^*$ are locally finite, compactly supported measures, then
\begin{align}
  \E\bigl[\ip{h,\mu}\ip{h,\nu}\bigr] &= \int_D\int_D G(x,y)\mu(dx)\nu(dy).\label{eq:measuregreen}
\end{align}

\subsubsection{Traces}

In this section, we explain how to define $\ip{h,\mu}$ when $\mu$ is a measure
supported on a curve~$\gamma$ in $\overline{D}$, which along with \eqref{eq:measuregreen}
explains \thref{prop:BG2}.
Suppose that $\gamma$ is a simple closed curve in $\overline{D}$, and suppose it forms the boundary
of an open set $E$ and is locally a graph of a Lipschitz function.
Suppose that $\mu$ is supported on
$\gamma$ and bounded with respect to the natural measure there.
Precisely, let $\Hh$ denote $1$-dimensional Hausdorff measure
and suppose that $\mu=\rho\,d\Hh$ for a bounded function $\rho$.
Our goal is to define $\ip{h,\mu}$ by showing that $\mu\in H(D)^*$.
\begin{lem}
  If $D\subset\RR^2$ is bounded, or it is unbounded and its complement contains an open set,
  then the functional  $f\mapsto \int f\,d\mu$ for $f\in H_s(D)$ extends to an element of $H(D)^*$.
\end{lem}
\begin{proof}
First, suppose that
$D$ is bounded.
It suffices to show that $f\mapsto\int f\,d\mu$ is a bounded linear functional with respect to
the Sobolev norm, since this is equivalent to the one given by the
Dirichlet inner product.
The restriction map $H^1_0(D)\to H^1(E)$ is obviously linear and bounded.
By the Sobolev trace theorem \cite[Theorem~4.3.1]{EG},
there is a bounded trace operator $T\colon H^1(E)\to L^2(d\Hh)$
such that $Tf=f\vert_{\gamma}$ when $f$ is continuous.
Thus for $f\in H_s(D)$, we have
\begin{align*}
  \biggl\lvert\int f\,d\mu\biggr\rvert &\leq \int\abs{Tf}\norm{\rho}_\infty\,d\Hh
   \leq \norm{\rho}_\infty\norm{Tf}_{L^2(d\Hh)}\Hh(\gamma)^{1/2}\leq C\norm{f}_{H^1_0(D)}.
\end{align*}
Thus $f\mapsto \int f\,d\mu$ is bounded and admits a unique extension to all
$f\in H(D)$.

Now, suppose that $D\subset\RR^2$ is unbounded. We will identify $\RR^2$ with $\CC$.
Suppose that there is a neighborhood
of $z_0\in\CC$ disjoint from $D$. Consider the conformal map $\varphi(z)=1/(z-z_0)$, and let
$D'=\varphi(D)$, a bounded set. The pushforward measure $\mu'=\mu\circ\varphi$
is supported on $\varphi(\gamma)$, and it has a bounded density with respect to
$\Hh$. By the previous paragraph, for some $C$ and
any $f\in H_s(D)$ we have
\begin{align*}
  \biggl\lvert\int_D f\,d\mu\biggr\rvert = \biggl\lvert\int_{D'}f\circ\varphi\,d\mu'\biggr\rvert
  \leq C\bigl\lVert f\circ\varphi\bigr\rVert_{\grad} = C\norm{f}_\grad
\end{align*}
by the conformal invariance of $\norm{\cdot}_\grad$.
Thus $f\mapsto \int f\,d\mu$ extends to a bounded linear functional on $H(D)$.
\end{proof}

Identifying $\mu$ with its associated element of $H(D)^*$, we have justified
the existence of $\ip{h,\mu}$.
This is the random variable denoted by
$\int_\gamma \rho(z)h(z)\,dz$ in \thref{prop:BG2}.
Together with \eqref{eq:measuregreen}, this explains \thref{prop:BG2}.
}
\subsection{Convergence of fluctuation process to the Gaussian free field}

Recall that $F_t(x)$ counts the eigenvalues of $G(t, 2d(t))$ that
are less than or equal to $2\sqrt{2d(t)-1}x$ and that
\begin{align*}
  \F_t(x) = F_t(x) - \E[F_t(x)\mid N(t)].
\end{align*}
Our goal is to show that $\F_{s+t}(x)$, considered as a function is $x$ and $t$, converges in some sense
to the Gaussian free field. First, we show that integrals against $\F_t(x)$ can be expressed in terms
of traces.
As usual, $T_k(x)$ and $U_k(x)$ denote the Chebyshev polynomials of order $k$ on $[-1,1]$
of the first and second kind, respectively.
\begin{lem}\thlabel{lem:heighttrace}
  \begin{align*}
    \int_{-\infty}^{\infty} U_{k-1}(x)\F_t(x)\,dx
      &= -\frac{1}{k}\Bigl( \tr T_k\bigl(G(t,2d(t))\bigr)
        - \E\bigl[\tr T_k\bigl(G(t,2d(t))\bigr)\,\big\vert\,N(t)\bigr]\Bigr).
  \end{align*}
\end{lem}
\begin{proof}
   As $x\to\pm\infty$, we have $\F_t(x)\to 0$ almost surely.
   Integrating by parts and using the relation $T'_k(x) = kU_{k-1}(x)$,
  \begin{align*}
    \int_{-\infty}^{\infty} U_{k-1}(x)\F_t(x)\,dx
      &=-\frac{1}{k}\int_{-\infty}^{\infty}T_k(x)\,d\F_t(x)\\
      &= -\frac{1}{k}\sum_{i=1}^{N(t)} T_k(\lambda_i) + \frac{1}{k}\E\Biggl[
        \sum_{i=1}^{N(t)} T_k(\lambda_i) \;\bigg\vert\; N(t)\Biggr],
  \end{align*}
  where $\lambda_1\geq\cdots\geq\lambda_{N(t)}$ are the eigenvalues
  of $G(t)$ divided by $2\sqrt{2d(t)-1}$.
  This is equal to
  \begin{align*}
    \int_{-\infty}^{\infty} U_{k-1}(x)\F_t(x)\,dx
      &= -\frac{1}{k}\Bigl( \tr T_k\bigl(G(t,2d(t))\bigr)
        - \E\bigl[\tr T_k\bigl(G(t,2d(t))\bigr)\,\big\vert\,N(t)\bigr]\Bigr).
  \end{align*}
  Note that when $k$ is even, the $na_0$ term introduced by the trace (see
  \thref{def:tr}) is cancelled by the same term in the expectation.
\end{proof}
Combining this lemma with \thref{thm:diagonallimit},
integrals of the form $\int p(x)\F_{s+t}(x)\,dx$ converge jointly as $s\to\infty$
to a Gaussian field indexed by $t$ and by polynomials $p(x)$.
We now express this field in terms of the GFF.

\begin{proof}[Proof of \thref{thm:GFFconvergence}]
\thref{thm:diagonallimit} and \thref{lem:heighttrace} prove that
the integrals
\begin{align*}
  \int_{-\infty}^{\infty} p_i(x)H_s(x,t_i)\,dx,\qquad i=1,\ldots,n
\end{align*}
converge jointly
to a centered multivariate normal distribution, which is also the distribution
of the integrals against the GFF. We just need to check that the covariances match up.
It suffices to confirm this on a polynomial basis.
By \thref{thm:diagonallimit},
\begin{align}
  \lim_{s\to\infty}
  \E\biggl[\biggl( \int_{-\infty}^{\infty} U_{j-1}(x)H_{s}(x,t_0)\,dx\biggr)
   \Biggl( \int_{-\infty}^{\infty} U_{k-1}(x)H_{s}(x,t_1)\,dx\biggr)\Biggr]
  = \delta_{jk}
    \frac{\pi}{4k}e^{k(t_0-t_1)}\label{eq:covval}
\end{align}
for $t_0\leq t_1$.
By \thref{prop:BG2}, the covariance of
\begin{align*}
  \int_{-1}^1U_{j-1}(x)h(\Omega(x,t_0))\,dx \text{\quad and\quad}
\int_{-1}^1U_{k-1}(x)h(\Omega(x,t_1))\,dx
\end{align*}
is
\begin{align*}
  I \defeq  -\frac{1}{2\pi}\int_{-1}^1\int_{-1}^1 U_{j-1}(x)\log
    \biggl\lvert \frac{\Omega(x,t_0)-\Omega(y,t_1)}{\Omega(x,t_0)-\overline{\Omega}(y,t_1)}
    \biggr\rvert U_{k-1}(y)\,dx\,dy.
\end{align*}
Substituting $x=\cos u$ and $y=\cos v$, we have
\begin{align}\label{eq:Itobound}
  I = -\frac{1}{2\pi}\int_0^{\pi}\int_0^{\pi} U_{j-1}(\cos u)\sin u
      \log  \biggl\lvert \frac{e^{t_0+iu}-e^{t_1+iv}}{e^{t_0+iu}-e^{t_1-iv}}
    \biggr\rvert U_{k-1}(\cos v)\sin v\,du\,dv.
\end{align}
Assume that $t_0<t_1$.
For any constant $w\in\CC$ with $\abs{w}=t_1$, we can define
  functions $\log(z-w)$ and $\log(z-\overline{w})$ that are analytic on $\abs{z}<t_1$.
  For each $v$, we choose two such logarithm functions with $w=e^{t_1+iv}$ to get
  \begin{align*}
    \log\biggl\lvert \frac{e^{t_0+iu}-e^{t_1+iv}}{e^{t_0+iu}-e^{t_1-iv}} \biggr\rvert
     &= \frac12\Bigl( \log\bigl(e^{t_0+iu}-e^{t_1+iv}\bigr)
       +\log\bigl(e^{t_0-iu}-e^{t_1-iv}\bigr)\\
       &\qquad\qquad-\log\bigl(e^{t_0+iu}-e^{t_1-iv}\bigr)
       -\log\bigl(e^{t_0-iu}-e^{t_1+iv}\bigr)
       \Bigr).
  \end{align*}
  Using the relation $U_{n-1}(\cos x) = \sin(nx)/\sin x$, we then have
  \begin{align*}
    I &= -\frac{1}{4\pi}\int_0^\pi\int_0^{2\pi}\sin(ju)\sin(kv) \Bigl(
      \log\bigl(e^{t_0+iu}-e^{t_1+iv}\bigr) - \log\bigl(e^{t_0+iu}-e^{t_1-iv}\bigr)\Bigr)du\,dv,
  \end{align*}
  and by integrating by parts in $u$,
  \begin{align*}
    I
      &= -\frac{1}{4j\pi}\int_0^\pi\int_0^{2\pi}\cos(ju)\sin(kv)
      \biggl( \frac{ie^{t_0+iu}}{e^{t_0+iu}-e^{t_1+iv}} - \frac{ie^{t_0+iu}}{e^{t_0+iu}-e^{t_1-iv}}\biggr)du\,dv\\
     &= -\frac{1}{4j\pi}\int_0^{2\pi}\int_0^{2\pi}\cos(ju)\sin(kv)
      \frac{ie^{t_0+iu}}{e^{t_0+iu}-e^{t_1+iv}}\,du\,dv.
  \end{align*}
  We then integrate by parts in $v$ to get
  \begin{align*}
    I &= \frac{1}{4jk\pi}\int_0^{2\pi}\int_0^{2\pi}\cos(ju)\cos(kv)
      \frac{e^{t_0+t_1+i(u+v)}}{\bigl(e^{t_0+iu}-e^{t_1+iv}\bigr)^2}\,du\,dv.
  \end{align*}
  Let $\gamma$ denote a counterclockwise path around the unit disc.
  \begin{align*}
    I &= \frac{1}{4jk\pi}\int_0^{2\pi}\cos(kv)\int_\gamma
      \frac{z^{j}+z^{-j}}{2iz}\frac{e^{t_0+t_1+iv}z}{\bigl(e^{t_0}z - e^{t_1+iv}\bigr)^2}
        dz\,dv.
  \end{align*}
  The integrand of the path integral has a single pole in the unit disc at $0$, and the residue
  there is $je^{j(t_0-t_1-iv)}/2i$. This gives
  \begin{align*}
    I &= \frac{1}{4k}\int_0^{2\pi}\cos(kv)
       e^{j(t_0-t_1-iv)}\,
    dv\\
    &= \frac{1}{4k}\int_\gamma\frac{w^{k}+w^{-k)}}{2iw}
       e^{j(t_0-t_1)}w^{-j}\,
    dw \\
    &= \frac{e^{j(t_0-t_1)}}{8ik}
      \int_\gamma \bigl(w^{k-j-1}+w^{-k-j-3}\bigr)
       dw.
  \end{align*}
  By computing residues, this is $\pi e^{j(t_0-t_1)}/4k$ if $j=k$ and $0$ otherwise,
  agreeing with \eqref{eq:covval} for all $t_0<t_1$.
  To extend this to $t_0=t_1$ by a limiting argument, we apply the dominated convergence
  theorem to the integral in \eqref{eq:Itobound}.
  One can show that
  \begin{align*}
    \Biggl\lvert\log  \biggl\lvert \frac{e^{t_0+iu}-e^{t_1+iv}}{e^{t_0+iu}-e^{t_1-iv}}
    \biggr\rvert\Biggr\rvert
    &\leq \log\biggl\lvert\frac{e^{iu} - e^{-iv}}{e^{iu}-e^{iv}}\biggr\rvert
  \end{align*}
  for all $t_0\leq t_1$.  The right-hand side of this equation
  is integrable over $0\leq u,v\leq \pi$. The other factors of the integrand in
  \eqref{eq:Itobound} are bounded there. Thus by the dominated convergence theorem
  we can compute $I$ when $t_0=t_1$ by letting $t_0\to t_1$ from below.
\end{proof}

config: arxiv