Top

Foundations of Computational Mathematics

Published in:

Open Access 21-01-2022

Continuum Limit of Lipschitz Learning on Graphs

Authors: Tim Roith, Leon Bungert

Published in: Foundations of Computational Mathematics | Issue 2/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Patentsearch

Off

Abstract

Tackling semi-supervised learning problems with graph-based methods has become a trend in recent years since graphs can represent all kinds of data and provide a suitable framework for studying continuum limits, for example, of differential operators. A popular strategy here is p-Laplacian learning, which poses a smoothness condition on the sought inference function on the set of unlabeled data. For $p<\infty $ continuum limits of this approach were studied using tools from $\varGamma $-convergence. For the case $p=\infty $, which is referred to as Lipschitz learning, continuum limits of the related infinity Laplacian equation were studied using the concept of viscosity solutions. In this work, we prove continuum limits of Lipschitz learning using $\varGamma $-convergence. In particular, we define a sequence of functionals which approximate the largest local Lipschitz constant of a graph function and prove $\varGamma $-convergence in the $L^{\infty }$-topology to the supremum norm of the gradient as the graph becomes denser. Furthermore, we show compactness of the functionals which implies convergence of minimizers. In our analysis we allow a varying set of labeled data which converges to a general closed set in the Hausdorff distance. We apply our results to nonlinear ground states, i.e., minimizers with constrained $L^p$-norm, and, as a by-product, prove convergence of graph distance functions to geodesic distance functions.

Communicated by Alan Edelman.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

1 Introduction

Several works in mathematical data science and machine learning have proven the importance of semi-supervised learning as an essential tool for data analysis, see [17, 38‐41]. Many classification tasks and problems in image analysis (see, e.g., [17] for an overview) traditionally require an expert examining the data by hand, and this so-called labeling process is often a time-consuming and expensive task. In contrast, one typically faces an abundance of unlabeled data which one would also like to equip with suitable labels. This is the key goal of the semi-supervised learning problem which mathematically can be formulated as the extension of a labeling function

$$\begin{aligned} g:{\mathcal {O}}\rightarrow \mathbb {R}\end{aligned}$$

onto the whole data set $V:={\mathcal {V}}\cup {\mathcal {O}}$, where ${\mathcal {O}}$ denotes the set of labeled and ${\mathcal {V}}$ the set of unlabeled data. In most cases, the underlying data can be represented as a finite weighted graph $(V,\omega )$—composed of vertices V and a weight function $\omega $ assigning similarity values to pairs of vertices—which provides a convenient mathematical framework. A popular method to generate a unique extension of the labeling function to the whole data set is so- called p-Laplacian regularization, which can be formulated as minimization task

$$\begin{aligned} \min _{\mathbf {u}:V\rightarrow \mathbb {R}} \sum _{x,y\in V} \omega (x,y)^p \left| \mathbf {u}(x)-\mathbf {u}(y)\right| ^p, \quad \text { subject to }\mathbf {u} = g\text { on }{\mathcal {O}}, \end{aligned}$$

(1)

over all graph functions $\mathbf {u}:V\rightarrow \mathbb {R}$ subject to a constraint given by the labels on ${\mathcal {O}}$, see, e.g., [2, 22, 35, 38]. This method is equivalent to solving the p-Laplacian partial differential equations on graphs [19] and therewith introduces a certain amount of smoothness of the labeling function. Furthermore, continuum limits of this model as the number of unlabeled data tends to infinity were studied using tools from $\varGamma $-convergence [22, 35, 36] and PDEs [14‐16] (see Sect. 1.2 for more details).

Still, p-Laplacian regularization comes with the drawback that it is ill-posed if p is smaller than the ambient space dimension in the sense that the obtained solutions tend to be an average of the label values rather than properly incorporating the information. Extensive studies of this problem were carried out in [35, 36]. To overcome this degeneracy, there are several options: In [16] it was investigated at which rates the number of labeled data has to grow to obtain a well-posed problem for $p=2$ in (1). In [15] it was suggested to replace the pointwise constraint $\mathbf {u}=g$ on ${\mathcal {O}}$ with measure-valued source terms for the graph Laplacian equation. In contrast, in [2] the authors propose to consider the p-Laplacian regularization for large p. In order to have well-posedness for general space dimensions, one therefore considers the limit $p\rightarrow \infty $ which leads to the so-called Lipschitz learning problem

$$\begin{aligned} \min _{\mathbf {u}:V\rightarrow \mathbb {R}} \max _{x,y\in V}\omega (x,y) \left| \mathbf {u}(x)-\mathbf {u}(y)\right| \quad \text { subject to }\mathbf {u} = g\text { on }{\mathcal {O}}. \end{aligned}$$

(2)

While in the case $p<\infty $ one has the unique existence of solutions and equivalence of the p-Laplacian PDE and the energy minimization task, these properties are lost in the case $p=\infty $. One distinguished continuum model—in the sense that it admits unique solutions—connected to this problem is absolutely minimizing Lipschitz extensions and the associated infinity Laplacian equation (see, e.g., [3‐5, 20, 27, 34]). Using the concept of viscosity solutions, in [14] a convergence result on continuum limits for the infinity Laplacian equation on the flat torus was established, see again Sect. 1.2 for more details. Still, in [30] the authors suggest that other Lipschitz extensions (next to the absolutely minimizing) are indeed relevant for machine learning tasks but a rigorous continuum limit for general Lipschitz extensions has been pending.

The main goal of this paper is to derive a continuum limit for the Lipschitz learning problems (2) to which end we prove $\varGamma $-convergence and compactness of the functional in (2). We investigate novel smoothness conditions on the underlying domain which are special for this $L^{\infty }$-variational problem and originate from the discrepancy between the maximum local Lipschitz constant and the global one. We apply our results to minimizers of a Rayleigh quotient involving the $L^{\infty }$-norm of the gradient as first examined in [13]. The concrete outline of this paper can be found in Sect. 1.3.

1.1 Assumptions and Main Result

Let $\varOmega \subset \mathbb {R}^d$, $d\in \mathbb {N}$, be an open and bounded domain, and let $\varOmega _n\subset {\overline{\varOmega }}$ for $n\in \mathbb {N}$ denote a sequence of finite subsets. For each $n\in \mathbb {N}$ we consider the finite weighted graph $(\varOmega _n, \omega _n)$, where $\omega _n:\varOmega _n\times \varOmega _n\rightarrow [0,\infty )$ is a weighting function which in our context is given as

$$\begin{aligned} \omega _n(x,y) := \eta _{s_n}(\left| x-y\right| ) := \eta (\left| x-y\right| /s_n). \end{aligned}$$

Here $\eta :[0,\infty )\rightarrow [0,\infty )$ denotes the kernel and $s_n>0$ the scaling parameter. The edge set of the graph is implicitly characterized via the weighting function, i.e., for $x,y\in \varOmega _n$ we have

$$\begin{aligned} (x,y)\text { is an edge iff } \omega _n(x,y)>0. \end{aligned}$$

In the following we state standard assumptions on the kernel function $\eta $, see, e.g., [14, 22, 35, 36],

(K1)

$\eta $ is positive and continuous at 0,

(K2)

$\eta $ is non-increasing,

(K3)

$\mathrm {supp}(\eta ) \subset [0,c_\eta ]$ for some $c_\eta >0$.

Similar to [22] we define the value $\sigma _{\eta } := {{\,\mathrm{ess\,sup}\,}}_{t\ge 0} \left\{ \eta (t)~t\right\} $ which is a positive number and appears in the $\varGamma $-limit.

To incorporate constraints, for each n we denote by ${\mathcal {O}}_n\subset \varOmega _n$ the set of labeled vertices as shown in (2). Often this set is fixed and therefore independent of n (e.g., [14, 22, 35]; however, see also [15, 16] for p-Laplacian learning models with varying constraint sets). As we see in Lemmas 5 and 6, making this assumption is not necessary in our case. We only require that the sets ${\mathcal {O}}_n$ converge to some closed set ${\mathcal {O}}\subset {\overline{\varOmega }}$ in the Hausdorff distance sufficiently fast, i.e.,

$$\begin{aligned} d_H({\mathcal {O}}_n,{\mathcal {O}}) := \max \left( \sup _{x\in {\mathcal {O}}}\inf _{y\in {\mathcal {O}}_n} |x-y|, \sup _{y\in {\mathcal {O}}_n}\inf _{x\in {\mathcal {O}}} |x-y|\right) = o(s_n),\quad n \rightarrow \infty , \end{aligned}$$

(3)

where $s_n$ denotes the spatial scaling of the kernel, introduced above. A prototypical example for the constraint set is ${\mathcal {O}}=\partial \varOmega $ which corresponds to the problem of extending Lipschitz continuous boundary values g from $\partial \varOmega $ to $\varOmega $. Considering a labeling function $g:{\overline{\varOmega }}\rightarrow \mathbb {R}$ which is Lipschitz continuous allows us to restrict it to the finite set of vertices ${\mathcal {O}}_n$. The target functional for the discrete case has the form

$$\begin{aligned} E_n(\mathbf {u}) = \frac{1}{s_n}\max _{x,y\in \varOmega _n} \left\{ \eta _{s_n}(\left| x-y\right| ) \left| \mathbf {u}(x) - \mathbf {u}(y)\right| \right\} \end{aligned}$$

(4)

for a function $\mathbf {u}:\varOmega _n\rightarrow \mathbb {R}$.

Additionally we define the constrained version of the functional, which incorporates the labeling function, as follows

