Finding the convex envelope of a boundary datum using random geometric graphs

1. Probleemstelling

Het doel van dit onderzoek is om de convexe omhulling (convex envelope) van een randwaarde (boundary datum) binnen een begrensd domein in de Euclidische ruimte te benaderen.

• Context: Gegeven is een continue functie $f$ gedefinieerd op de rand $\partial D$ van een strikt convex domein $D \subset \mathbb{R}^d$. Men zoekt de unieke convexe functie $u$ binnen $D$ die overeenkomt met $f$ op de rand.
• Analytische Karakterisering: In de continue theorie wordt deze convexe omhulling beschreven als de unieke viscositeitoplossing van de volgende partiële differentiaalvergelijking (PDE):
  $$\begin{cases} \lambda_1(D^2 u)(x) = 0 & x \in D \\ u(x) = f(x) & x \in \partial D \end{cases}$$
  Hierbij is $\lambda_1(D^2 u)$ het kleinste eigenwaarde van de Hessiaan van $u$. De voorwaarde $\lambda_1 \geq 0$ is equivalent met convexiteit.
• Uitdaging: Het numeriek oplossen van deze PDE is complex, vooral in hoge dimensies. De auteurs onderzoeken een discrete, probabilistische benadering via willekeurige meetkundige grafen (Random Geometric Graphs - RGG) en speltheorie.

2. Methodologie

De auteurs combineren elementen uit de kansrekening, grafentheorie en de theorie van viscositeitoplossingen.

A. Het Model: Willekeurige Meetkundige Grafen

• Puntwolk: Er wordt een willekeurige steekproef $\chi_n = \{X_1, \dots, X_n\}$ gegenereerd met een uniforme verdeling op het eenheidskubus $[0, 1]^d$.
• Grafenstructuur: Een graaf $G_n$ wordt gedefinieerd waarbij punten verbonden zijn als hun onderlinge afstand kleiner is dan een straal $r_n$. Dit is een proximity graph.
• Regime: Het onderzoek werkt in het superconnectiviteitsregime, wat betekent dat $n r_n^d / \log n \to \infty$ als $n \to \infty$. Dit garandeert dat de graaf bijna zeker verbonden is en dat er voldoende buren zijn in alle richtingen.

B. Discrete Benadering en Speltheorie

De auteurs definiëren een één-speler spel op de graaf om de convexe omhulling te benaderen:

1. Spelpositie: Een token start bij een punt $x_0$ in het domein $D$.
2. Strategie: De speler $J$ kiest een buur $y$ uit een specifieke "annulus" (ringvormige regio) rondom $x_0$ met straal $r_n$.
3. Willekeurige beweging: De volgende positie $x_1$ wordt met gelijke kans ($1/2$) gekozen als óf het gekozen punt $y$, óf het gespiegelde punt $y_{x_0}$ (de reflectie van $y$ ten opzichte van $x_0$). Omdat het exacte gespiegelde punt niet altijd in de steekproef zit, wordt een benaderend gespiegeld punt gebruikt dat dicht bij de reflectie ligt.
4. Doel: De speler probeert de verwachte uitbetaling (payoff) $f(x_\tau)$ te minimaliseren, waarbij $\tau$ de tijd is waarop het spel het domein verlaat (de rand $B_n$ bereikt).
5. Dynamic Programming Principle (DPP): De waarde van het spel $u_n(x)$ voldoet aan de volgende discrete vergelijking:
   $$u_n(x) = \min_{y \in N_x^{\delta_n}} \left( \frac{1}{2} u_n(y) + \frac{1}{2} u_n(y_x) \right)$$
   Dit is de discrete analogie van de vergelijking $\lambda_1(D^2 u) = 0$.

C. Technische Randvoorwaarden

Om convergentie te garanderen, moeten de parameters $r_n$ (straal) en $\delta_n$ (breedte van de annulus) op een specifieke manier afnemen:

• $r_n \to 0$ en $\delta_n \to 0$.
• Er geldt een sterkere voorwaarde dan alleen connectiviteit: $\sqrt{n} r_n^{2d} / \log n \to \infty$.
• Er moet voldoende dichtheid van punten zijn in elke richting binnen de annulus om de tweede-orde differentiatie in alle richtingen te kunnen schatten.

3. Belangrijkste Bijdragen

1. Probabilistische Controle van de Grafenstructuur:
   De auteurs bewijzen dat, onder de gegeven voorwaarden, de willekeurige grafen bijna zeker de eigenschap hebben dat elke knoop buren heeft in "alle richtingen" binnen de annulus. Dit wordt bewezen met behulp van concentratieongelijkheden (Talagrand/Bousquet) voor empirische processen. Dit is cruciaal om de Hessiaan in elke richting te kunnen benaderen.

2. Speltheoretische Formulering:
   Ze introduceren een spel op een willekeurige graaf waarvan de waarde functie exact voldoet aan een discrete DPP. Ze tonen aan dat deze discrete vergelijking een unieke oplossing heeft (via een vergelijkingsprincipe).

3. Convergentiebewijs:
   Het centrale resultaat is het bewijs dat de oplossing van het discrete spel op de willekeurige graaf convergeert naar de continue convexe omhulling van de randwaarde wanneer het aantal punten $n \to \infty$.

4. Resultaten

• Stelling 1: Voor bijna elke realisatie van de willekeurige punten, is de waarde van het spel $u_n$ de unieke oplossing van de discrete DPP (1.7).
• Stelling 2 (Hoofdstelling): Als de parameters voldoen aan de specifieke asymptotische voorwaarden (zoals in vergelijking 1.6), dan convergeert de gereconstrueerde functie $\tilde{u}_n$ (de uitbreiding van de spelwaarde naar het hele domein) uniform naar de unieke viscositeitoplossing $u$ van de continue PDE (1.8).
  $$\lim_{n \to \infty} \sup_{x \in D} |\tilde{u}_n(x) - u(x)| = 0 \quad \text{(bijna zeker)}$$
• Onafhankelijkheid: De limiet is onafhankelijk van de specifieke spelparameters (zoals de exacte keuze van $r_n$ en $\delta_n$), zolang ze maar binnen het juiste regime vallen; de limiet wordt uitsluitend bepaald door de randwaarde $f$.

5. Betekenis en Relevantie

• Verbinding tussen PDE's en Grafen: Het artikel versterkt het verband tussen continue partiële differentiaalvergelijkingen en discrete leerprocedures op grafen. Het toont aan dat complexe niet-lineaire PDE's (zoals die voor convexe omhulling) kunnen worden benaderd door lokale operaties op grote, willekeurige datasets.
• Semi-supervised Learning: De methode biedt een theoretische basis voor semi-supervised learning op grafen, waarbij labels op de rand worden gebruikt om waarden in het binnenste te reconstrueren onder convexiteitsvoorwaarden.
• Numerieke Toepassingen: Hoewel de huidige methode probabilistisch is, biedt het inzicht in hoe men convexe omhullingen kan berekenen in hoge dimensies zonder een vaste grid, wat nuttig kan zijn voor data-analyse en optimalisatieproblemen.
• Technische Innovatie: Het gebruik van een "gespiegeld" punt in een discrete setting om de tweede-orde afgeleide te simuleren, is een elegante oplossing voor het discretiseren van de Hessiaan op willekeurige puntenwolk.

Kortom, dit paper levert een rigoureus wiskundig bewijs dat een spel op een willekeurige meetkundige graaf een consistente en convergente benadering vormt voor het vinden van de convexe omhulling van een functie.