Gradient Descent on Point Clouds and Applications in Learned Operator Correction

Technische Samenvatting: Gradiëntafdaling op Puntenwolken en Toepassingen in Geleerde Operatorcorrectie

Probleemstelling
Het artikel behandelt de uitdaging van het minimaliseren van een energiefunctie $E(x)$ over een onbekende variëteit $\mathcal{M} \subset \mathbb{R}^D$. Hoewel data in veel toepassingen (met name beeldvorming) voldoet aan de variëteitsveronderstelling (lage intrinsieke dimensie ondanks een hoge extrinsieke dimensie), is de variëteit doorgaans onbekend en alleen toegankelijk via een eindige verzameling steekproeven (een puntenwolk) $\{x_i\}_{i=1}^n \subset \mathcal{M}$.

Standaard gradiëntafdaling in de omringende Euclidische ruimte faalt in deze context om twee primaire redenen:

1. Geometrische Beperking: Iteraties kunnen afdrijven van de variëteit, de regio's binnen waar de energielandschap of gradiëntinformatie onbetrouwbaar of ongedefinieerd is.
2. Geleerde Operatorcorrectie: Geleerde correcties (bijv. neurale netwerken die een goedkoop forward model corrigeren) worden getraind op specifieke datavariëteiten. Deze correcties falen vaak of produceren foutieve gradiënten wanneer iteraties de nabijheid van de trainingsdata verlaten. Bestaande methoden die proberen dit te corrigeren door punten langs de optimalisatietrajecorie toe te voegen, zijn computationeel evenredig duur.

Methodologie
De auteurs stellen een tweestaps gradiëntafdaling-schema voor dat direct op de puntenwolk opereert zonder een expliciete parametrisatie van de variëteit te vereisen. De methode gaat ervan uit dat de variëteit een compacte, $d$-dimensionale, tweemaal continu differentieerbare Riemannse variëteit met een positieve reach is.

1. Continu Formulering (Bekende Variëteit):
   De auteurs definiëren eerst een gradiëntstroom voor een bekende variëteit $\mathcal{M}$:
   $$\dot{\xi}(t) = -\Pi_{T_{\xi(t)}\mathcal{M}} \nabla E(\xi(t)) + \lambda n(\xi(t))$$
   waarbij $\Pi_{T_{\xi(t)}\mathcal{M}}$ de projectie op de raakruimte is, $n(\xi(t)) = P_\mathcal{M}(\xi(t)) - \xi(t)$ de normaalvector is die naar de variëteit wijst, en $\lambda > 0$ een strafparameter is. Deze stroom zorgt ervoor dat de sequentie convergeert naar de variëteit terwijl de energie wordt geminimaliseerd.

2. Discreet Schema (Onbekende Variëteit):
   Omdat de variëteit onbekend is, worden de raakruimten en normaalvectoren benaderd met behulp van lokale Principale Componenten Analyse (PCA) op de steekproeven van de puntenwolk.

   • Stap 1 (Tangentiële Afdaling): De gradiënt wordt geprojecteerd op een geschatte raakruimte. Dit wordt bereikt door projecties te middelen op de raakruimten van de $K$-dichtstbijzijnde buren van de huidige iteratie $\xi_k$. De raakruimte in een punt $x_i$ wordt geschat via de eigenvectoren van de lokale empirische covariantie-matrix.
   • Stap 2 (Normale Correctie): De iteratie wordt teruggeprojecteerd naar de variëteit. De normaalvector wordt geschat door het verschil te middelen tussen de huidige punt en het lokale gemiddelde van de variëteitssteekproeven, geprojecteerd op de geschatte normaalruimte (het orthogonale complement van de raakruimte).

   Het algoritme roteert tussen deze stappen, wat ervoor zorgt dat de trajectorie binnen een tubulaire buurt van de variëteit blijft.

Theoretische Bijdragen
Het artikel biedt een rigoureuze convergentieanalyse onder geschikte stabiliteits- en steekproefveronderstellingen:

• Convergentie naar de Variëteit: De auteurs bewijzen dat het discrete schema convergeert naar de oplossing van de continue gradiëntstroom PDE naarmate de tijdstap $\tau \to 0$.
• Foutgrenzen: Ze stellen vast dat de afstand van de iteraties tot de variëteit verdwijnt naarmate de tijdstap, de steekproeffout en de fout in de raakvlakschatting verdwijnen.
• Convergentie naar Lokale Minimale: Onder aannames van geodetische convexiteit en lokale exponentiële stabiliteit, convergeert het discrete schema naar een lokaal minimum. De foutgrens hangt af van de consistentie van de geleerde tangentiële en normale benaderingen ($\beta$ en $\gamma$).
• PCA Consistentie: Het artikel bevat een bewijs (Theorem 2.6) dat laat zien dat de PCA-gebaseerde raakvlakbenadering convergeert naar het ware raakvlak met een snelheid die afhankelijk is van de steekproefdichtheid en de gladheid van de variëteitsdichtheid.

Toepassingen en Resultaten
De methodologie wordt toegepast op Geleerde Operatorcorrectie in inverse problemen, specif씩 Fotoakoestische Tomografie (PAT).

• Context: In PAT is het exacte forward model $A$ computationeel duur, terwijl een goedkoop benaderingsmodel $\tilde{A}$ artefacten introduceert. Een neuraal netwerk wordt getraind om de normale operator $\tilde{A}^*\tilde{A}$ te corrigeren om $A^*A$ te benaderen.
• Probleem: Standaard optimalisatie met de geleerde correctie divergeert of produceert artefacten wanneer iteraties de trainingsdatavariëteit verlaten omdat de correctie buiten dit gebied onbetrouwbaar is.
• Experimenten:
  • Synthetische 2D Variëteit in 3D: De auteurs laten zien dat gradiëntafdaling op puntenwolken robuust is tegen ruisige gradiënten (waarbij de ruis schaalt met de afstand tot de variëteit), terwijl standaard Euclidische gradiëntafdaling onder dezelfde ruiscondities significant faalt.
  • PAT Reconstructie:
    • Zonder variëteitsbeperkingen faalt de geleerde correctie om tot een goede oplossing te convergeren, waarbij artefacten worden geproduceerd die slechter zijn dan de ongecorrigeerde benadering.
    • Met de voorgestelde puntenwolk gradiëntafdaling wordt de optimalisatie beperkt tot de datavariëteit. De resultaten tonen aan dat de gecorrigeerde methode convergeert naar een oplossing met een nauwkeurigheid die vergelijkbaar is met het dure exacte model, wat de ongecorrigeerde benadering aanzienlijk overtreft.
    • De methode blijkt robuust voor het aantal steekproeven, hoewel de prestaties licht afnemen bij minder steekproeven door toegenomen ruis in de gradiëntschatting.

Betekenis en Claims
De auteurs beweren dat hun primaire nieuwheid ligt in het ontwikkelen van een bewijsbaar convergerende gradiëntafdaling methode die direct opereert op onbekende variëteiten die uitsluitend worden gerepresenteerd door puntenwolken.

• In tegenstelling tot klassieke benaderingen die expliciete geometrische kennis vereisen, combineert deze methode lokale raakvlakschatting en projectie om iteraties dicht bij de datavariëteit te houden.
• Het raamwerk is bijzonder effectief voor geleerde operatorcorrectie, omdat het de optimalisatie stabiliseert door excursies naar regio's te voorkomen waar geleerde modellen onnauwkeurig zijn.
• Het artikel positioneert dit als een brug tussen variëteitsgebaseerde optimalisatie en datagestuurde modellering, waardoor gradiëntgebaseerde methoden mogelijk worden in settings waar de onderliggende geometrie niet expliciet bekend is maar datasteekproeven beschikbaar zijn.

De auteurs blijven bescheiden en merken op dat, hoewel de methode de optimalisatie stabiliseert, de gecorrigeerde gradiënten niet perfect zijn zelfs op de variëteit, wat strategieën zoals vroege stopzetting noodzakelijk maakt. Ze erkennen ook dat fijne bemonstering van de variëteit noodzakelijk is voor een hoge nauwkeurigheid, wat suggereert dat adaptieve bemonstering nabij het minimum een toekomstige vereiste kan zijn voor bredere toepassing.