$$\begin{aligned} E_{n,\mathrm {cons}}(\mathbf {u})= {\left\{ \begin{array}{ll} E_n(\mathbf {u})&{}\text { if } \mathbf {u} = g\text { on }{\mathcal {O}}_n,\\ \infty &{}\text { else.} \end{array}\right. } \end{aligned}$$

A typical problem in this context of continuum limits is to find a single metric space in which the convergence of these functionals takes place. In our case we choose the normed space $L^{\infty }(\varOmega )$ and thus need to extend the functionals $E_n$ to $L^{\infty }(\varOmega )$. This can be achieved by employing the well-established technique (see, e.g., [23]) of only considering piecewise constant functions. To this end we let $p_n$ denote a closest point projection, i.e., a map $p_n:\varOmega \rightarrow \varOmega _n$ such that

$$\begin{aligned} p_n(x)\in {{\,\mathrm{arg\,min}\,}}_{y\in \varOmega _n}\left| x-y\right| \end{aligned}$$

for each $x\in \varOmega $. While $p_n$ is not necessarily uniquely determined, this ambiguity is not relevant for our analysis. There, it is only important to control the value of $\left| p_n(x)-x\right| $ which is independent of the choice of $p_n$. This map has already been employed in [14] and it allows us to transform a graph function $\mathbf {u}:\varOmega _n\rightarrow \mathbb {R}$ to a piecewise constant function, by considering $\mathbf {u}\circ p_n\in L^{\infty }(\varOmega )$. This function is constant on each so-called Voronoi cell $\mathrm {int}(p_n^{-1}(y))$ for $y\in \varOmega _n$. This procedure is similar to the technique proposed in [22], where an optimal transport map $T_n:\varOmega \rightarrow \varOmega _n$ is used for turning graph functions into continuum functions. Now we can extend the functional $E_n$ and $E_{n,\mathrm {cons}}$ to arbitrary functions $u\in L^{\infty }(\varOmega )$ by defining with a slight abuse of notation

$$\begin{aligned} E_{n}(u)&:= {\left\{ \begin{array}{ll} E_{n}(\mathbf {u}) \quad &{}\text {if }\exists \mathbf {u}:\varOmega _n\rightarrow \mathbb {R}: u = \mathbf {u} \circ p_n, \\ \infty \quad &{}\text {else}. \end{array}\right. } \end{aligned}$$

(5)

$$\begin{aligned} E_{n,\mathrm {cons}}(u)&:= {\left\{ \begin{array}{ll} E_{n,\mathrm {cons}}(\mathbf {u}) \quad &{}\text {if }\exists \mathbf {u}:\varOmega _n\rightarrow \mathbb {R}: u = \mathbf {u} \circ p_n, \\ \infty \quad &{}\text {else}. \end{array}\right. } \end{aligned}$$

(6)

In order to control how the discrete sets $\varOmega _n$ fill out the domain $\varOmega $, we consider the value

$$\begin{aligned} r_n:=\sup _{x\in \varOmega } \min _{y\in \varOmega _n} \left| x-y\right| , \end{aligned}$$

(7)

and require that it tends faster to zero than the scaling $s_n$, namely, we assume that

$$\begin{aligned} \frac{r_n}{s_n}\longrightarrow 0, \quad n \rightarrow \infty . \end{aligned}$$

(8)

We are interested in the case that $(s_n)_{n\in \mathbb {N}}\subset (0,\infty )$ is a null sequence meaning that $s_n\rightarrow 0$ for $n\rightarrow \infty $.

Remark 1

In the context of continuum limits one often employs random geometric graphs, where the discrete sets are obtained as a sequence of points that are i.i.d. w.r.t. a probability distribution $\mu \in {\mathcal {P}}({{\overline{\varOmega }}})$. Typically there is no need to use a probabilistic framework in the $L^\infty $ context, since in contrast to the graph p-Dirichlet energy (13), which is a Monte Carlo approximation of an integral functional, the corresponding discrete Lipschitz energy (4) approximates an essential supremum. Therefore, only the support of a probability measure enters our problem. Similar observations are made in [14, 31] where the value $r_n$ is also employed to control the discrete sets $\varOmega _n$.

The $\varGamma $-limit of the discrete functionals $E_n$ turns out to be a constant multiple of the following continuum functional

$$\begin{aligned} {\mathcal {E}}(u) := {\left\{ \begin{array}{ll} {{\,\mathrm{ess\,sup}\,}}_{x\in \varOmega }~\left| \nabla {u}(x)\right| &{}\text {if } u \in W^{1,\infty }(\varOmega ),\\ \infty &{}\text {else.} \end{array}\right. } \end{aligned}$$

(9)

A constrained version of this functional can be defined analogously

$$\begin{aligned} {\mathcal {E}}_{\mathrm {cons}}(u) := {\left\{ \begin{array}{ll} {\mathcal {E}}(u)&{}\text {if } u \in W^{1,\infty }(\varOmega )\text { and } u=g\text { on }{\mathcal {O}},\\ \infty &{}\text {else.} \end{array}\right. } \end{aligned}$$

(10)

Before stating our main results we need to introduce a final assumption on the domain $\varOmega $ which is necessary because of the discrepancy of the Lipschitz constant and the supremal norm of the gradient of functions on non-convex sets. For this we introduce the geodesic distance, induced on $\varOmega $ by the Euclidean distance, which is defined as

$$\begin{aligned} d_\varOmega (x,y)=\inf \left\{ \mathrm {len}(\gamma ): \gamma :[a,b]\rightarrow \varOmega \text { is a curve with } \gamma (a)=x, \gamma (b) = y \right\} , \end{aligned}$$

where the length of a curve is given by

$$\begin{aligned} \mathrm {len}(\gamma ):=\sup \left\{ \sum _{i=0}^{N-1} \left| \gamma (t_{i+1})-\gamma (t_i)\right| \,:\,N\in \mathbb {N},\,a=t_0\le t_1\le \cdots \le t_N=b\right\} , \end{aligned}$$

see, e.g., [10, Prop. 3.2]. While on convex domains it holds $d_\varOmega (x,y)=\left| x-y\right| $, we only need to assume the weaker condition:

$$\begin{aligned} \lim _{\delta \downarrow 0}\sup \left\{ \frac{d_\varOmega (x,y)}{\left| x-y\right| }\,:\, x,y\in \varOmega ,\,\left| x-y\right| <\delta \right\} \le 1. \end{aligned}$$

(11)

In Sect. 3 we explore examples of sets which satisfy this condition; however, already at this point we would like to say that it is satisfied, for instance, for convex sets, for sets with smooth boundary, or for sets which locally are diffeomorphic to a convex set. In a nutshell, condition (11) prohibits the presence of internal corners in the boundary. Furthermore, since it holds $d_\varOmega (x,y)\ge \left| x-y\right| $, condition (11) requires the geodesic and the Euclidean distance to coincide locally.

Main results Our two main results state the discrete-to-continuum $\varGamma $-convergence of the functionals $E_{n,\mathrm {cons}}$ to $\sigma _\eta ~{\mathcal {E}}_\mathrm {cons}$ and that sequences of minimizers of the discrete functionals converge to a minimizer of the continuum functional.

Theorem 1

(Discrete to continuum $\varGamma $-convergence) Let $\varOmega \subset \mathbb {R}^{d}$ be a domain satisfying (11), let the kernel fulfill (K1)–(K3), and let the constraint sets ${\mathcal {O}}_n,{\mathcal {O}}$ satisfy (3), then for any null sequence $\left( s_{n}\right) _{n\in \mathbb {N}}\subset (0,\infty )$ which satisfies the scaling condition (8) we have

$$\begin{aligned} E_{n,\mathrm {cons}}\overset{\varGamma }{\longrightarrow }\sigma _{\eta }~{\mathcal {E}}_\mathrm {cons}. \end{aligned}$$

(12)

Theorem 2

(Convergence of Minimizers) Let $\varOmega \subset \mathbb {R}^{d}$ be a domain satisfying (11), let the kernel fulfill (K1)–(K3), let the constraint sets ${\mathcal {O}}_n,{\mathcal {O}}$ satisfy (3), and $\left( s_{n}\right) _{n\in \mathbb {N}}\subset (0,\infty )$ be a null sequence which satisfies the scaling condition (8). Then any sequence $\left( u_{n}\right) _{n\in \mathbb {N}}\subset L^{\infty }(\varOmega )$ such that

$$\begin{aligned} \lim _{n\rightarrow \infty }\left( E_{n,\mathrm {cons}}(u_n) - \inf _{u\in L^{\infty }(\varOmega )}E_{n,\mathrm {cons}}(u)\right) = 0 \end{aligned}$$

is relatively compact in $L^{\infty }(\varOmega )$ and

$$\begin{aligned} \lim _{n\rightarrow \infty } E_{n,\mathrm {cons}}(u_n) = \min _{u\in L^{\infty }(\varOmega )}\sigma _{\eta }~{\mathcal {E}}_{\mathrm {cons}}(u). \end{aligned}$$

Furthermore, every cluster point of $(u_n)_{n\in \mathbb {N}}$ is a minimizer of ${\mathcal {E}}_{\mathrm {cons}}$.

The first studies concerning the limit behavior of difference operators on random graphs were carried out in [33] and the follow-up work [32], which considers the consistency of spectral clustering on graphs. The main motivation of our paper is the works [22, 35] where the $\varGamma $-convergence of the discrete functionals

$$\begin{aligned} E^{(p)}_n(\mathbf {u}) = \frac{1}{s_n^p n^2}\sum _{x,y\in \varOmega _n} \eta _{s_n}(\left| x-y\right| ) \left| \mathbf {u}(x)-\mathbf {u}(y)\right| ^p \end{aligned}$$

(13)

toward a continuum functional of the form

$$\begin{aligned} {\mathcal {E}}^{(p)}(u) = \sigma _\eta \int _{\varOmega } \left| \nabla {u}\right| ^p \rho ^2(x)~\mathrm {d}x, \end{aligned}$$

for $1\le p<\infty $ and u smooth enough, is shown. Here, $\rho $ is the density of the measure $\mu $ according to which the points $x_i$ are distributed. The $\varGamma $-convergence is considered w.r.t. the $TL^{p}$ topology, which allows to compare discrete functions $\mathbf {u}\in L^{p}(\nu _n)$ with continuum functions $u\in L^{p}(\mu )$ via an optimal transport ansatz. Here, $\nu _n$ denotes the empirical measure for the set $\varOmega _n$, see (21). In particular, the problem they study is connected to the extension task (1) by considering the constrained functional

$$\begin{aligned} E^{(p)}_{n,\mathrm {cons}}(\mathbf {u}):= {\left\{ \begin{array}{ll} E^{(p)}_n(\mathbf {u})&{}\text { if } \mathbf {u}(x_i) = g(x_i) \text { for }x_i\in {\mathcal {O}},\\ \infty &{}\text { else}, \end{array}\right. } \end{aligned}$$

and the associated minimization problem

$$\begin{aligned} \inf _{\mathbf {u}\in L^{p}(\nu _n)}E^{(p)}_{n,\mathrm {cons}}(\mathbf {u}). \end{aligned}$$

(14)

Here, the constraint set ${\mathcal {O}}$ is assumed to be a fixed collection of finitely many points. The main result they show ensures that minimizers of the functionals $E^{(p)}_{n,\mathrm {cons}}$ converge uniformly toward minimizers of a respective constrained version of ${\mathcal {E}}^{(p)}$ under appropriate assumptions on the scaling $s_n$. The motivation for considering the limit $p\rightarrow \infty $ for above problems is given in [2], where the graph p-Laplacian for $p<d$ is noticed to have undesirable properties, namely the solution of problem (14) tends to equal a constant at the majority of the vertices with sharp spikes at the labeled data. Using a suitable scaling, this problem does not occur in the case $p>d$ (which is intuitively connected to the Sobolev embedding $W^{1,p}(\varOmega ) \hookrightarrow C^{0,1-d/p}({{\overline{\varOmega }}})$ for $p>d$ see [1, Ch. 4]) and, in particular, as pointed out in [30, Sec. 3] one generally hopes for better interpolation properties in the case $p\rightarrow \infty $. However, in this limit the interpretation of the measure $\mu $ and its density changes, namely only its support enters the problem. The functional ${\mathcal {E}}^{(p)}$ incorporates information about the distribution of the data in the form of the density $\rho $. Using standard properties of $L^p$-norms, the limit $p\rightarrow \infty $ on the other hand reads

$$\begin{aligned} \mu {\text {-}}{{\,\mathrm{ess\,sup}\,}}_{x\in \varOmega } \left| \nabla {u}\right| = \lim _{p\rightarrow \infty } \big ({\mathcal {E}}^{(p)}(u)\big )^{1/p} \end{aligned}$$

and thus only the support of the measure $\mu $ is relevant. This phenomenon was already observed in [2, 14] which the authors informally described as the limit ‘forgetting’ the distribution of the data. Furthermore, this observation is consistent with our results, since the limit $n\rightarrow \infty $ is independent of the sequence $\left( x_{i}\right) _{i\in \mathbb {N}}\subset \varOmega $ as long as it fills out the domain $\varOmega $ sufficiently fast, see Theorem 1 for the precise condition. In the case $p<\infty $ the minimization task (1) is equivalent to the graph p-Laplace equation, for which the formal limit $p\rightarrow \infty $ leads to the graph infinity Laplace equation

$$\begin{aligned} \begin{aligned} \varDelta _\infty \mathbf {u}&= 0 \text { in } V{\setminus }{\mathcal {O}},\\ \mathbf {u}&= g\text { in }{\mathcal {O}}, \end{aligned} \end{aligned}$$

(15)

where the operator $\varDelta _\infty $ on $\varOmega _n$ is defined as

$$\begin{aligned} \varDelta _\infty \mathbf {u}(x):=\max _{y\in \varOmega _n}\omega (x,y)(\mathbf {u}(y) - \mathbf {u}(x)) + \min _{y\in \varOmega _n}\omega (x,y)(\mathbf {u}(y) - \mathbf {u}(x)). \end{aligned}$$

One should note that the unique solution of (15) also solves the Lipschitz learning task (2), see, e.g., [14, 30]. A first study concerning the continuum limit of this problem is carried out in [14]. The main result therein states that the solutions of the discrete problems converge uniformly to the viscosity solution of the continuum equation,

$$\begin{aligned} \begin{aligned} \varDelta _\infty u&=0 \text { in }\varOmega ,\\ u&=g\text { on }{\mathcal {O}}, \end{aligned} \end{aligned}$$

(16)

where the continuum infinity Laplacian for a smooth function u is defined as

$$\begin{aligned} \varDelta _\infty u := \langle \nabla u, D^2 u\nabla u\rangle = \sum _{i,j=1}^d \partial _i u\,\partial _j u\, \partial ^2_{ij}u. \end{aligned}$$

(17)

The considered domain is the flat torus, i.e., $\varOmega =\mathbb {R}^{d}{\setminus }\mathbb {Z}^d$ and again the constraint set ${\mathcal {O}}$ is assumed to be fixed and finite. Furthermore, the only requirement on the sequence of points $\varOmega _n\subset \varOmega $ is characterized by the value $r_n$ defined in (7).

Theorem 3

[14, Thm. 2.1] Consider the flat torus $\varOmega =\mathbb {R}^{d}{\setminus }\mathbb {Z}^d$, let the kernel $\eta \in C^2([0,\infty ))$ be such that

$$\begin{aligned} {\left\{ \begin{array}{ll} \eta (s)\ge 1&{}\text { for } s\le 1,\\ \eta (s)=0&{}\text { for } s\ge 2, \end{array}\right. } \end{aligned}$$

then for a null sequence $\left( s_{n}\right) _{n\in \mathbb {N}}\subset (0,\infty )$ such that

$$\begin{aligned} \frac{r_n^2}{s_n^3}\longrightarrow 0 \end{aligned}$$

(18)

and for the sequence $\mathbf {u}_n$ of solutions to problem (15) we have that $\mathbf {u}_n \rightarrow u$ uniformly, where $u\in C^{0,1}(\varOmega )$ is the unique viscosity solution of the infinity Laplace equation (16) on $\varOmega $, i.e.,

$$\begin{aligned} \lim _{n\rightarrow \infty }\max _{x\in \varOmega _n}\left| \mathbf {u}_n(x) - u(x)\right| = 0. \end{aligned}$$

Remark 2

We state this result, since it provides the first continuum limit of the infinity Laplace equation (15) on general graphs. Solutions of this problem constitute a special subclass of minimizers in the Lipschitz learning task (2). To show that the limit of solutions of (15) solve the continuum PDE (16) the author in [14] utilizes a consistency argument which requires smoothness of the kernel $\eta $ and the relatively strict scaling condition (18). In contrast, our results consider the general minimization problem (2), which allows us to work with the weakest scaling condition possible (8)—namely that the graph is asymptotically connected—and much weaker conditions on the kernel $\eta $.

Remark 3

(Convergence Rates) Note that [14] did not establish rates of convergence for solutions of the graph infinity Laplacian equation (15) and neither do we for general minimizers of (2). Indeed, $\varGamma $-convergence is not a good tool for proving quantitative rates since it is a very indirect notion of convergence (see also [35, 36] which do not establish convergence rates either). At the same time $\varGamma $-convergence typically allows for much less restrictive conditions on the graph scaling than PDE techniques, cf. Remark 2. Still, in the recent work [12] we successfully used comparison principle techniques to show rates of convergence for solutions of the graph infinity Laplacian equation (15) in a much more general setting than the one considered in [14]. For showing this it suffices to use quantitative versions of the weak scaling assumption (8) and the domain regularity condition (11).

Since the solutions of the continuum PDE (16) only exist in the viscosity sense, the proof of this theorem involves viscosity techniques. The arguments are therefore fundamentally different to the results for the case $p<\infty $ in [36]. This is our motivation to use $\varGamma $-convergence also for $p=\infty $.

1.3 Outline

In Sect. 2 we give an overview of the concepts of $\varGamma $-convergence and the closest point projection. In particular, we derive a transformation rule for supremal functionals which is the analogue of the well-known integral transformation rule for the change of variables.

Section 3 is devoted to the proofs of our main results Theorems 1 and 2. Similar to the strategy in [22], in Sect. 3.1 we first prove $\varGamma $-convergence of the non-local auxiliary functionals

$$\begin{aligned} {\mathcal {E}}_{s}(u) := \frac{1}{s}~{{\,\mathrm{ess\,sup}\,}}_{x,y\in \varOmega } \left\{ \eta _{s}(\left| x-y\right| )\left| u(x) - u(y)\right| \right\} ,\quad s>0 \end{aligned}$$

(19)

which mimic the non-local structure of the discrete functionals $E_n$ in (4), to the continuum functional ${\mathcal {E}}$ in (9). Subsequently, in Sect. 3.2 we use this result for proving our first main result, discrete to continuum $\varGamma $-convergence of the constrained discrete functionals $E_{n,\mathrm {cons}}$. In Sect. 4 we prove compactness of the discrete functionals which yields our second main result, the convergence of minimizers.

In Sect. 5 we apply our results to a nonlinear eigenvalue problem and prove convergence of discrete ground states to continuum ground states. Furthermore, generalizing the results in [13], we characterize the latter as geodesic distance function to the constraint set ${\mathcal {O}}$.

2 Mathematical Background

This section reviews two important mathematical tools which we use in this paper. The first one is the concept of $\varGamma $-convergence, which allows to deduce convergence of minimizers from convergence of functionals. The second concept, entirely unrelated to $\varGamma $-convergence, is the closest point projection which we employ in order to turn graph functions into continuum ones. Furthermore, we derive a supremal version of the transformation rule.

2.1 $\varGamma $-Convergence

In this section we introduce a convergence concept that is frequently employed in the theory of variational problems, namely the so-called $\varGamma $-convergence. We refer to [8] for a detailed introduction.

Definition 1

($\varGamma -convergence$) Let X be a metric space and let $F_n:X\rightarrow [-\infty ,\infty ]$ be a sequence of functionals. We say that $F_n$ $\varGamma $-converges to the functional $F:X\rightarrow [-\infty ,\infty ]$ if

(i)

(liminf inequality) for every sequence $\left( x_{n}\right) _{n\in \mathbb {N}}\subset X$ converging to $x\in X$ we have that

$$\begin{aligned} \liminf _{n\rightarrow \infty } F_n(x_n) \ge F(x); \end{aligned}$$

(ii)

(limsup inequality) for every $x\in X$ there exists a sequence $\left( x_{n}\right) _{n\in \mathbb {N}}\subset X$ converging to x and

$$\begin{aligned} \limsup _{n\rightarrow \infty } F_n(x_n)\le F(x). \end{aligned}$$

The notion of $\varGamma $-convergence is especially useful, since it implies the convergence of minimizers under additional compactness assumptions. For convenience we prove the respective result below, the proof is an adaption of a similar result in [8, Thm. 1.21].

Lemma 1

(Convergence of Minimizers) Let X be a metric space and $F_n:X\rightarrow [0,\infty ]$ a sequence of functionals $\varGamma $-converging to $F\rightarrow X:[0,\infty ]$ which is not identically $+\infty $. If there exists a relatively compact sequence $(x_n)_{n\in \mathbb {N}}$ such that

$$\begin{aligned} \lim _{n\rightarrow \infty } \left( F_n(x_n) - \inf _{x\in X} F_n(x)\right) = 0, \end{aligned}$$

then we have that

$$\begin{aligned} \lim _{n\rightarrow \infty } \inf _{x\in X} F_n(x) = \min _{x\in X} F(x) \end{aligned}$$

and any cluster point of $(x_n)_{n\in \mathbb {N}}$ is a minimizer of F.

Proof

Using the $\varGamma $-convergence of $F_n$ for any $y\in X$ we can find a sequence $\left( y_{n}\right) _{n\in \mathbb {N}}\subset X$ such that

$$\begin{aligned} \limsup _{n\rightarrow \infty } F_n(x_n) = \limsup _{n\rightarrow \infty } \inf _{x\in X} F_n(x)\le \limsup _{n\rightarrow \infty } F_n(y_n)\le F(y) \end{aligned}$$

and thus

$$\begin{aligned} \limsup _{n\rightarrow \infty } F_n(x_n) \le \inf _{x\in X} F(x)<\infty , \end{aligned}$$

(20)

where for the last inequality we use the fact that F is not identically $+\infty $. By assumption the sequence $(x_n)_{n\in \mathbb {N}}$ is relatively compact, therefore we can find an element $x\in X$ and a subsequence such that $x_{n_k}\rightarrow x$, for which the liminf inequality yields

$$\begin{aligned} F(x)\le \liminf _{n\rightarrow \infty } F_n({\tilde{x}}_n)\le \liminf _{k\rightarrow \infty } F_{n_k}(x_{n_k})\le \limsup _{n\rightarrow \infty } F_n(x_{n}), \end{aligned}$$

where we employ the sequence

$$\begin{aligned} {\tilde{x}}_n := {\left\{ \begin{array}{ll} x_{n_k}&{}\text {if } n= n_k,\\ x&{}\text {else.} \end{array}\right. } \end{aligned}$$

Together with (20) we have that x is a minimizer of F and $\lim _{n\rightarrow \infty } F_n(x_n) = F(x)$. Since the above reasoning works for any subsequence converging to some element in X we have that every cluster point is a minimizer. $\square $

A condition that ensures the existence of a relatively compact sequence of minimizers is the so-called compactness property for functionals. A sequence of functionals is called compact if for any sequence $\left( x_{n}\right) _{n\in \mathbb {N}}\subset X$ the property

$$\begin{aligned} \sup _{n\in \mathbb {N}} F_n(x_n) <\infty \end{aligned}$$

implies that $(x_n)_{n\in \mathbb {N}}$ is relatively compact. In Sect. 4 we show that the constrained functionals $E_{n,\mathrm {cons}}$ fulfill the compactness property. This strategy is standard in the context of continuum limits and has already been employed in [22, 36].

2.2 The Closest Point Projection

In [22, 36] a map $T_n:\varOmega \rightarrow \varOmega _n$ is employed in order to transform integrals w.r.t. the empirical measure, defined as

$$\begin{aligned} \nu _n(A) := \frac{1}{\left| \varOmega _n\right| } \sum _{x\in \varOmega _n} \delta _x(A),\quad A\in {\mathcal {B}}(\varOmega ), \end{aligned}$$

(21)

into integrals w.r.t. a probability measure $\nu \in {\mathcal {P}}({{\overline{\varOmega }}})$. Here, ${\mathcal {B}}(\varOmega )$ denotes the Borel $\sigma $-algebra and ${\mathcal {P}}({\overline{\varOmega }})$ is the set of probability measures on $\varOmega $. One assumes the push-forward condition

$$\begin{aligned} \nu _n = T_{n\#}\nu = \nu \circ T_n^{-1}, \end{aligned}$$

which yields the following transformation,

$$\begin{aligned} \sum _{x\in \varOmega _n} \mathbf {u}(x) = \int _{\varOmega } \mathbf {u}(x)~\mathrm {d}\nu _n(x) = \int _{\varOmega } \mathbf {u}(T_n(x))~\mathrm {d}\nu (x), \end{aligned}$$

for a function $\mathbf {u}:\varOmega _n\rightarrow \mathbb {R}$, see, for example, [6]. Informally speaking the push-forward condition manifests the intuition that the map $T_n$ has to preserve the weighting imposed by the empirical measure $\nu _n$. However, the supremal functionals in our case only take into account whether a respective set has positive measure or is a null set. Therefore, the assumptions on the map $T_n$ can be weakened for an analogous transformation rule. In fact, we only need that the push-forward measure is equivalent to the original one.

Lemma 2

For two probability measures $\mu ,\nu \in {\mathcal {P}}({\overline{\varOmega }})$, a measurable map $T:\varOmega \rightarrow \varOmega $ which fulfills

(i)

$\nu<<T_{\#}\mu $,

(ii)

$T_{\#}\mu<<\nu $,

and for a measurable function $f:\varOmega \rightarrow \mathbb {R}$ we have that

$$\begin{aligned} \nu {\text {-}}{{\,\mathrm{ess\,sup}\,}}_{x\in \varOmega } f(x) = \mu {\text {-}}{{\,\mathrm{ess\,sup}\,}}_{y\in \varOmega } f(T(y)). \end{aligned}$$

Remark 4

In the case $\nu =\nu _n$ we observe that assumption (i) is equivalent to

$$\begin{aligned} \mu (T^{-1}(x))>0 \end{aligned}$$

(22)

for all $x\in \varOmega _n$. Furthermore, assumption (ii) is a generalization of the property that $T(\varOmega )\subset \varOmega _n$. If (i) and (ii) are fulfilled we call the measures $\nu $ and $T_{\#}\mu $ equivalent. Additionally, the statement still holds true for a finite measure $\mu $ and a general measure $\nu $. However, for our application it suffices to consider probability measures.

Proof

First we consider a set $A\in {\mathcal {B}}(\varOmega )$ such that $\nu (A)=0$. For this we have that

$$\begin{aligned} \sup _{x\in \varOmega {\setminus } A} f(x) \ge \sup _{y\in T^{-1}(\varOmega {\setminus } A)} f(T(y)) = \sup _{y\in \varOmega {\setminus } T^{-1}(A)} f(T(y))=(\#) \end{aligned}$$

and since $\nu (A)=0$ we can use (ii) to infer that $\mu (T^{-1}(A))=0$. This implies that

$$\begin{aligned} (\#)\ge \inf _{\mu (B)=0} \sup _{y\in \varOmega {\setminus } B} f(T(y)) = \mu {\text {-}}{{\,\mathrm{ess\,sup}\,}}_{y\in \varOmega } f(T(y)). \end{aligned}$$

The null set A was arbitrary and thus taking the infimum over all $\nu $-null sets we obtain

$$\begin{aligned} \nu {\text {-}}{{\,\mathrm{ess\,sup}\,}}_{x\in \varOmega } f(x) \ge \mu {\text {-}}{{\,\mathrm{ess\,sup}\,}}_{x\in \varOmega } f(T(y)). \end{aligned}$$

On the other hand take $B\in {\mathcal {B}}(\varOmega )$ such that $\mu (B)=0$ then

$$\begin{aligned} \sup _{y\in \varOmega {\setminus } B} f(T(y))= \sup _{x\in T(\varOmega {\setminus } B)} f(x) \end{aligned}$$

and since $T^{-1}(T(\varOmega {\setminus } B))\supset \varOmega {\setminus } B$ we have that

$$\begin{aligned} 1\ge&\mu (T^{-1}(T(\varOmega {\setminus } B)))\ge \mu (\varOmega {\setminus } B) = 1\\ \Rightarrow&\mu (\varOmega {\setminus } T^{-1}(T(\varOmega {\setminus } B)))=0\\ \Rightarrow&\nu (\varOmega {\setminus }(T(\varOmega {\setminus } B)))=0. \end{aligned}$$

This implies that

$$\begin{aligned} \sup _{x\in T(\varOmega {\setminus } B)} f(x)\ge \inf _{\nu (A)=0}\sup _{x\in \varOmega {\setminus } A} f(x) = \nu {\text {-}}{{\,\mathrm{ess\,sup}\,}}_{x\in \varOmega } f(x). \end{aligned}$$

Taking the infimum overall $\mu $-null sets completes the proof. $\square $

An important type of mapping $T_n$ in our context is the so-called closest point projection.

Definition 2

(Closest Point Projection) For a finite set of points $\varOmega _n\subset \varOmega $ a map $p_n:\varOmega \rightarrow \varOmega _n$ is called closest point projection if

$$\begin{aligned} p_n(x)\in {{\,\mathrm{arg\,min}\,}}_{y\in \varOmega _n}\left| x-y\right| \end{aligned}$$

for each $x\in \varOmega $.

Remark 5

Recalling the standard definition of a Voronoi tessellation (see, e.g., [29]) one notices that the control volume associated with the vertex $x_i\in \varOmega _n$ is given by $\mathrm {int}(p_n^{-1}(x_i))$.

The use of a closest point projection is very natural for $L^{\infty }$-type scenarios and has, for example, already been employed in [14] for a similar problem. In particular, we can see that $\lambda ^{d}(p_n^{-1}(x_i)) >0$ for every vertex $x_i\in \varOmega _n$ and thus $\nu _n<<p_{n\#}\lambda ^{d}$, where $\lambda ^d$ denotes the $d$-dimensional Lebesgue measure. The second condition $p_{n\#}\lambda ^{d}<<\nu _n$ follows directly from the definition of the map $p_n$ and thus the conditions for Lemma 2 are fulfilled. In fact, for each function $u\in L^{\infty }(\varOmega )$ such that $u = \mathbf {u} \circ p_n$ for some $\mathbf {u}:\varOmega _n\rightarrow \mathbb {R}$ we can employ Lemma 2 to reformulate the extension (5) of the discrete functional as follows,

$$\begin{aligned} E_n(u)&= E_n(\mathbf {u}) \nonumber \\ \nonumber&= \frac{1}{s_n}\max _{x,y\in \varOmega _n} \eta _{s_n}(\left| x-y\right| ) \left| \mathbf {u}(x)-\mathbf {u}(y)\right| \nonumber \\ \nonumber&= \frac{1}{s_n} \nu _n{\text {-}}{{\,\mathrm{ess\,sup}\,}}_{x,y\in \varOmega } \eta _{s_n}(\left| x-y\right| ) \left| \mathbf {u}(x)-\mathbf {u}(y)\right| \nonumber \\&=\frac{1}{s_n}{{\,\mathrm{ess\,sup}\,}}_{x,y\in \varOmega } \eta _{s_n}(\left| p_n(x)-p_n(y)\right| ) \left| u(x)-u(y)\right| . \end{aligned}$$

(23)

Note that the weights consider the distance between the nearest vertices to x and y, respectively, and not the Euclidean distance between x and y. This observation is important for the estimate in Sect. 3.2.

3 $\varGamma $-Convergence of Lipschitz Functionals

3.1 Non-local to Local Convergence

In this section we show the $\varGamma $-convergence of the non-local functionals (19) to the continuum functional defined in (9) with respect to the $L^{\infty }$ topology. We first prove the liminf inequality.

Lemma 3

(liminf inequality) Let $\varOmega \subset \mathbb {R}^{d}$ be an open domain and let the kernel fulfill (K1)–(K3), then for a null sequence $\left( s_{n}\right) _{n\in \mathbb {N}}\subset (0,\infty )$ we have

$$\begin{aligned} \liminf _{n\rightarrow \infty }{\mathcal {E}}_{s_n}(u_n) \ge \sigma _{\eta }~{\mathcal {E}}(u) \end{aligned}$$

(24)

for every sequence $\left( u_{n}\right) _{n\in \mathbb {N}}\subset L^{\infty }(\varOmega )$ converging to $u\in L^{\infty }(\varOmega )$ in $L^{\infty }(\varOmega )$.

Proof

We assume w.l.o.g. that

$$\begin{aligned} \liminf _{n\rightarrow \infty }{\mathcal {E}}_{s_n}(u_n) < \infty . \end{aligned}$$

(25)

We choose a vector $h \in \mathbb {R}^{d}$ and estimate the supremum over $x,y\in \varOmega $ by a supremum over a difference quotient, namely

$$\begin{aligned} {\mathcal {E}}_{s_n}(u_n)= & {} {{\,\mathrm{ess\,sup}\,}}_{x,y\in \varOmega } \eta _{s_n}(\left| x-y\right| )~ \frac{\left| u_n(x) - u_n(y)\right| }{s_n} \\\ge & {} \eta (\left| h\right| )~{{\,\mathrm{ess\,sup}\,}}_{x\in \varOmega } \frac{\left| u_n(x) - u_n(x + s_n h)\right| }{s_n}~\mathbb {I}_\varOmega (x+s_n h). \end{aligned}$$

In the above transformation we ensured to not enlarge the supremum by multiplying by the indicator function. Considering the function

$$\begin{aligned} v_n^h(x):= \frac{u_n(x) - u_n(x + s_n h)}{s_n}~\mathbb {I}_\varOmega (x+s_n h) \end{aligned}$$

for $\eta (\left| h\right| )>0$ we have that

$$\begin{aligned} \liminf _{n\rightarrow \infty }\left\| v_n^h\right\| _{L^{\infty }}\le C \end{aligned}$$

which follows directly form (25). Thus, by the sequential Banach–Alaoglu theorem, the sequence $(v_n^h)_{n\in \mathbb {N}}$ possesses convergent subsequences. For any such subsequence $(v_{n_k}^h)_{k\in \mathbb {N}}$ there exists $v^h\in L^{\infty }$ such that

$$\begin{aligned} v_{n_k}^h \rightharpoonup ^*v^h \end{aligned}$$

in the $\hbox {weak}^{*}$ topology of $L^{\infty }$, i.e., for every $w\in L^{1}(\varOmega )$ we have

$$\begin{aligned} \int _{\varOmega } v_{n_k}^h~w~\mathrm {d}x \rightarrow \int _{\varOmega } v^h~w~\mathrm {d}x. \end{aligned}$$

(26)

We want to identify the function $v^h$, for which we use a smooth function $\phi \in C_c^\infty (\varOmega )$ as the test function in (26). We shift the difference quotient of $u_n$ to a quotient of $\phi $ and hope to obtain the directional derivative in the limit. Since $\mathrm {supp}(\phi )\subset \subset \varOmega $, we can choose $n_0$ large enough such that

$$\begin{aligned} x+s_n h\in \varOmega \end{aligned}$$

for all $n\ge n_0$ and for all $x\in \mathrm {supp}(\phi )$. Therefore, we get

$$\begin{aligned} \int _{\varOmega } v_{n_k}^h(x)~\phi (x)~\mathrm {d}x&= \int _{\varOmega } \frac{u_n(x) - u_n(x + s_n h(x))}{s_n}~\phi (x)~\mathrm {d}x\\ {}&= \int _{\varOmega } u_n(x)~ \frac{\phi (x) - \phi (x - s_n h)}{s_n} ~\mathrm {d}x. \end{aligned}$$

Furthermore, for $n\ge n_0$ we have

$$\begin{aligned}&\left| u_n(x)~\frac{\phi (x) - \phi (x - s_n h)}{s_n} - u(x) \nabla {\phi }(x)\cdot (-h)\right| \\&\le \left\| u_n-u\right\| _{L^{\infty }}~\left| \frac{\phi (x) - \phi (x - s_n h)}{s_n}\right| \\&\qquad + \left\| u\right\| _{L^{\infty }} \left| \frac{\phi (x) - \phi (x - s_n h)}{s_n} -\nabla {\phi }(x)\cdot (-h)\right| \\&\le \left| h\right| \left\| u_n-u\right\| _{L^{\infty }}\left\| \nabla {\phi }\right\| _{L^{\infty }}\\&\qquad + \left\| u\right\| _{L^{\infty }} \left| \frac{\phi (x) - \phi (x - s_n h)+\nabla {\phi }(x)\cdot (s_nh)}{s_n}\right| \xrightarrow {n\rightarrow \infty } 0, \end{aligned}$$

since $u_n$ converges to u in $L^{\infty }$, $\phi \in C^\infty _c$ has a bounded gradient, and since the difference quotient converges to the directional derivative. Besides the pointwise convergence, we also easily obtain the boundedness of the function sequence, since

$$\begin{aligned} \left| u_n(x)~\frac{\phi (x) - \phi (x - s_n h)}{s_n}\right|&\le \left| h\right| \left\| u_n\right\| _{L^{\infty }}~\left\| \nabla {\phi }\right\| _{L^{\infty }}\\&\le \left| h\right| (\left\| u_n-u\right\| _{L^{\infty }}+\left\| u\right\| _{L^{\infty }})~\left\| \nabla {\phi }\right\| _{L^{\infty }}, \end{aligned}$$

which is uniformly bounded. Thus, we can apply Lebesgue’s convergence theorem to see that

$$\begin{aligned} \int _{\mathbb {R}^{d}} v^h~\phi ~\mathrm {d}x = \lim _{k\rightarrow \infty }\int _{\varOmega } v_{n_k}^h~\phi ~\mathrm {d}x = -\int _{\mathbb {R}^{d}} u~(\nabla {\phi }\cdot h)~\mathrm {d}x. \end{aligned}$$

In particular, we can choose $h_i=c\,e_i$, where $e_i$ denotes the ith unit vector and the constant $c>0$ is small enough to ensure that $\eta (\left| h_i\right| )>0$, to obtain

$$\begin{aligned} \int _{\mathbb {R}^{d}} v^{h_i}~\phi ~\mathrm {d}x&= -c\int _{\mathbb {R}^{d}} u~\partial _i \phi ~\mathrm {d}x \end{aligned}$$

for all $i\in \{1,\ldots ,d\}$ and all $\phi \in C^\infty _c(\varOmega )$. This yields that $u\in W^{1,\infty }(\varOmega )$ and again for any h such that $\eta (\left| h\right| )>0$

$$\begin{aligned} \int _{\mathbb {R}^{d}} v^h~\phi ~\mathrm {d}x = \int _{\mathbb {R}^{d}} (\nabla {u}\cdot h)~\phi ~\mathrm {d}x. \end{aligned}$$

Using the density of $C^\infty _c(\varOmega )$ in $L^{1}(\varOmega )$ w.r.t. $\left\| \cdot \right\| _{L^{1}}$ we obtain that

$$\begin{aligned} \int _{\mathbb {R}^{d}} v^h~w~\mathrm {d}x = \int _{\mathbb {R}^{d}} (\nabla {u}\cdot h)~w~\mathrm {d}x \end{aligned}$$

for any $w\in L^{1}(\varOmega )$. Since the limit is independent of the subsequence $v_{n_k}^h$, we obtain that the $\hbox {weak}^{*}$ convergence holds for the whole sequence, i.e., $v_{n}^h \rightharpoonup ^*\nabla u\cdot h$ and thus together with the lower semi-continuity of $\left\| \cdot \right\| _{L^{\infty }}$

$$\begin{aligned} \liminf _{n\rightarrow \infty }{\mathcal {E}}_{s_n}(u_n) \ge \eta (\left| h\right| )~\liminf _{n\rightarrow \infty }\left\| v_{n}^h\right\| _{L^{\infty }} \ge \eta (\left| h\right| )~\left\| \nabla {u}\cdot h\right\| _{L^{\infty }}, \end{aligned}$$

for every $h\in \mathbb {R}^d$ such that $\eta (\left| h\right| )>0$. Since the inequality is trivially true for $\eta (\left| h\right| )=0$ we obtain

$$\begin{aligned} \liminf _{n\rightarrow \infty }{\mathcal {E}}_{s_n}(u_n) \ge \sup _{h\in \mathbb {R}^{d}}\eta (\left| h\right| )\left\| \nabla {u}\cdot h\right\| _{L^{\infty }}. \end{aligned}$$

Considering $z\in \varOmega $ such that $\nabla u(z)$ exists and satisfies $\left| \nabla {u}(z)\right| >0$, and taking $t\ge 0$ we have that

$$\begin{aligned} \sup _{h\in \mathbb {R}^{d}}\eta (\left| h\right| )~\left\| \nabla {u}\cdot h\right\| _{L^{\infty }} \ge \eta (t)\, \left\| \nabla {u}\cdot t\frac{\nabla {u}(z)}{\left| \nabla {u}(z)\right| }\right\| _{L^{\infty }}\ge \eta (t)\,t\,{\left| \nabla {u}(z)\right| }. \end{aligned}$$

This inequality holds for every $t\ge 0$ and almost every $z\in \varOmega $, since it is again trivially fulfilled if $\nabla u(z)$ exists and is equal to zero. Hence, we obtain

$$\begin{aligned} \liminf _{n\rightarrow \infty }{\mathcal {E}}_{s_n}(u_n) \ge \sigma _\eta ~{\mathcal {E}}(u) \end{aligned}$$

which concludes the proof. $\square $

We proceed by proving the limsup inequality. The most important fact here is that for $u\in W^{1,\infty }(\varOmega )$ and for almost every $x,y\in \varOmega $ we have the inequality

$$\begin{aligned} \left| u(x)-u(y)\right| \le \left\| \nabla {u}\right\| _{L^{\infty }} d_{\varOmega }(x,y), \end{aligned}$$

(27)

where $d_{\varOmega }(\cdot ,\cdot )$ denotes the geodesic distance on $\varOmega $, see [9, P. 269]. Since the non-local functional ${\mathcal {E}}_s$ compares points $x,y\in \varOmega $ that are close together w.r.t. the Euclidean distance, we need to asymptotically bound the geodesic distance from above by the Euclidean distance. For this, we assume condition (11), which we repeat here for convenience:

$$\begin{aligned} \lim _{\delta \downarrow 0}\sup \left\{ \frac{d_\varOmega (x,y)}{\left| x-y\right| }\,:\,x,y\in \varOmega ,\,\left| x-y\right| <\delta \right\} \le 1. \end{aligned}$$

Lemma 4

(limsup inequality) Let $\varOmega \subset \mathbb {R}^{d}$ be a domain satisfying (11), $\left( s_{n}\right) _{n\in \mathbb {N}}\subset (0,\infty )$ a null sequence and let the kernel fulfill (K1)–(K3), then for each $u\in L^{\infty }(\varOmega )$ there exists a sequence $\left( u_{n}\right) _{n\in \mathbb {N}}\subset L^{\infty }(\varOmega )$ converging to u strongly in $L^{\infty }(\varOmega )$ such that

$$\begin{aligned} \limsup _{n\rightarrow \infty }{\mathcal {E}}_{s_n}(u_n) \le \sigma _\eta ~{\mathcal {E}}(u). \end{aligned}$$

(28)

Proof

If $u\notin W^{1,\infty }$ the inequality holds trivially. If $u\in W^{1,\infty }$ we see that

$$\begin{aligned} {\mathcal {E}}_{s_n}(u)&= \frac{1}{s_n}~{{\,\mathrm{ess\,sup}\,}}_{x,y\in \varOmega } \left\{ \eta _{s_n}(\left| x-y\right| )\left| u(x) - u(y)\right| \right\} \\&\le \frac{1}{s_n}~{{\,\mathrm{ess\,sup}\,}}_{x,y\in \varOmega } \left\{ \eta _{s_n}(\left| x-y\right| )~d_{\varOmega }(x,y)\right\} ~ \left\| \nabla {u}\right\| _{L^{\infty }} \\&\le \frac{1}{s_n}~{{\,\mathrm{ess\,sup}\,}}_{x,y\in \varOmega } \left\{ \eta _{s_n}(\left| x-y\right| )~ \left| x-y\right| \frac{d_\varOmega (x,y)}{\left| x-y\right| }\right\} ~\left\| \nabla {u}\right\| _{L^{\infty }}. \end{aligned}$$

By (11), for any $\varepsilon >0$ we can find $\delta >0$ such that

$$\begin{aligned} \frac{d_\varOmega (x,y)}{\left| x-y\right| }\le 1+\varepsilon ,\quad \forall x,y\in \varOmega \,:\,\left| x-y\right| <\delta . \end{aligned}$$

Choosing $n\in \mathbb {N}$ so large that $c_\eta s_n<\delta $, where $c_\eta $ is the radius of the kernel $\eta $, we obtain

$$\begin{aligned} {\mathcal {E}}_{s_n}(u)&\le (1+\varepsilon ){{\,\mathrm{ess\,sup}\,}}_{x,y\in \varOmega } \left\{ \eta _{s_n} (\left| x-y\right| )\frac{\left| x-y\right| }{s_n} \right\} ~\left\| \nabla {u}\right\| _{L^{\infty }} \\&= (1+\varepsilon ){{\,\mathrm{ess\,sup}\,}}_{z\in \mathbb {R}^{d}} \left\{ \eta (\left| z\right| )\left| z\right| \right\} ~\left\| \nabla {u}\right\| _{L^{\infty }} \\&= (1+\varepsilon )~\sigma _\eta ~\left\| \nabla {u}\right\| _{L^{\infty }} = (1+\varepsilon )~{\sigma _\eta }\,{\mathcal {E}}(u). \end{aligned}$$

Since $\varepsilon >0$ was arbitrary, this shows that the constant sequence $u_n:=u$ fulfills the limsup inequality. $\square $

The previous lemmata directly imply the $\varGamma $-convergence of the respective functionals, which we state below.

Theorem 4

(Non-local to local $\varGamma $-convergence) Let $\varOmega \subset \mathbb {R}^{d}$ be a domain satisfying (11) and let the kernel fulfill (K1)–(K3), then for any null sequence $\left( s_{n}\right) _{n\in \mathbb {N}}\subset (0,\infty )$ we have that

$$\begin{aligned} {\mathcal {E}}_{s_n}\overset{\varGamma }{\longrightarrow }\sigma _{\eta }~{\mathcal {E}}. \end{aligned}$$

(29)

Remark 6

Assumption (11) is not satisfied for general non-convex domains, whereas

$$\begin{aligned} \left| u(x)-u(y)\right| \le {\text {Lip}}(u)\left| x-y\right| \end{aligned}$$

is. Hence, one might consider replacing the functional ${\mathcal {E}}(u)=\sigma _\eta \left\| \nabla {u}\right\| _{L^{\infty }}$ by ${\mathcal {E}}(u)=\sigma _\eta {\text {Lip}}(u)$ which allows to prove the limsup inequality for arbitrary (in particular, non-convex) domains. However, as the following example shows, the liminf inequality is not true for this functional and one has

$$\begin{aligned} \sigma _\eta \left\| \nabla {u}\right\| _{L^{\infty }}\le \liminf _{n\rightarrow \infty }{\mathcal {E}}_{s_n}(u_n)\le \limsup _{n\rightarrow \infty }{\mathcal {E}}_{s_n}(u_n) \le \sigma _\eta {\text {Lip}}(u) \end{aligned}$$

where each inequality can be strict.

Example 1

We consider the non-convex domain $\varOmega =\{x\in \mathbb {R}^2: \max (|x_1|,|x_2|) {<} 1\}{\setminus }\left( [0,1]\times [-1,0]\right) $ which does not satisfy (11), the function

$$\begin{aligned} u(x)= {\left\{ \begin{array}{ll} x_1^p \quad &{}\text {if } x_1,x_2 \ge 0,\\ x_2^p \quad &{}\text {if } x_1,x_2 \le 0,\\ 0 \quad &{}\text {else}, \end{array}\right. } \end{aligned}$$

for some power $p\ge 1$ and the kernel $\eta (t)=\chi _{[0,1]}(t)$ for $x\ge 0$. Then one can compute that

$$\begin{aligned} \left\| \nabla {u}\right\| _{L^{\infty }} =p ,\quad {\text {Lip}}(u) = \max (\sqrt{2},p), \quad \lim _{n\rightarrow \infty }{\mathcal {E}}_{s_n}(u) = {\left\{ \begin{array}{ll} \sqrt{2},\quad &{}p=1,\\ p,\quad &{}p>1. \end{array}\right. } \end{aligned}$$

The case $1<p<\sqrt{2}$ shows that the liminf inequality $\liminf _{n\rightarrow \infty }{\mathcal {E}}_{s_n}(u_n)\ge {\text {Lip}}(u)$ is false, in general.

Example 2

(The domain condition (11)) In this example we will study several scenarios where condition (11) is satisfied. Let us first remark that if one fixes $x\in \varOmega $ then

$$\begin{aligned} \lim _{\delta \downarrow 0}\sup \left\{ \frac{d_\varOmega (x,y)}{\left| x-y\right| }\,:\,y\in \varOmega ,\,\left| x-y\right| <{\delta }\right\} \le 1. \end{aligned}$$

is always true since $\varOmega $ is open. Hence, (11) is in fact a condition on the boundary of the domain.

If $\varOmega $ is convex, it holds $d_\varOmega (x,y)=\left| x-y\right| $ and hence (11) is trivially true.
If $\varOmega $ is locally $C^{1,1}$-diffeomorphic to a convex set, then (11) is satisfied as well. By this we mean that for all $x\in \varOmega $ there exists $\delta >0$, a convex set $C\subset \mathbb {R}^d$, and a diffeomorphism $\varPhi :C\rightarrow \mathbb {R}^d$ with inverse $\varPsi $ such that $B_\delta (x)\cap \varOmega = \varPhi (C)$. In particular, this includes domains with a sufficiently regular boundary. To see this let $x\in \varOmega $ and $y\in B_\delta (x)\cap \varOmega =\varPhi (C)$. Because C is convex, we can connect $\varPsi (x)$ and $\varPsi (y)$ with a straight line $\tau (t)=(1-t)\varPsi (x)+t\varPsi (y)$ for $t\in [0,1]$ and consider the curve $\gamma (t)=\varPhi (\tau (t))\subset \varPhi (C)$ which lies in $B_\delta (x)\cap \varOmega $ since $\tau $ lies in C. Hence,
$$\begin{aligned} d_\varOmega (x,y)&\le \mathrm {len}(\gamma ) = \int _0^1\left| {\dot{\gamma }}(t)\right| \mathrm {d}t \le \int _0^1 \left| \nabla {\varPhi }(\tau (t))\right| \left| {\dot{\tau }}(t)\right| \mathrm {d}t \\&= \int _0^1 \left| \nabla {\varPhi }(\tau (t))\right| \left| \varPsi (y)-\varPsi (x)\right| \mathrm {d}t \\&= \int _0^1 \left| \nabla {\varPhi }(\tau (t))\right| \left| \nabla {\varPsi }(x)\right| \left| x-y\right| \mathrm {d}t + o(\left| x-y\right| ) \\&\le \int _0^1 \left| \nabla {\varPhi }(\tau (t))\right| \left| \nabla {\varPsi }(\gamma (t))\right| \left| x-y\right| \mathrm {d}t \\&\qquad + \int _0^1 \left| \nabla {\varPhi }(\tau (t))\right| \left| \nabla {\varPsi }(\gamma (t))-\nabla {\varPsi }(x)\right| \left| x-y\right| \mathrm {d}t + o(\left| x-y\right| ) \\&\le \left| x-y\right| + c\left| x-y\right| \int _0^1 \left| \nabla {\varPhi }(\tau (t))\right| \left| \gamma (t)-x\right| \mathrm {d}t + o(\left| x-y\right| ) \\&= \left| x-y\right| + c\left| x-y\right| \int _0^1 \left| \nabla {\varPhi }(\tau (t))\right| \\&\quad \times \left| \varPhi (\tau (t))-\varPhi (\varPsi (x))\right| \mathrm {d}t + o(\left| x-y\right| ) \\&\le \left| x-y\right| + c\left| x-y\right| \int _0^1 \left| \tau (t)-\varPsi (x)\right| \mathrm {d}t + o(\left| x-y\right| ) \\&= \left| x-y\right| + c\left| x-y\right| \left| \varPsi (y)-\varPsi (x)\right| \int _0^1 t\mathrm {d}t + o(\left| x-y\right| ) \\&\le \left| x-y\right| + c\left| x-y\right| ^2 + o(\left| x-y\right| ), \end{aligned}$$
where we used Lipschitz continuity of $\varPhi ,\varPsi $ and $\nabla {\varPsi }$ and the fact that $\varPhi $ is a diffeomorphism which implies $\nabla \varPhi (\tau (t))=(\nabla \varPsi (\gamma (t)))^{-1}$. Note that the constant $c>0$ is changing with every inequality. Dividing by $\left| x-y\right| $ and letting $\left| x-y\right| \rightarrow 0$, we finally get (11).

3.2 Discrete to Continuum Convergence

We now consider the $\varGamma $-convergence of the discrete functionals. While in the previous section we employed an arbitrary null sequence $\left( s_{n}\right) _{n\in \mathbb {N}}\subset (0,\infty )$ for the scaling, we are now limited to certain scaling sequences depending on the sequence of sets $\varOmega _n$. In particular, we have to control how fast the scaling $s_n$ tends to zero in comparison with how fast the points in $\varOmega _n$ fill out the domain $\varOmega $. The following simple example illustrates why we have to consider the relationship between $s_n$ and $\varOmega _n$.

Example 3

Let $\left( x_{n}\right) _{n\in \mathbb {N}}\subset \mathbb {R}^{d}$ be an arbitrary sequence of points, then we can choose $s_n$ small enough such that $\eta _{s_n}(\left| x-y\right| ) =0$ for $x,y \in \varOmega _n$ and thus we have that $E_n(u_n)=0$ for every $n\in \mathbb {N}$. In this situation the liminf inequality does not hold true.

As illustrated in the example above, we need to take special care of points $x,y\in \varOmega _n$, where $\eta _{s_n}(\left| x-y\right| )=0$. Formulating this problem in terms of the map $p_n$ we have to consider the case where

$$\begin{aligned} \eta _{s_n}(\left| p_n(x)-p_n(y)\right| )=0. \end{aligned}$$

Using that the kernel has radius $c_\eta <\infty $ it follows that $\left| p_n(x)-p_n(y)\right| >c_\eta s_n$ and thus

$$\begin{aligned} \begin{aligned} \left| x-y\right|&= \left| x-p_n(x)+p_n(x)-p_n(y)+p_n(y)-y\right| \\ {}&\ge \left| p_n(x)-p_n(y)\right| -2\left\| {\text {Id}}- p_n\right\| _{L^{\infty }}\\&> c_\eta s_n-2\left\| {\text {Id}}- p_n\right\| _{L^{\infty }}=:c_\eta {\tilde{s}}_n. \end{aligned} \end{aligned}$$

The idea now is to use this new scaling ${\tilde{s}}_n$ for the non-local functionals, where we have to impose that ${\tilde{s}}_n >0$ for all n large enough. But more importantly we must ensure that the quotient ${\tilde{s}}_n/s_n$ converges to 1, i.e.,

$$\begin{aligned} \frac{{{\tilde{s}}}_n}{s_n}= \frac{s_n-2\left\| {\text {Id}}- p_n\right\| _{L^{\infty }}/c_\eta }{s_n}= 1-\frac{2\left\| {\text {Id}}- p_n\right\| _{L^{\infty }}/c_\eta }{s_n} \longrightarrow 1, \end{aligned}$$

which is equivalent to the fact that

$$\begin{aligned} \frac{\left\| {\text {Id}}- p_n\right\| _{L^{\infty }}}{s_n}\longrightarrow 0. \end{aligned}$$

This argumentation was first applied in [22], where instead of the map $p_n$ an optimal transport map $T_n$ was employed. For a closest point projection $p_n$ we know that

$$\begin{aligned} \left\| {\text {Id}}- p_n\right\| _{L^{\infty }} = \sup _{x\in \varOmega } \mathrm {dist}(x, \varOmega _n)=r_n. \end{aligned}$$

which thus yields the scaling assumption (8).

Lemma 5

(liminf inequality) Let $\varOmega \subset \mathbb {R}^{d}$ be a domain, let the constraint sets satisfy (3), and let the kernel fulfill (K1)–(K3), then for any null sequence $\left( s_{n}\right) _{n\in \mathbb {N}}\subset (0,\infty )$ which satisfies the scaling condition (8) we have that

$$\begin{aligned} \liminf _{n\rightarrow \infty }E_{n,\mathrm {cons}}(u_n) \ge \sigma _{\eta }~{\mathcal {E}}_\mathrm {cons}(u) \end{aligned}$$

for every sequence $\left( u_{n}\right) _{n\in \mathbb {N}}\subset L^{\infty }(\varOmega )$ converging to $u\in L^{\infty }(\varOmega )$ in $L^{\infty }(\varOmega )$.

Proof

W.l.o.g. we assume that $\liminf _{n\rightarrow \infty }E_{n,\mathrm {cons}}(u_n) <\infty $. After possibly passing to a subsequence, we can, furthermore, assume that $u_n=g$ on ${\mathcal {O}}_n$. We first show that the limit function u satisfies $u=g$ on ${\mathcal {O}}$.

Since $\eta $ is continuous and positive in 0, we know that there exists $0<t<c_\eta $ such that $\eta (s)>C$ for all $0<s<t$ where $C>0$. Furthermore, using (3) we infer that for all $x\in {\mathcal {O}}$ there exists $x_n\in {\mathcal {O}}_n$ with $|x-x_n|=o(s_n)$. In particular, for n large enough it holds $\left| x-x_n\right| \le s_nt$. This allows us to estimate:

$$\begin{aligned} \left| u(x)-g(x)\right|&\le \left| u(x)-u_n(x)\right| + \left| u_n(x)-u_n(x_n)\right| \\&\quad + \left| u_n(x_n)-g(x_n)\right| + \left| g(x_n) - g(x)\right| \\&\le \left\| u-u_n\right\| _{L^{\infty }(\varOmega )} + \frac{1}{C}\eta (\left| x-x_n\right| )\left| u_n(x)-u_n({x_n})\right| \\&\quad + 0 + {\text {Lip}}(g)\left| x-x_n\right| \\&\le \left\| u-u_n\right\| _{L^{\infty }(\varOmega )} + \frac{s_n}{C} E_{n,\mathrm {cons}}(u_n) + {\text {Lip}}(g)\left| x-x_n\right| \\&\le \left\| u-u_n\right\| _{L^{\infty }(\varOmega )} + \frac{s_n}{C} E_{n,\mathrm {cons}}(u_n) + {\text {Lip}}(g) s_n\,{t}. \end{aligned}$$

Taking $n\rightarrow \infty $, using that $E_{s_n}(u_n)$ is uniformly bounded and $s_n\rightarrow 0$, we obtain $u=g$ on ${\mathcal {O}}$.

The main idea for proving the liminf inequality here is to establish a discrete to non-local control estimate and then use Lemma 3.

Since we assumed $\liminf _{n\rightarrow \infty }E_{n,\mathrm {cons}}(u_n) <\infty $, we know that $u_n$ is piecewise constant for every $n\in \mathbb {N}$, in the sense of Sect. 1.1, i.e., $u_n=\mathbf {u}_n \circ p_n$ for some $\mathbf {u}_n:\varOmega _n\rightarrow \varOmega $. As shown in (23) we can express $E_{n,\mathrm {cons}}$ as follows:

$$\begin{aligned} E_{n,\mathrm {cons}}(u_n) =\frac{1}{s_n}{{\,\mathrm{ess\,sup}\,}}_{x,y \in \varOmega }\eta _{s_n}(\left| p_n(x)-p_n(y)\right| ) \left| u_n(x) - u_n(y)\right| =(\#). \end{aligned}$$

In order to apply Lemma 3, we need to transform the weighting that considers the distance between $p_n(x)$ and $p_n(y)$ into another one that measures the distance between x and y.

Case 1 There exists $t>0$ such that $\eta $ is constant on [0, t].

We employ the observation that whenever $\left| p_n(x)-p_n(y)\right| >s_n\,t$, for the new scaling ${\tilde{s}}_n:=s_n-2r_n/t$ we have

$$\begin{aligned} \frac{\left| x-y\right| }{{\tilde{s}}_n}&\ge \frac{\left| p_n(x)-p_n(y)\right| -2 r_n}{s_n-2r_n/t}\\ {}&= \frac{\left| p_n(x)-p_n(y)\right| }{s_n} \underbrace{\frac{1 -2 r_n/\left| p_n(x)-p_n(y)\right| }{1-2r_n/(ts_n)}}_{>1}\\ {}&> \frac{\left| p_n(x)-p_n(y)\right| }{s_n}, \end{aligned}$$

where we used that $r_n=\left\| {\text {Id}}-p_n\right\| _{L^{\infty }}$. Since $\eta $ is non-increasing (K2) and $\eta $ is constant on [0, t), we get

$$\begin{aligned} \eta _{s_n}(\left| p_n(x)-p_n(y)\right| ) \ge \eta _{{\tilde{s}}_n}(\left| x-y\right| ) \end{aligned}$$

for almost all $x,y\in \varOmega $. This allows us to further estimate

$$\begin{aligned} (\#) \ge \frac{1}{s_n}{{\,\mathrm{ess\,sup}\,}}_{x,y \in \varOmega } \eta _{{\tilde{s}}_n}(\left| x-y\right| ) \left| u_n(x) - u_n(y)\right| = \frac{{\tilde{s}}_n}{s_n}~{\mathcal {E}}_{{\tilde{s}}_n}(u_n). \end{aligned}$$

Together with the assumption $r_n/s_n\rightarrow 0$ we obtain that ${\tilde{s}}_n>0$ for n large enough and ${\tilde{s}}_n/s_n \rightarrow 1$ which finally justifies the application of Lemma 3, i.e.,

$$\begin{aligned} \liminf _{n\rightarrow \infty } E_{n,\mathrm {cons}}(u_n) \ge \liminf _{n\rightarrow \infty }\frac{{\tilde{s}}_n}{s_n}~ {\mathcal {E}}_{{\tilde{s}}_n}(u_n)\ge \sigma _{\eta }~{\mathcal {E}}(u)=\sigma _\eta ~{\mathcal {E}}_\mathrm {cons}(u). \end{aligned}$$

Case 2 We now assume the kernel to fulfill (K1)–(K3). The strategy is to find a $t>0$ where one can cut off the kernel without changing the value $\sigma _\eta $. From the continuity at $t=0$ (K1) we have that

$$\begin{aligned} \lim _{t\rightarrow 0} \eta (t)~t =0 \end{aligned}$$

and thus there exists a $t^*>0$ such that

$$\begin{aligned} \sup _{t\in [0,t^*]}\eta (t)~t\le \sigma _\eta . \end{aligned}$$

We define

$$\begin{aligned} {\tilde{\eta }}(t)= {\left\{ \begin{array}{ll} \eta (t)&{}\text { for } {t>t^*},\\ \eta (t^*)&{}\text { for }t\in [0,t^*], \end{array}\right. } \end{aligned}$$

for which we have $\sigma _{{\tilde{\eta }}}=\sigma _\eta $ and thus the first case applies. Namely, using that $\eta $ is non-increasing (K2) and hence $\eta \ge {{\tilde{\eta }}}$ we obtain

$$\begin{aligned}&\liminf _{n\rightarrow \infty } E_{n,\mathrm {cons}}(u_n) \\&\quad \ge \liminf _{n\rightarrow \infty }\left( \frac{1}{s_n}{{\,\mathrm{ess\,sup}\,}}_{x,y \in \varOmega } {\tilde{\eta }}_{s_n}(\left| p_n(x)-p_n(y)\right| ) \left| u_n(x) - u_n(y)\right| \right) \\&\quad \ge \sigma _{\eta }~{\mathcal {E}}_\mathrm {cons}(u). \end{aligned}$$

$\square $

We now consider the limsup inequality for the constrained functionals.

Lemma 6

(limsup inequality) Let $\varOmega \subset \mathbb {R}^{d}$ be a domain satisfying (11) and let the kernel fulfill (K1)–(K3), then for a null sequence $\left( s_{n}\right) _{n\in \mathbb {N}}\subset (0,\infty )$ and a function $u\in L^{\infty }(\varOmega )$ there exists a sequence $\left( u_{n}\right) _{n\in \mathbb {N}}\subset L^{\infty }(\varOmega )$ converging to $u\in L^{\infty }(\varOmega )$ in $L^{\infty }(\varOmega )$ such that

$$\begin{aligned} \limsup _{n\rightarrow \infty } E_{n,\mathrm {cons}}(u_n) \le \sigma _\eta ~{\mathcal {E}}_{\mathrm {cons}}(u). \end{aligned}$$

Proof

If ${\mathcal {E}}_\mathrm {cons}(u)=\infty $ the inequality holds trivially. We thus consider $u\in W^{1,\infty }(\varOmega )$ such that $u(x)=g(x)$ for every $x\in {\mathcal {O}}$ and define a recovery sequence as follows: Let $\mathbf {u}_n \in L^{\infty }(\nu _n)$ be defined by

$$\begin{aligned} \mathbf {u}_n(x) = {\left\{ \begin{array}{ll} u(x), \quad &{}x \in \varOmega _n {\setminus } {\mathcal {O}}_n, \\ g(x), \quad &{}x \in {\mathcal {O}}_n, \end{array}\right. } \end{aligned}$$

and define $u_n:=\mathbf {u}_n \circ p_n$, where $p_n:\varOmega \rightarrow \varOmega _n$ denotes a closest point projection. Then $u_n\in L^{\infty }(\varOmega )$ and by definition it holds

$$\begin{aligned} E_{n,\mathrm {cons}}(u_n)=E_{n,\mathrm {cons}}(\mathbf {u}_n) = \frac{1}{s_n} \max _{x,y\in \varOmega _n}\eta _{s_n}(\left| x-y\right| )\left| \mathbf {u}_n(x)-\mathbf {u}_n(y)\right| . \end{aligned}$$

We have to distinguish three cases:

Case 1 Let $x,y\in \varOmega _n{\setminus }{\mathcal {O}}_n$, then we can compute, using (27)

$$\begin{aligned} \left| \mathbf {u}_n(x)-\mathbf {u}_n(y)\right| = \left| u(x)-u(y)\right| \le d_\varOmega (x,y)~\left\| \nabla {u}\right\| _{L^{\infty }} \end{aligned}$$

and therefore

$$\begin{aligned} \frac{1}{s_n}\eta _{s_n}(\left| x-y\right| ) \left| \mathbf {u}_n(x)-\mathbf {u}_n(y)\right|&\le \underbrace{ \eta _{s_n}(\left| x-y\right| )~\frac{\left| x-y\right| }{s_n} }_{\le \sigma _\eta } \frac{d_\varOmega (x,y)}{\left| x-y\right| }~ \left\| \nabla {u}\right\| _{L^{\infty }}\\ {}&\le \sigma _\eta ~\frac{d_\varOmega (x,y)}{\left| x-y\right| }~ \left\| \nabla {u}\right\| _{L^{\infty }}. \end{aligned}$$

Case 2 Let $x\in \varOmega _n{\setminus }{\mathcal {O}}_n$ and $y\in {\mathcal {O}}_n$. Then for every ${\tilde{y}}\in {\mathcal {O}}$ it holds, using (27)

$$\begin{aligned} \left| \mathbf {u}_n(x)-\mathbf {u}_n(y)\right|&= \left| u(x)-g(y)\right| \\&\le \left| u(x)-u({\tilde{y}})\right| + \underbrace{\left| u({\tilde{y}})-g({\tilde{y}})\right| }_{=0} + \left| g({\tilde{y}})-g(y)\right| \\&\le \left\| \nabla {u}\right\| _{L^{\infty }}\mathrm {d}_\varOmega (x,{\tilde{y}}) + {\text {Lip}}(g)\left| {\tilde{y}}-y\right| \\&\le \left\| \nabla {u}\right\| _{L^{\infty }}d_\varOmega (x,y) + \left\| \nabla {u}\right\| _{L^{\infty }}d_\varOmega (y,{\tilde{y}}) + {\text {Lip}}(g) \left| {\tilde{y}}-y\right| \\&\le \left\| \nabla {u}\right\| _{L^{\infty }} d_\varOmega (x,y) + \left\| \nabla {u}\right\| _{L^{\infty }} \frac{d_\varOmega (y,{\tilde{y}})}{\left| y-{\tilde{y}}\right| }\\&\qquad \left| y-{\tilde{y}}\right| + {\text {Lip}}(g)\left| y-{\tilde{y}}\right| . \end{aligned}$$

From this we have, using the same arguments as in the first case, that there is a $C>0$ such that

$$\begin{aligned} \frac{1}{s_n}\eta _{s_n}(\left| x-y\right| ) \left| \mathbf {u}_n(x)-\mathbf {u}_n(y)\right| \le \sigma _\eta ~\frac{d_\varOmega (x,y)}{\left| x-y\right| }~ \left\| \nabla {u}\right\| _{L^{\infty }} + C~\frac{\left| y-{\tilde{y}}\right| }{s_n}. \end{aligned}$$

Case 3 Let $x,y\in {\mathcal {O}}_n$, then for ${\tilde{x}},{\tilde{y}}\in {\mathcal {O}}$ we have

$$\begin{aligned} \left| \mathbf {u}_n(x)-\mathbf {u}_n(y)\right|&= \left| g(x)-g(y)\right| \\&= \left| g(x)-u({\tilde{x}})\right| + \left| u({\tilde{x}})-u({\tilde{y}})\right| + \left| u({\tilde{y}})-g(y)\right| \\&= \left| g(x)-g({\tilde{x}})\right| + \left| u({\tilde{x}})-u({\tilde{y}})\right| + \left| g({\tilde{y}})-g(y)\right| \\&\le {\text {Lip}}(g)\left| x-{\tilde{x}}\right| + \left\| \nabla {u}\right\| _{L^{\infty }} d_\varOmega ({\tilde{x}},{\tilde{y}}) + {\text {Lip}}(g)\left| y-{\tilde{y}}\right| \end{aligned}$$

and therefore again

$$\begin{aligned} \frac{1}{s_n}\eta _{s_n}(\left| x-y\right| ) \left| \mathbf {u}_n(x)-\mathbf {u}_n(y)\right|&\le \sigma _\eta ~\frac{d_\varOmega (x,y)}{\left| x-y\right| }~ \left\| \nabla {u}\right\| _{L^{\infty }} \\&\quad + {\text {Lip}}(g)~\left( \frac{\left| y-{\tilde{y}}\right| +\left| x-{\tilde{x}}\right| }{s_n}\right) . \end{aligned}$$

By (11) for every $\varepsilon >0$ there is $n_0\in \mathbb {N}$ sufficiently large such that for all $n\ge n_0$ it holds

$$\begin{aligned} \sigma _\eta ~\frac{d_\varOmega (x,y)}{\left| x-y\right| }~ \left\| \nabla {u}\right\| _{L^{\infty }} \le \sigma _\eta \left\| \nabla {u}\right\| _{L^{\infty }} + \varepsilon /2, \end{aligned}$$

whenever $\left| x-y\right| \le c_\eta s_n$. Additionally, thanks to (3) and the compactness of ${\mathcal {O}}_n$ and ${\mathcal {O}}$ for every $x\in {\mathcal {O}}_n$ we can choose ${\tilde{x}}\in {\mathcal {O}}$ such that

$$\begin{aligned} \frac{\left| x- {\tilde{x}}\right| }{s_n}\le \frac{\varepsilon }{4 \max \{C,{\text {Lip}}(g)\}} \end{aligned}$$

and analogously for y and ${\tilde{y}}$. Combining the estimates from all three cases, we obtain

$$\begin{aligned} E_{n,\mathrm {cons}}(u_n)&\le \max \left\{ \sigma _\eta \left\| \nabla {u}\right\| _{L^{\infty }} + \frac{\varepsilon }{2},\sigma _\eta \left\| \nabla {u}\right\| _{L^{\infty }} + \frac{3\varepsilon }{4},\sigma _\eta \left\| \nabla {u}\right\| _{L^{\infty }} + \varepsilon \right\} \\&=\sigma _\eta ~\left\| \nabla u\right\| _{L^{\infty }} + \varepsilon \end{aligned}$$

for all $n\ge n_0$. Finally, this yields

$$\begin{aligned} \limsup _{n\rightarrow \infty }E_{n,\mathrm {cons}}(u_n) \le \sigma _\eta ~{\mathcal {E}}_\mathrm {cons}(u), \end{aligned}$$

as desired.

For showing that $u_n\rightarrow u$ in $L^{\infty }(\varOmega )$ one proceeds similarly: If $p_n(x)\in \varOmega _n{\setminus }{\mathcal {O}}_n$ one has thanks to (27)

$$\begin{aligned} \left| u(x)-u_n(x)\right|&=\left| u(x)-u(p_n(x))\right| \le \left\| \nabla {u}\right\| _{L^{\infty }} d_\varOmega (x,p_n(x)) \\&=\left\| \nabla {u}\right\| _{L^{\infty }}\frac{d_\varOmega (x,p_n(x))}{\left| x-p_n(x)\right| }\left| x-p_n(x)\right| \rightarrow 0,\quad n\rightarrow \infty , \end{aligned}$$

where we also used (11) and $\left| x-p_n(x)\right| \le r_n\rightarrow 0$. In the case $p_n(x)\in {\mathcal {O}}_n$ by (3) one again finds ${\tilde{x}}\in {\mathcal {O}}$ such that $\left| p_n(x)-{\tilde{x}}\right| =o(s_n)$. Then by (27) and (11) we have

$$\begin{aligned} \left| u(x)-u_n(x)\right|&=\left| u(x)-g(p_n(x))\right| \\&\le \left| u(x)-u(p_n(x))\right| + |u(p_n(x))-\underbrace{g({\tilde{x}})}_{=u({\tilde{x}})}| +\left| g({\tilde{x}})-g(p_n(x))\right| \\ {}&\le { \left\| \nabla {u}\right\| _{L^{\infty }}\frac{d_\varOmega (p_n(x),x)}{\left| p_n(x)-x\right| }\left| p_n(x)-x\right| } \\&\qquad + \left\| \nabla {u}\right\| _{L^{\infty }}\frac{d_\varOmega (p_n(x),{\tilde{x}})}{\left| p_n(x)-{\tilde{x}}\right| }\left| p_n(x)-{\tilde{x}}\right| +{\text {Lip}}(g) \left| p_n(x)-{\tilde{x}}\right| \\&\rightarrow 0 \end{aligned}$$

since $\left| p_n(x)-x\right| \le r_n\rightarrow 0$ and $\left| p_n(x)-{\tilde{x}}\right| =o(s_n)\rightarrow 0$. Combining both cases proves $\left\| u-u_n\right\| _{L^{\infty }}\rightarrow 0$ as $n\rightarrow \infty $. $\square $

Remark 7

We note that the proof of the limsup inequality does not use any specific properties of the scaling, in fact even a sequence of disconnected graphs or the situation of Example 3 allows for such an inequality.

Remark 8

(Relevance of the Hausdorff convergence) The condition that the Hausdorff distance of ${\mathcal {O}}_n$ and ${\mathcal {O}}$ converges to zero as $n\rightarrow \infty $ (cf. (3)) implies both that ${\mathcal {O}}_n$ well approximates ${\mathcal {O}}$ and vice versa. The first condition is only used in the proof of the liminf inequality Lemma 5 whereas the second one only enters for the limsup inequality Lemma 6. Furthermore, the proof of the latter is drastically simplified if one assumes that ${\mathcal {O}}_n\subset {\mathcal {O}}$ for all $n\in \mathbb {N}$, which implies that the second term in the Hausdorff distance (3) equals zero. In this case, introducing the continuum points ${\tilde{x}},{\tilde{y}}\in {\mathcal {O}}$ is not necessary and many estimates in the previous proof become trivial.

Combining Lemmas 5 and 6 we immediately obtain the $\varGamma $-convergence of the discrete functionals to those defined in the continuum, which is the statement of Theorem 1.

Remark 9

(Homogeneous boundary conditions) In the case that ${\mathcal {O}}=\partial \varOmega $ and the constraints satisfy $g=0$ on ${\mathcal {O}}$ any function with ${\mathcal {E}}_\mathrm {cons}(u)<\infty $ satisfies $u\in W^{1,\infty }_0(\varOmega )$. For this it is well known that functions $u\in W^{1,\infty }_0(\varOmega )$ can be extended from $\varOmega $ to $\mathbb {R}^{d}$ by zero without changing $\left\| \nabla {u}\right\| _{L^{\infty }}$. In this case one can prove the limsup inequality Lemma 6 and hence also the $\varGamma $-convergence Theorem 1 for general open sets $\varOmega $ without demanding (11) or even convexity. For this one simply utilizes the estimate

$$\begin{aligned} \left| \mathbf {u}_n(x)-\mathbf {u}_n(y)\right| =\left| u(x)-u(y)\right| \le \left\| \nabla u\right\| _{L^{\infty }}\left| x-y\right| \end{aligned}$$

which is true if one extends u by zero on $\mathbb {R}^d{\setminus }\varOmega $, multiplies with the kernel, and takes the supremum.

4 Compactness

We now want to make use of Lemma 1 in order to characterize the behavior of minimizers of the discrete problems or more generally sequences of approximate minimizers, as described in the condition of the mentioned lemma. The first result is a general characterization of relatively compact sets in $L^{\infty }$, the proof uses classical ideas from [18, Lem. IV.5.4].

Lemma 7

Let $(\varOmega ,\mu )$ be a finite measure space and $K\subset L^{\infty }(\varOmega ;\mu )$ be a bounded set w.r.t. $\left\| \cdot \right\| _{L^{\infty }(\varOmega ;\mu )}$ such that for every $\varepsilon >0$ there exists a finite partition $\{V_i\}_{i=1}^n$ of $\varOmega $ into subsets $V_i$ with positive and finite measure such that

$$\begin{aligned} \mu {\text {-}}{{\,\mathrm{ess\,sup}\,}}_{x,y\in V_i} \left| u(x) - u(y)\right| < \varepsilon \ \forall u\in K, i=1,\ldots ,n, \end{aligned}$$

(30)

then K is relatively compact.

Proof

Let $\varepsilon >0$ be given and let $\{V_i\}_{i=1}^n$ be a partition into sets with finite and positive measure such that

$$\begin{aligned} \mu {\text {-}}{{\,\mathrm{ess\,sup}\,}}_{x,y\in V_i} \left| u(x) - u(y)\right| < \frac{\varepsilon }{3},\quad \ \forall u\in K,\; i=1,\ldots ,n. \end{aligned}$$

(31)

We define the operator ${\mathcal {T}}:L^{\infty }(\varOmega ;\mu )\rightarrow L^{\infty }(\varOmega ;\mu )$ as

$$\begin{aligned} ({\mathcal {T}}u)(x):= \frac{1}{\mu (V_i)}\int _{V_i} u(y)~\mathrm {d}\mu (y)\quad \text {for } x\in V_i, \end{aligned}$$

which is well defined thanks to $0<\mu (V_i)<\infty $ for all $i=1,\ldots ,n$. Using (31) we observe that for $\mu $-almost every $x\in V_i$

$$\begin{aligned} \left| u(x) - ({\mathcal {T}}u)(x)\right| \le \frac{1}{\mu (V_i)}\int _{V_i} \left| u(x)-u(y)\right| ~\mathrm {d}\mu (y) < \frac{\varepsilon }{3} \end{aligned}$$

and thus $\left\| u - {\mathcal {T}}u\right\| _{L^{\infty }(\varOmega ;\mu )}< \frac{\varepsilon }{3}$. Furthermore, ${\mathcal {T}}(K)\subset \text {span}(\{\mathbb {I}_{V_1},\ldots , \mathbb {I}_{V_n}\})$, where we let $\mathbb {I}_M$ denote the indicator function of a set M, defined by $\mathbb {I}_M(x)=0$ if $x\notin M$ and $\mathbb {I}_M(x)=1$ if $x\in M$. Hence, ${\mathcal {T}}$ has finite-dimensional range and since K is bounded we have

$$\begin{aligned} \left\| {\mathcal {T}}u\right\| _{L^{\infty }(\varOmega ;\mu )} \le \left\| u\right\| _{L^{\infty }(\varOmega ;\mu )} \le C\quad \forall u\in K \end{aligned}$$

and therefore ${\mathcal {T}}(K)$ is relatively compact. This implies that there exist finitely many functions $\{u_j\}_{j=1}^{N}\subset L^{\infty }(\varOmega ;\mu )$ such that

$$\begin{aligned} {\mathcal {T}}(K)\subset \bigcup _{j=1}^N B_{\frac{\varepsilon }{3}}({\mathcal {T}}(u_j)), \end{aligned}$$

where $B_t(u):=\{v\in L^{\infty }(\varOmega ;\mu )\;:\;\left\| u-v\right\| _{L^{\infty }(\varOmega ;\mu )}<t\}$ denotes the open ball with radius $t>0$ around $u\in L^{\infty }(\varOmega ;\mu )$. For $u\in K$ we can thus find $j\in \{1,\ldots ,N\}$ such that ${\mathcal {T}}(u)\in B_{\frac{\varepsilon }{3}}({\mathcal {T}}(u_j))$ and thus

$$\begin{aligned} \left\| u-u_j\right\| _{L^{\infty }} \le \left\| u - {\mathcal {T}}(u)\right\| _{L^{\infty }} + \left\| {\mathcal {T}}(u) - {\mathcal {T}}(u_j)\right\| _{L^{\infty }} + \left\| {\mathcal {T}}(u_j)-u_j\right\| _{L^{\infty }} < \varepsilon . \end{aligned}$$

This implies that K is totally bounded and since $L^{\infty }(\varOmega ;\mu )$ is complete the result follows from [18, Lem. I.6.15]. $\square $

The previous lemma allows us to prove a compactness result for the non-local functionals, where we again need the domain $\varOmega $ to fulfill condition (11).

Lemma 8

Let $\varOmega \subset \mathbb {R}^{d}$ be a bounded domain satisfying (11) and let the kernel $\eta $ fulfill (K1)–(K3), and let $\left( s_{n}\right) _{n\in \mathbb {N}}\subset (0,\infty )$ be a null sequence. Then every bounded sequence $\left( u_{n}\right) _{n\in \mathbb {N}}\subset L^{\infty }(\varOmega )$ such that

$$\begin{aligned} \sup _{n\in \mathbb {N}}{\mathcal {E}}_{s_n}(u_n)&<\infty \end{aligned}$$

(32)

is relatively compact.

Proof

We want to apply Lemma 7 in order to see that the sequence is relatively compact. Therefore, let $\varepsilon >0$ be given and w.l.o.g. we rescale the kernel such that

$$\begin{aligned} \eta (t)\ge 1\text { for }t\le 1. \end{aligned}$$

Using (11) we can find $\delta >0$ such that for every $x,y\in \varOmega $ with $\left| x-y\right| \le \delta $ there is a path $\gamma :[0,1]\rightarrow \varOmega $ such that $\gamma (0)=x, \gamma (1)=y$ and

$$\begin{aligned} \text {len}(\gamma )\le (1+\varepsilon )\left| x-y\right| . \end{aligned}$$

We divide this path by points $0=t_0<\cdots<t_i<\cdots <t_{k_n}=1$ such that for $z_i:=\gamma (t_i)$ we have that

$$\begin{aligned} \left| z_i-z_{i+1}\right| \le s_n \end{aligned}$$

for $i=0,\ldots , k_n$, where

$$\begin{aligned} k_n \le \lfloor (1+\varepsilon )~\left| x-y\right| /s_n \rfloor . \end{aligned}$$

Then we have that

$$\begin{aligned} \left| u_n(x)-u_n(y)\right|&\le \sum _{i=0}^{{k_n-1}} {\left| u_n(z_i) - u_n(z_{i+1})\right| } \\ {}&\le s_n~\sum _{i=0}^{{k_n-1}} \eta _{s_n}(\left| z_i-z_{i+1}\right| ) \frac{\left| u_n(z_i) - u_n(z_{i+1})\right| }{s_n}\\&\le s_n~\sum _{i=0}^{{k_n-1}} {\mathcal {E}}_{s_n}(u_n)\\ {}&\le s_n~k_n~\underbrace{\sup _{n\in \mathbb {N}}{\mathcal {E}}_{s_n}(u_n)}_{=:C<\infty }\\ {}&\le C~(1+\varepsilon )~ \left| x-y\right| . \end{aligned}$$

Choosing a partition $\{V_i\}_{i=1}^N$ of $\varOmega $ into sets with positive Lebesgue measure such that

$$\begin{aligned} \text {diam}(V_i)< \min \left\{ \delta , \frac{\varepsilon }{C~(1+\varepsilon )}\right\} \end{aligned}$$

for $i=1,\ldots ,N,$ yields that

$$\begin{aligned}&{{\,\mathrm{ess\,sup}\,}}_{x,y\in V_i} \left| u_n(x)- u_n(y)\right| \le C~(1+\varepsilon )~ {{\,\mathrm{ess\,sup}\,}}_{x,y\in V_i} \left| x-y\right| \\&\quad \le C~(1+\varepsilon )~\text {diam}(V_i) < \varepsilon . \end{aligned}$$

Since $\left( u_{n}\right) _{n\in \mathbb {N}}\subset L^{\infty }$ is bounded in $L^{\infty }$ we can therefore apply Lemma 7 to infer that the sequence is relatively compact. $\square $

We will use this result in order to prove that the constrained functionals $E_{n,\mathrm {cons}}$ are compact, which then directly shows Theorem 2. The intuitive reason that these functionals are compact is the fact that for a domain $\varOmega $ that fulfills (11) each point $x\in \varOmega _n$ has finite geodesic distance to the set ${\mathcal {O}}_n$. This follows from the fact that the geodesic diameter of $\varOmega $ is bounded, as we show in the following lemma.

Lemma 9

Condition (11) implies that the geodesic diameter is finite, i.e.,

$$\begin{aligned} {\text {diam}}_g(\varOmega ):=\sup _{x,y\in \varOmega }d_\varOmega (x,y) < \infty . \end{aligned}$$

(33)

Proof

For $\varepsilon >0$ we can use (11) to find $\delta >0$ such that $d_\varOmega (x,y)<\left| x-y\right| (1+\varepsilon )$ for all $x,y\in \varOmega $ with $\left| x-y\right| <\delta $. Since we assume $\varOmega $ to be bounded we know that there exists a finite collection $\{x_1,\ldots ,x_N\}\subset \varOmega $ such that

$$\begin{aligned} \varOmega \subset \bigcup _{i=1}^N B_\delta (x_i). \end{aligned}$$

If two balls at centers $x_i,x_j$ share a common point $z\in \varOmega $ we see that

$$\begin{aligned} \begin{aligned} d_\varOmega (x_i,x_j)&\le d_\varOmega (x_i,z)+d_\varOmega (z,x_j) \\ {}&\le (1+\varepsilon )\left| x_i - z\right| + (1+\varepsilon )\left| z - x_j\right| \\ {}&\le 2(1+\varepsilon )\delta . \end{aligned} \end{aligned}$$

(34)

For any $x,y\in \varOmega $ assume that there exists a path $\gamma $ in $\varOmega $ from x to y. Therefore, also the image of $\gamma $ is covered by finitely many balls at centers $x_{k_1},\ldots ,x_{k_n}$ such that

$$\begin{aligned} B_\delta (x_{k_i})\cap B_\delta (x_{k_{i+1}})\cap \varOmega \ne \emptyset \end{aligned}$$

for $i=1,\ldots ,{n-1}$ with $x\in B_\delta (x_{k_1}), y\in B_\delta (x_{k_n})$. Using (34) this yields

$$\begin{aligned} d_\varOmega (x,y)&\le d_\varOmega (x,x_{k_1}) + \sum _{i=1}^{k_{n-1}} d_\varOmega (x_i,x_{i+1}) + d_\varOmega (x_{k_n},y)\\ {}&\le 2~(N + 1)(1+\varepsilon )\delta \end{aligned}$$

where we used $k_n\le N$. Note that the last expression above is independent of x, y which concludes the proof. $\square $

Lemma 10

Let $\varOmega \subset \mathbb {R}^{d}$ be a domain satisfying (11), let the kernel fulfill (K1)–(K3), and $\left( s_{n}\right) _{n\in \mathbb {N}}\subset (0,\infty )$ be a null sequence which satisfies the scaling condition (8). Let $\left( u_{n}\right) _{n\in \mathbb {N}}\subset L^{\infty }(\varOmega )$ be a sequence with

$$\begin{aligned} \sup _{n\in \mathbb {N}} E_{n,\mathrm {cons}}(u_n)&<\infty \end{aligned}$$

then it is bounded with respect to $\left\| \cdot \right\| _\infty $.

Remark 10

Similar to Remark 9, one can relax condition (11) in Lemma 10 by taking into account the specific form of the constraint set ${\mathcal {O}}\subset {\overline{\varOmega }}$. Indeed, an inspection of the following proof shows that it suffices to demand that

$$\begin{aligned} \sup _{x\in \varOmega }\inf _{y\in {\mathcal {O}}} d_\varOmega (x,y)<\infty , \end{aligned}$$

(35)

which means that ${\mathcal {O}}$ has finite geodesic distance to any point in $\varOmega $. In the case that ${\mathcal {O}}=\partial \varOmega $ this is always satisfied since $\varOmega $ is bounded. However, the condition is violated, e.g., if $\varOmega $ is an open, infinite but bounded spiral and ${\mathcal {O}}$ a single point at its center.

Proof

W.l.o.g. we assume

$$\begin{aligned} \eta (t)\ge 1\text { for }t\le 1. \end{aligned}$$

Let $n_0\in \mathbb {N}$ be large enough such that

$$\begin{aligned} r_n < s_n/2,\ \forall n\ge n_0 \end{aligned}$$

and for $x_0\in \varOmega _n, n\ge n_0$ let $\gamma :[0,1]\rightarrow \varOmega $ be a path in $\varOmega $ such that $\gamma (0)=x_0$ and $\gamma (1)\in {\mathcal {O}}_n.$ We divide $\gamma $ by points $0=t_0<\cdots <t_{k_n}=1$ such that

$$\begin{aligned} \left| \gamma (t_i) - \gamma (t_{i+1})\right|&= s_n - 2r_n,\quad i=0,\ldots ,k_n-2,\\ \left| \gamma (t_{k_n}) - \gamma (t_{k_n+1})\right|&\le s_n - 2r_n, \end{aligned}$$

and by definition of the parameter $r_n$ we know that for each $i=0,\ldots ,k_n$ there exists a vertex $x_i\in \varOmega _n$ such that

$$\begin{aligned} \left| x_i - \gamma (t_i)\right| \le r_n. \end{aligned}$$

Applying the triangle inequality this yields

$$\begin{aligned} \left| x_i - x_{i+1}\right|&\le \left| x_i- \gamma (t_i)\right| + \left| \gamma (t_i) - \gamma (t_{i+1})\right| + \left| x_{i+1} - \gamma (t_{i+1})\right| \\ {}&\le 2r_n + s_n - 2 r_n\le s_n, \end{aligned}$$

and thus $\eta _{s_n}(\left| x_i-x_{i+1}\right| )\ge 1$ for all $i=0,\ldots ,k_n-1$. By definition of the discrete functional (6) there exists $\mathbf {u}_n:\varOmega \rightarrow \mathbb {R}$ with $u_n=\mathbf {u}_n\circ p_n$ and we can estimate

$$\begin{aligned} \left| \mathbf {u}_n(x_0)\right|&\le \sum _{i=0}^{{k_n-2}} \left| \mathbf {u}_n(x_i) - \mathbf {u}_n(x_{i+1})\right| + \left| \mathbf {u}_n(x_{{k_n}})\right| \nonumber \\ {}&\le s_n \sum _{i=0}^{{k_n-2}} \eta _{s_n}(\left| x_i-x_{i+1}\right| ) \left| \mathbf {u}_n(x_i) - \mathbf {u}_n(x_{i+1})\right| /s_n + \left| g(x_{k_n})\right| \nonumber \\ {}&\le s_n~{(k_n-1)}~E_{n, \mathrm {cons}}(u_n) + \left| g(x_{k_n})\right| , \end{aligned}$$

(36)

where we used $\mathbf {u}_n(x)=g(x)$ for all $x\in {\mathcal {O}}_n$ since $E_{n,\mathrm {cons}}(u_n)<\infty $. It remains to show that the product $s_n~{(k_n-1)}$ is uniformly bounded in n, for which we first observe that the path $\gamma $ can be chosen such that

$$\begin{aligned} k_n-1\le \lfloor \text {diam}_g(\varOmega )/(s_n-2r_n) \rfloor \end{aligned}$$

and thus using (8)

$$\begin{aligned} s_n~(k_n-1) \le s_n~\left\lfloor \frac{\text {diam}_g(\varOmega )}{(s_n-2r_n)}\right\rfloor \le C \frac{1}{(1 - 2~r_n/s_n)} < {\tilde{C}},\ \forall n\in \mathbb {N}, \end{aligned}$$

where we note that ${\text {diam}}_g(\varOmega )<\infty $ according to Lemma 9. Together with (36) this yields that there exists a uniform constant $C>0$ such that $\left\| u_n\right\| _{L^{\infty }}\le C$ for all $n\in \mathbb {N}$. $\square $

We can now prove that the constrained functionals $E_{n,\mathrm {cons}}$ are indeed compact.

Lemma 11

Let $\varOmega \subset \mathbb {R}^{d}$ be a domain satisfying (11), let the kernel fulfill (K1)–(K3), and $\left( s_{n}\right) _{n\in \mathbb {N}}\subset (0,\infty )$ be a null sequence which satisfies the scaling condition (8). Then we have that every sequence $\left( u_{n}\right) _{n\in \mathbb {N}}\subset L^{\infty }(\varOmega )$ such that

$$\begin{aligned} \sup _{n\in \mathbb {N}} E_{n,\mathrm {cons}}(u_n)<\infty \end{aligned}$$

is relatively compact in $L^{\infty }$.

Proof

Using the same arguments as in the proof of Lemma 5 we can find a scaling sequence $\left( {{\tilde{s}}}_{n}\right) _{n\in \mathbb {N}}\subset (0,\infty )$ such that

$$\begin{aligned} E_{n}(u_n)&\ge \frac{{\tilde{s}}_n}{s_n}~{\mathcal {E}}_{{\tilde{s}}_n}(u_n) \end{aligned}$$

and ${\tilde{s}}_n/s_n\longrightarrow 1$. We choose $C:=\sup _{n\in \mathbb {N}} \frac{s_n}{{\tilde{s}}_n}<\infty $ to obtain

$$\begin{aligned} \sup _{n\in \mathbb {N}}{\mathcal {E}}_{{\tilde{s}}_n}(u_n) \le C\sup _{n\in \mathbb {N}}E_{n}(u_n) = C\sup _{n\in \mathbb {N}}E_{n,\mathrm {cons}}(u_n) <\infty . \end{aligned}$$

Thanks to Lemma 10 the sequence $(u_n)_{n\in \mathbb {N}}$ is bounded in $L^{\infty }$ and thus we can apply Lemma 8 to infer that $\left( u_{n}\right) _{n\in \mathbb {N}}\subset L^{\infty }(\varOmega )$ is relatively compact. $\square $

Together with Lemma 1 this finally yields our second main statement Theorem 2.

Proof of Theorem 2

Let $v\in L^{\infty }(\varOmega )$ with ${\mathcal {E}}_\mathrm {cons}(v)<\infty $ be arbitrary and $\left( v_{n}\right) _{n\in \mathbb {N}}\subset L^{\infty }(\varOmega )$ be a recovery sequence for v, the existence of which is guaranteed by Lemma 6. By assumption, the sequence $u_n$ satisfies

$$\begin{aligned} \limsup _{n\rightarrow \infty }E_{n,\mathrm {cons}}(u_n)&= \limsup _{n\rightarrow \infty } \inf _{u\in L^{\infty }(\varOmega )} E_{n,\mathrm {cons}}(u) \\&\le \limsup _{n\rightarrow \infty } E_{n,\mathrm {cons}}(v_n) \le \sigma _\eta ~{\mathcal {E}}_\mathrm {cons}(v)<\infty . \end{aligned}$$

Hence, Lemma 11 implies that $\left( u_{n}\right) _{n\in \mathbb {N}}\subset L^{\infty }(\varOmega )$ is relatively compact. Lemma 1 then concludes the proof. $\square $

5 Application to Ground States

In this section we apply the discrete-to-continuum $\varGamma $-convergence from Theorem 1 to so-called ground states, first studied in [13]. These are restricted minimizers of the functionals $E_{n,\mathrm {cons}}$ and ${\mathcal {E}}_\mathrm {cons}$ on $L^{p}$-spheres, where we assume that the constraint satisfies $g=0$ on ${\overline{\varOmega }}$. This makes the functionals $E_{n,\mathrm {cons}}$ and ${\mathcal {E}}_\mathrm {cons}$ absolutely 1-homogeneous.

For absolutely p-homogeneous functionals $F:X\rightarrow \mathbb {R}\cup \{\infty \}$ on a Banach space $(X,\left\| \cdot \right\| )$ with $p\in [1,\infty )$, which per definitionem satisfy

$$\begin{aligned} F(cu)=\left| c\right| ^pF(u),\quad \forall u\in X,\,c\in \mathbb {R}, \end{aligned}$$

ground states are defined as solutions to the minimization problem

$$\begin{aligned} \min \left\{ F(u) \,:\, \inf _{v\in {{\,\mathrm{arg\,min}\,}}F}\left\| u-v\right\| = 1 \right\} . \end{aligned}$$

Ground states and their relations to gradient flows and power methods are well studied in the literature, see, e.g., [11, 13, 21, 24‐26]. In particular, they constitute minimizers of the nonlinear Rayleigh quotient

$$\begin{aligned} R(u) = \frac{F(u)}{\inf _{v\in {{\,\mathrm{arg\,min}\,}}F}\left\| u-v\right\| ^p} \end{aligned}$$

and are related to nonlinear eigenvalue problems with the prime example being $F(u)=\int _\varOmega \left| \nabla {u}\right| ^p\mathrm {d}x$ on $X:=L^{\varOmega }$ where ground states solve the p-Laplacian eigenvalue problem

$$\begin{aligned} \lambda \left| u\right| ^{p-2}u = -\varDelta _p u. \end{aligned}$$

In [13] ground states of the functionals $E_{n,\mathrm {cons}}$ and ${\mathcal {E}}_\mathrm {cons}$ were characterized as distance functions. While there it was assumed that ${\mathcal {O}}=\partial \varOmega $, we will in the following generalize these results to the case of an arbitrary closed constraint set ${\mathcal {O}}\subset {\overline{\varOmega }}$. Subsequently, we will use the $\varGamma $-convergence, established in Theorem 1, to show discrete-to-continuum convergence of ground states.

5.1 Relation to Distance Functions

Here, we show that the unique $L^{p}$ ground states of the limit functional ${\mathcal {E}}_\mathrm {cons}$ coincide with multiples of the geodesic distance function to the set ${\mathcal {O}}$. To prove the desired statement, we need the following lemma, stating that the gradient of the geodesic distance function is bounded by one.

Lemma 12

Let ${\mathcal {O}}\subset {\overline{\varOmega }}$ be a closed set and

$$\begin{aligned} d_{\mathcal {O}}(x):=\inf _{y\in {\mathcal {O}}}d_\varOmega (x,y) \end{aligned}$$

be the geodesic distance function of ${\mathcal {O}}$, where $d_\varOmega (x,y)$ denotes the geodesic distance between $x,y\in \varOmega $. Then it holds

$$\begin{aligned} \left\| \nabla {d_{\mathcal {O}}}\right\| _{L^{\infty }}\le 1. \end{aligned}$$

Proof

Let $x,y\in \varOmega $ be arbitrary. Using the triangle inequality for $d_\varOmega $ we get

$$\begin{aligned} d_{\mathcal {O}}(y)\le d_\varOmega (x,y)+d_{\mathcal {O}}(x),\quad \forall x,y\in \varOmega . \end{aligned}$$

If x, y lie in a ball fully contained in $\varOmega $, then $d_\varOmega (x,y)=\left| x-y\right| $ and we obtain that $d_{\mathcal {O}}$ is Lipschitz continuous on this ball. Rademacher’s theorem then implies that $\nabla d_{\mathcal {O}}$ exists almost everywhere in the ball. Since the ball is arbitrary, $\nabla d_{\mathcal {O}}$ in fact exists almost everywhere in $\varOmega $.

Furthermore, since $\varOmega $ is open, for $x\in \varOmega $ and $t>0$ small enough the ball $B_t(x):=\{y\in \mathbb {R}^{d}\,:\,\left| x-y\right| <t\}$ lies within $\varOmega $ and it holds $d_\varOmega (x,y)=\left| x-y\right| $ for all $y\in B_t(x)$.

Choosing $y=x+ta\in B_t(x)$ with $a\in B_1(0)$ we get

$$\begin{aligned} \frac{d_{\mathcal {O}}(x+ta)-d_{\mathcal {O}}(x)}{t}\le \frac{d_\varOmega (x,x+ta)}{t}= \frac{\left| at\right| }{t}\le 1. \end{aligned}$$

Since a was arbitrary, we can conclude $\left| \nabla {d_{\mathcal {O}}}(x)\right| \le 1$ for almost all $x\in \varOmega $ which implies the desired statement. $\square $

With this lemma we now can prove that the unique ground state (up to scalar multiples) of the functional ${\mathcal {E}}_\mathrm {cons}$ is given by the geodesic distance function to ${\mathcal {O}}$. The only (weak) assumption which we need here is that $d_{\mathcal {O}}\in L^{p}(\varOmega )$ which is fulfilled, for instance, if $\varOmega $ has finite geodesic diameter or even only satisfies the relaxed condition (35), in which case $d_{\mathcal {O}}\in L^{\infty }(\varOmega )$ holds.

Theorem 5

Let ${\mathcal {O}}$ be a closed set such that ${\overline{\varOmega }}{\setminus }{\mathcal {O}}$ is connected and non-empty and $d_{\mathcal {O}}\in L^{p}(\varOmega )$, and let the constraint function satisfy $g=0$ on ${\mathcal {O}}$. For $p\in [1,\infty )$ the unique solution (up to global sign) to

$$\begin{aligned} \min \left\{ {\mathcal {E}}_{\mathrm {cons}}(u) \,:\,u\in L^{\infty }(\varOmega ),\, \left\| u\right\| _{L^{p}}= 1 \right\} \end{aligned}$$

(37)

is given by a positive multiple of the geodesic distance function $d_{\mathcal {O}}$.

If $\varOmega $ is convex or ${\mathcal {O}}=\partial \varOmega $, the geodesic distance $d_\varOmega (x,y)$ in the definition of $d_{\mathcal {O}}$ can be replaced by the Euclidean $|x-y|$ and $d_{\mathcal {O}}\in L^{p}(\varOmega )$ is always satisfied.

Proof

The case ${\mathcal {O}}=\partial \varOmega $ was already proved in [13]. If $\varOmega $ is convex it holds $d_\varOmega (x,y)=\left| x-y\right| $ which is and hence $d_{\mathcal {O}}$ is bounded and, in particular, lies in $L^{p}(\varOmega )$ for all $p\ge 1$.

We first prove that the geodesic distance function $d_{\mathcal {O}}$ is a solution of

$$\begin{aligned} \max \left\{ \left\| u\right\| _{L^{p}} \,:\,{u\in L^{\infty }(\varOmega )},\, {\mathcal {E}}_\mathrm {cons}(u)= 1 \right\} . \end{aligned}$$

(38)

Since ${\mathcal {O}}$ is closed and bounded, for every $x\in \varOmega $ we can choose $y_x\in {\mathcal {O}}$ such that $d_\varOmega (x,y_x)\le d_\varOmega (x,y)$ for all $y\in {\mathcal {O}}$. Hence, if $u=0$ on ${\mathcal {O}}$, we can choose $y=y_x$ and obtain from (27) that

$$\begin{aligned} \left| u(x)\right| \le \left\| \nabla {u}\right\| _{L^{\infty }}d_{\mathcal {O}}(x) \end{aligned}$$

(39)

for almost every $x\in \varOmega $ which implies

$$\begin{aligned} \left\| u\right\| _{L^{p}}\le \left\| \nabla {u}\right\| _{L^{\infty }}\left\| d_{\mathcal {O}}\right\| _{L^{p}}. \end{aligned}$$

(40)

Hence, for all $u\in L^{\infty }(\varOmega )$ with ${\mathcal {E}}_\mathrm {cons}(u)= 1$ one obtains from (40) that

$$\begin{aligned} \left\| u\right\| _{L^{p}}\le \left\| d_{\mathcal {O}}\right\| _{L^{p}}. \end{aligned}$$

From Lemma 12 we know that ${\mathcal {E}}_\mathrm {cons}(d_{\mathcal {O}})=\left\| \nabla {d_{\mathcal {O}}}\right\| _{L^{\infty }}\le 1$. At the same time choosing $u=d_{\mathcal {O}}$ in (40) shows that in fact ${\mathcal {E}}_\mathrm {cons}(d_{\mathcal {O}})=\left\| \nabla {d_{\mathcal {O}}}\right\| _{L^{\infty }}= 1$ and therefore $d_{\mathcal {O}}$ solves (38).

Regarding uniqueness we argue as follows: Since $p<\infty $ the inequality (40) is sharp if (39) is sharp which, using that $\left\| \nabla u\right\| _{L^{\infty }}={\mathcal {E}}_\mathrm {cons}(u)=1$, implies that all solutions u of (38) must fulfill

$$\begin{aligned} \left| u(x)\right| =d_{\mathcal {O}}(x),\quad \forall x\in \varOmega . \end{aligned}$$

If $\varOmega {\setminus }{\mathcal {O}}$ is connected, the continuity of u implies that (up to global sign) $u(x)=d_{\mathcal {O}}(x)$ for all $x\in \varOmega $.

Finally, we argue that (37) and (38) are equivalent: Since $d_{\mathcal {O}}\in L^{p}(\varOmega )$ we have $\left\| d_{\mathcal {O}}\right\| _{L^{p}}<\infty $. Then $d_{\mathcal {O}}/\left\| d_{\mathcal {O}}\right\| _{L^{p}}$ solves (37) since for any $u\in L^{\infty }(\varOmega )$ with $\left\| u\right\| _{L^{p}}=1$ it holds

$$\begin{aligned} {\mathcal {E}}_\mathrm {cons}\left( \frac{d_{\mathcal {O}}}{\left\| d_{\mathcal {O}}\right\| _{L^{p}}}\right) = \frac{{\mathcal {E}}_\mathrm {cons}(d_{\mathcal {O}})}{\left\| d_{\mathcal {O}}\right\| _{L^{p}}} = \frac{1}{\left\| d_{\mathcal {O}}\right\| _{L^{p}}} = \frac{\left\| u\right\| _{L^{p}}}{\left\| d_{\mathcal {O}}\right\| _{L^{p}}} \le {\mathcal {E}}_\mathrm {cons}(u), \end{aligned}$$

where we used (40) for the inequality. Analogously, if u solves (37) then

$$\begin{aligned} {\mathcal {E}}_\mathrm {cons}(u)\le {\mathcal {E}}_\mathrm {cons}(d_{\mathcal {O}}/\left\| d_{\mathcal {O}}\right\| _{L^{p}})=1/\left\| d_{\mathcal {O}}\right\| _{L^{p}}<\infty . \end{aligned}$$

This follows from the fact that $d_{\mathcal {O}}\ne 0$ since ${{\overline{\varOmega }}}{\setminus }{\mathcal {O}}\ne \emptyset $. Then $u/{\mathcal {E}}_\mathrm {cons}(u)$ solves (38) since, using again (40), it holds

$$\begin{aligned} \left\| \frac{u}{{\mathcal {E}}_\mathrm {cons}(u)}\right\| _{L^{p}} = \frac{1}{{\mathcal {E}}_\mathrm {cons}(u)} \ge \frac{\left\| d_{\mathcal {O}}\right\| _{L^{p}}}{\left\| u\right\| _{L^{p}}} = \left\| d_{\mathcal {O}}\right\| _{L^{p}} \end{aligned}$$

and $d_{\mathcal {O}}$ solves (38). $\square $

Remark 11

In the case $p=\infty $ the geodesic distance function is still a ground state, however, not the unique one. In this case, other ground states are given by $\infty $-Laplacian eigenfunctions, see, e.g., [7, 28, 37].

Remark 12

If one drops the condition that ${\overline{\varOmega }}{\setminus }{\mathcal {O}}$ is connected, ground states coincide with (positive or negative) multiples of the distance function on each connected component of ${\overline{\varOmega }}{\setminus }{\mathcal {O}}$.

Similarly, one can also prove that ground states of the discrete functionals $E_{n,\mathrm {cons}}$ coincide with multiples of distance functions to ${\mathcal {O}}_n$ with respect to the geodesic graph distance if $\varOmega _n{\setminus }{\mathcal {O}}_n$ is connected in the graph-sense. The result can be found in [13]; however, since we do not need it here, we refrain from stating it.

5.2 Convergence of Ground States

In this section we first show that the $\varGamma $-convergence of the functionals $E_{n,\mathrm {cons}}$ to $\sigma _\eta {\mathcal {E}}_\mathrm {cons}$ implies the convergence of their respective ground states. Together with the characterization from Theorem 5 this implies that discrete ground states converge to the geodesic distance function.

Theorem 6

(Convergence of Ground States) Under the conditions of Theorem 1 let the sequence $(u_n)_{n\in \mathbb {N}}\subset L^{\infty }(\varOmega )$ fulfill

$$\begin{aligned} u_n \in {{\,\mathrm{arg\,min}\,}}\left\{ E_{n,\mathrm {cons}}(u) \,:\,u\in L^{\infty }(\varOmega ),\, \left\| u\right\| _{L^{p}}=1 \right\} . \end{aligned}$$

Then (up to a subsequence) $u_n\rightarrow u$ in $L^{\infty }(\varOmega )$ where

$$\begin{aligned} u \in {{\,\mathrm{arg\,min}\,}}\left\{ {\mathcal {E}}_{\mathrm {cons}}(u) \,:\,u\in L^{\infty }(\varOmega ),\, \left\| u\right\| _{L^{p}}=1 \right\} \end{aligned}$$

and it holds

$$\begin{aligned} \lim _{n\rightarrow \infty }{E_{n,\mathrm {cons}}(u_n)} = \sigma _\eta ~{\mathcal {E}}_{\mathrm {cons}}(u). \end{aligned}$$

(41)

Proof

Let $u\in L^{\infty }(\varOmega )$ be a ground state of ${\mathcal {E}}_\mathrm {cons}$ and $(v_n)_{n\in \mathbb {N}}\subset L^{\infty }(\varOmega )$ be a recovery sequence of u, whose existence is guaranteed by Theorem 1. Since $u_n$ is a ground state and $E_{n,\mathrm {cons}}$ is absolutely 1-homogeneous, we get

$$\begin{aligned} E_{n,\mathrm {cons}}(u_n) \le E_{n,\mathrm {cons}}\left( \frac{v_n}{\left\| v_n\right\| _{L^{p}}}\right) = E_{n,\mathrm {cons}}(v_n)\frac{1}{\left\| v_n\right\| _{L^{p}}}. \end{aligned}$$

Taking the limsup on both sides yields

$$\begin{aligned} \limsup _{n\rightarrow \infty } E_{n,\mathrm {cons}}(u_n) \le \sigma _\eta ~{\mathcal {E}}_\mathrm {cons}(u)\frac{1}{\left\| u\right\| _{L^{p}}} = \sigma _\eta ~{\mathcal {E}}_\mathrm {cons}(u) < \infty , \end{aligned}$$

where we used boundedness of $\varOmega $ to conclude that $L^{\infty }$-convergence implies convergence of the $L^{p}$-norms. Hence, by Lemma 11 the sequence $(u_n)_{n\in \mathbb {N}}$ possesses a subsequence (which we do not relabel) which converges to some $u^*\in L^{\infty }(\varOmega )$ with $\left\| u^*\right\| _{L^{p}}=1$. Using the previous inequality, the liminf inequality from Lemma 5, and the fact that u is a ground state we conclude

$$\begin{aligned} \sigma _\eta ~{\mathcal {E}}_\mathrm {cons}(u^*)&\le \liminf _{n\rightarrow \infty } E_{n,\mathrm {cons}}(u_n) \\&\le \limsup _{n\rightarrow \infty } E_{n,\mathrm {cons}}(u_n) \\&\le \sigma _\eta ~{\mathcal {E}}_\mathrm {cons}(u) \\&\le \sigma _\eta ~{\mathcal {E}}_\mathrm {cons}(u^*). \end{aligned}$$

Hence, $u^*$ is also a ground state and (41) holds true. $\square $

Using the characterization of ground states as distance functions we obtain the following

Corollary 1

Under the conditions of Theorems 5 and 6 the sequence $(u_n)_{n\in \mathbb {N}}\subset L^{\infty }(\varOmega )$, given by

$$\begin{aligned} u_n \in {{\,\mathrm{arg\,min}\,}}\left\{ E_{n,\mathrm {cons}}(u) \,:\,u\in L^{\infty }(\varOmega ),\, \left\| u\right\| _{L^{p}}=1 \right\} , \end{aligned}$$

converges to a multiple of the geodesic distance function $d_{\mathcal {O}}$.

6 Conclusion and Future Work

In this work we derived continuum limits of semi-supervised Lipschitz learning on graphs. We first proved $\varGamma $-convergence of non-local functionals to the supremal norm of the gradient. This allowed us to show $\varGamma $-convergence of the discrete energies which appear in the Lipschitz learning problem. In order to interpret graph functions as functions defined on the continuum, we employed a closest point projection. We also showed that the discrete functionals are compact which implies discrete-to-continuum convergence of minimizers. We applied our results to a nonlinear eigenvalue problem whose solutions are geodesic distance functions.

Future work will include the generalization of our results to general metric measure spaces or Riemannian manifolds, which constitute a generic domain for the data in real-world semi-supervised learning problems. Furthermore, we intend to see how the application of our results to absolutely minimizing Lipschitz extensions [5] on graphs unfolds. Namely, we want to gain insight whether it is possible to prove their convergence toward solutions of the infinity Laplacian equation under less restrictive assumptions than the ones used in [15].

Open AccessThis article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

next article The Average Condition Number of Most Tensor Rank Decomposition Problems is Infinite

Robert A. Adams and John Fournier. Sobolev Spaces, Volume 140 (Pure and Applied Mathematics). Academic Press, New York, 2003.

Ahmed El Alaoui, Xiang Cheng, Aaditya Ramdas, Martin J. Wainwright, and Michael I. Jordan. Asymptotic behavior of $l_{p}$-based Laplacian regularization in semi-supervised learning. 2016. arxiv: 1603.00564.

Gunnar Aronsson. Minimization problems for the functional ${{\rm sup}}_{x} F(x, f(x), f^{\prime } (x))$. In: Arkiv för Matematik 6.1 (1965), pp. 33–53. https://doi.org/10.1007/bf02591326.CrossRefMATH

Gunnar Aronsson. On the partial differential equation $u^{2} _{x}u_{xx}+2u_{x}u_{y}u_{xy}+ u ^{2}_{y}u_{yy} = 0$. In: Arkiv för Matematik 7.5 (1968), pp. 395–425. https://doi.org/10.1007/bf02590989.CrossRef

Gunnar Aronsson, Michael Crandall, and Petri Juutinen. A tour of the theory of absolutely minimizing functions. In: Bulletin of the American Mathematical Society 41.4 (2004), pp. 439–505.MathSciNetCrossRefMATH

Vladimir I. Bogachev. Measure Theory. Springer, Berlin, Heidelberg, 2007. https://doi.org/10.1007/978-3-540-34514-5.

Farid Bozorgnia, Leon Bungert, and Daniel Tenbrinck. The Infinity Laplacian eigenvalue problem: reformulation and a numerical scheme. 2020. arXiv: 2004.08127 [math.NA].

Andrea Braides. Gamma-convergence for Beginners. Vol. 22. Oxford University Press, Oxford, 2002.CrossRefMATH

Haim Brezis. Functional Analysis, Sobolev Spaces and Partial Differential Equations. Springer, New York, 2010. https://doi.org/10.1007/978-0-387-70914-7.

10.

Martin R. Bridson and André Haefliger. Metric Spaces of Non-Positive Curvature. Springer, Berlin, Heidelberg, 1999. https://doi.org/10.1007/978-3-662-12494-9.

11.

Leon Bungert and Martin Burger. Asymptotic profiles of nonlinear homogeneous evolution equations of gradient flow type. In: Journal of Evolution Equations 20.3 (2020), pp. 1061–1092. https://doi.org/10.1007/s00028-019-00545-1.MathSciNetCrossRefMATH

12.

Leon Bungert, Jeff Calder, and Tim Roith. Uniform Convergence Rates for Lipschitz Learning on Graphs. 2021. arXiv: 2111.12370 [math.NA].

13.

Leon Bungert, Yury Korolev, and Martin Burger. Structural analysis of an $L$-infinity variational problem and relations to distance functions. Pure and Applied Analysis 2.3 (2020), pp. 703–738. https://doi.org/10.2140/paa.2020.2.703.MathSciNetCrossRefMATH

14.

Jeff Calder. Consistency of Lipschitz Learning with Infinite Unlabeled Data and Finite Labeled Data. In: SIAM Journal on Mathematics of Data Science 1.4 (2019), pp. 780–812. https://doi.org/10.1137/18m1199241.MathSciNetCrossRefMATH

15.

Jeff Calder, Brendan Cook, Matthew Thorpe, and Dejan Slepčev. Poisson Learning: Graph Based semi-supervised learning at very low label rates. In: International Conference on Machine Learning. PMLR. 2020, pp. 1306–1316.

16.

Jeff Calder, Dejan Slepčev, and Matthew Thorpe. Rates of Convergence for Laplacian Semi-Supervised Learning with Low Labeling Rates. 2020. arXiv: 2006.02765 [math.ST].

17.

Olivier Chapelle, Bernhard Schölkopf, and Alexander Zien. Semi-Supervised Learning. Cambridge, MA: The MIT Press, 2010.

18.

Paul Civin, Nelson Dunford, and Jacob T. Schwartz. Linear Operators. Part I: General Theory. American Mathematical Monthly 67 (1960), p. 199.MathSciNetCrossRef

19.

Abderrahim Elmoataz, Matthieu Toutain, and Daniel Tenbrinck. On the $p$-Laplacian and $\infty $-Laplacian on Graphs with Applications in Image and Data Processing. In: SIAM Journal on Imaging Sciences 8.4 (2015), pp. 2412–2451. https://doi.org/10.1137/15m1022793.

20.

Lawrence C Evans and Charles K Smart. Everywhere differentiability of infinity harmonic functions. Calculus of Variations and Partial Differential Equations 42.1-2 (2011), pp. 289–299.MathSciNetCrossRefMATH

21.

Tal Feld, Jean-François Aujol, Guy Gilboa, and Nicolas Papadakis. Rayleigh quotient minimization for absolutely one-homogeneous functionals. Inverse Problems 35.6 (2019), p. 064003.MathSciNetCrossRefMATH

22.

Nicolás García Trillos and Dejan Slepčev. Continuum Limit of Total Variation on Point Clouds. In: Archive for Rational Mechanics and Analysis 220.1 (2015), pp. 193–241. https://doi.org/10.1007/s00205-015-0929-z.

23.

Yves van Gennip and Andrea L. Bertozzi. Gamma-convergence of graph Ginzburg–Landau functionals. In: Advances in Differential Equations 17.11/12 (2012), pp. 1115–1180.MATH

24.

Ryan Hynd and Erik Lindgren. Inverse iteration for $p$-ground states. In: Proceedings of the American Mathematical Society 144.5 (2016), pp. 2121– 2131. https://doi.org/10.1090/proc/12860.

25.

Ryan Hynd and Erik Lindgren. Approximation of the least Rayleigh quotient for degree $p$ homogeneous functionals. In: Journal of Functional Analysis 272.12 (2017), pp. 4873–4918. https://doi.org/10.1016/j.jfa.2017.02.024.

26.

Ryan Hynd and Erik Lindgren. Extremal functions for Morrey’s inequality in convex domains. In: Mathematische Annalen 375.3-4 (2019), pp. 1721–1743. https://doi.org/10.1007/s00208-018-1775-8.MathSciNetCrossRefMATH

27.

Petri Juutinen. Absolutely minimizing Lipschitz extensions on a metric space. In: Annales Academiae Scientiarum Fennicae Mathematica Volumen 27 (Jan. 2002), pp. 57–67.MathSciNetMATH

28.

Petri Juutinen, Peter Lindqvist, and Juan J Manfredi. The infinity Laplacian: examples and observations. Institut Mittag-Leffler, 1999.

29.

Peter Knabner and Lutz Angermann. Numerical Methods for Elliptic and Parabolic Partial Differential Equations. Springer, Berlin, Heidelberg, 2003. https://doi.org/10.1007/b97419.

30.

Rasmus Kyng, Anup Rao, Sushant Sachdeva, and Daniel A Spielman. Algorithms for Lipschitz learning on graphs. In: Conference on Learning Theory. PMLR. 2015, pp. 1190–1223.

31.

Erwan Le Gruyer. On absolutely minimizing Lipschitz extensions and PDE $\Delta _{\infty }(u) = 0$. In: Nonlinear Differential Equations and Applications NoDEA 14.1 (2007), pp. 29–55.MathSciNetCrossRefMATH

32.

Ulrike von Luxburg, Mikhail Belkin, and Olivier Bousquet. Consistency of spectral clustering. In: The Annals of Statistics 36.2 (2008), pp. 555–586. https://doi.org/10.1214/009053607000000640.MathSciNetCrossRefMATH

33.

David Pollard. Strong Consistency of $k$-Means Clustering. In: The Annals of Statistics 9.1 (1981), pp. 135–140. https://doi.org/10.1214/aos/1176345339.

34.

Scott Sheffield and Charles K. Smart. Vector-valued optimal Lipschitz extensions. In: Communications on Pure and Applied Mathematics 65.1 (2012), pp. 128–154.MathSciNetCrossRefMATH

35.

Dejan Slepčev and Matthew Thorpe. Analysis of $p$-Laplacian Regularization in Semisupervised Learning. In: SIAM Journal on Mathematical Analysis 51.3 (2019), pp. 2085–2120. https://doi.org/10.1137/17m115222x.

36.

Nicolás García Trillos, Dejan Slepčev, James von Brecht, Thomas Laurent, and Xavier Bresson. Consistency of Cheeger and Ratio Graph Cuts. In: J. Mach. Learn. Res. 17.1 (2016), pp. 6268–6313.MathSciNetMATH

37.

Yifeng Yu. Some properties of the ground states of the infinity Laplacian. In: Indiana University Mathematics Journal (2007), pp. 947–964.

38.

Xiaojin Zhu, Zoubin Ghahramani, and John Lafferty. Semi-Supervised Learning Using Gaussian Fields and Harmonic Functions. In: ICML’03 (2003), pp. 912–919.

39.

Xiaojin Zhu and Andrew B. Goldberg. Introduction to semi-supervised learning. In: Synthesis lectures on artificial intelligence and machine learning 3.1 (2009), pp. 1–130.MATH

40.

Xiaojin Zhu, John Lafferty, and Ronald Rosenfeld. Semi-supervised learning with graphs. PhD thesis. Carnegie Mellon University, language technologies institute, school of computer science, 2005.

41.

Xiaojin Jerry Zhu. Semi-supervised learning literature survey. Tech. rep. University of Wisconsin-Madison Department of Computer Sciences, 2005.

Title: Continuum Limit of Lipschitz Learning on Graphs
Authors: Tim Roith
Leon Bungert
Publication date: 21-01-2022
Publisher: Springer US
Published in: Foundations of Computational Mathematics / Issue 2/2023
Print ISSN: 1615-3375
Electronic ISSN: 1615-3383
DOI: https://doi.org/10.1007/s10208-022-09557-9

Springer Professional

Continuum Limit of Lipschitz Learning on Graphs

Abstract

Publisher's Note

1 Introduction

1.1 Assumptions and Main Result

1.3 Outline

2 Mathematical Background

2.1 \(\varGamma \)-Convergence

2.2 The Closest Point Projection

3 \(\varGamma \)-Convergence of Lipschitz Functionals

3.1 Non-local to Local Convergence

3.2 Discrete to Continuum Convergence

4 Compactness

5 Application to Ground States

5.1 Relation to Distance Functions

5.2 Convergence of Ground States

6 Conclusion and Future Work

Publisher's Note

Premium Partner

Springer Professional

Abstract

Publisher's Note

1 Introduction

1.1 Assumptions and Main Result

1.2 Related Work

1.3 Outline

2 Mathematical Background

2.1 \(\varGamma \)-Convergence

2.2 The Closest Point Projection

3 \(\varGamma \)-Convergence of Lipschitz Functionals

3.1 Non-local to Local Convergence

3.2 Discrete to Continuum Convergence

4 Compactness

5 Application to Ground States

5.1 Relation to Distance Functions

5.2 Convergence of Ground States

6 Conclusion and Future Work

Publisher's Note

Other articles of this Issue 2/2023

A Common Variable Minimax Theorem for Graphs

Learning Elliptic Partial Differential Equations with Randomized Linear Algebra

Explicit Computation of a Galois Representation Attached to an Eigenform Over from the of a Surface

The Average Condition Number of Most Tensor Rank Decomposition Problems is Infinite

Halting Time is Predictable for Large Models: A Universality Property and Average-Case Analysis

Affine-Invariant Ensemble Transform Methods for Logistic Regression

Premium Partner