Euclidean Distance Degrees in Macaulay2

Technische Samenvatting: Euclidische Afstand-graden in Macaulay2

Probleemstelling
De Euclidische Afstand (ED) graad is een fundamentele invariant in algebraïsche optimalisatie, die de complexiteit van nabijheidsproblemen voor reële algebraïsche variëteiten meet. Specifiek is de ED-graad gedefinieerd als het aantal niet-singular complexe kritische punten van de gekwadrateerde Euclidische afstandfunctie $\|x - u\|^2$ (of een gewogen variant $\|x - u\|_w^2$) beperkt tot een variëteit $X \subseteq \mathbb{R}^n$, voor een generieke datapunt $u \in \mathbb{R}^n$. Hoewel veel wetenschappelijke en technische modellen worden uitgedrukt in polynomsystemen, waren instrumenten voor het berekenen van ED-graden voor willekeurige variëteiten beperkt. Dit artikel adresseert de behoefte aan een robuuste software-implementatie die in staat is deze graden te berekenen met behulp van zowel symbolische als numerieke algebraïsche geometrie technieken.

Methodologie
De auteurs introduceren het EuclideanDistanceDegree pakket voor het computer algebra systeem Macaulay2. Het pakket implementeert vier verschillende algoritmische benaderingen om ED-graden te berekenen, gecategoriseerd naar de aard van de invoervariëteit (impliciet versus geparametriseerd) en de computationele strategie (symbolisch versus numeriek):

1. Minoren Methode (Symbolisch):

   • Benadering: Deze methode behandelt de variëteit $X$ als een complexe variëteit gedefinieerd door een priem ideaal $I_X$. Het construeert een uitgebreide Jacobiaan-matrix $\hat{J}$ door een rij vector afgeleid van de gewogen afstandsgradiënt toe te voegen aan de standaard Jacobiaan $J$ van de definiërende polynomen.
   • Berekening: Het gewogen kritische ideaal wordt berekend via saturatie: $C_{X,u,w} = (I_X + \text{minors}_{c+1}(\hat{J})) : I_{X_{sing}}^\infty$.
   • Output: De graad van dit ideaal levert de ED-graad op. Deze benadering is symbolisch geïmplementeerd en kan de expliciete vergelijkingen van het kritische ideaal teruggeven.

2. Links Kern Methode (Numeriek/Volledige Doorsneden):

   • Benadering: Ontworpen voor variëteiten met een grote codimensie waar de minoren-methode computationeel onhaalbaar is vanwege de saturatiestap en de explosie van minoren. Het maakt gebruik van Lagrange-multipliers om de kritische puntvergelijkingen direct op te lossen.
   • Berekening: Voor een volledige doorsnede gedefinieerd door $f_1, \dots, f_k$, wordt het systeem $G(x, \lambda) = 0$ gevormd, dat de definiërende polynomen combineert met de Lagrange-multiplier conditie $\lambda_0(x-u) + \sum \lambda_i \nabla f_i = 0$.
   • Implementatie: Dit systeem wordt numeriek opgelost met behulp van het Bertini softwarepakket via homotopie-continuatie.

3. Homotopie Methode (Numeriek/Voorbij Volledige Doorsneden):

   • Benadering: Een uitbreiding van de links kern methode, geschikt voor variëteiten die geen volledige doorsneden zijn of voor het verkennen van geparametriseerde gewichten.
   • Berekening: Het maakt gebruik van een twee-fasen homotopie-continuatieproces. Eerst wordt een "startsysteem" opgelost met generieke gewichten om een initiële bovengrens op de ED-graad vast te stellen. Vervolgens volgt een parameter-homotopie de oplossingen naar het doel-systeem (specifieke gewichten of data).
   • Efficiëntie: Dit maakt het mogelijk om de ED-graden voor meerdere gewichts- of dataconfiguraties efficiënt te berekenen, aangezien de initiële fase slechts één keer uitgevoerd hoeft te worden.

4. Conormale Variëteiten Methode (Geparametriseerd):

   • Benadering: Gericht op variëteiten gegeven door een parametrisatie $\phi: \mathbb{C}^d \to \mathbb{C}^n$.
   • Berekening: Het construeert een affiene conormale variëteit door de kern te vinden van de getransponeerde Jacobiaan van de parametrisatie. De kritische punten worden geïdentificeerd als paren $(x, \lambda)$ die voldoen aan een specifieke lineair systeem met betrekking tot de parametrisatie en de kern-generatoren.
   • Implementatie: Dit kan symbolisch of numeriek berekend worden met behulp van het MonodromySolver pakket.

Belangrijkste Bijdragen

• Softwarepakket: De primaire bijdrage is het EuclideanDistanceDegree Macaulay2 pakket, dat symbolische en numerieke methoden voor ED-graad berekening verenigt.
• Algoritmische Diversiteit: Het pakket biedt implementaties voor vier verschillende methoden (Minoren, Links Kern, Homotopie, Conormaal), waardoor gebruikers de meest geschikte tool kunnen selecteren op basis van de structuur van de variëteit (bijv. codimensie, impliciet versus geparametriseerd) en de gewenste output (exact symbolische graad versus numerieke benadering).
• Interoperabiliteit: De symbolische methoden bevatten een optie om de genererende polynomen van het kritische ideaal terug te geven, wat replicatie en kruisvalidatie met andere software zoals HomotopyContinuation.jl vergemakkelijkt.
• Numerieke Robuustheid: Het pakket integreert met Bertini en MonodromySolver, en biedt configuratieopties om pad-falen (bijv. paden die naar oneindig divergeren) af te handelen en ondersteunt zowel eenheid-, gewogen als generieke ED-graad berekeningen.

Resultaten en Voorbeelden
Het artikel valideert het pakket via een reeks voorbeelden:

• Symbolische Verificatie: Het pakket berekent succesvol de eenheid ED-graad (5) en de generieke ED-graad (9) voor de Dingdong-oppervlakte, waarbij de vergelijkingen van het kritische ideaal worden teruggevonden.
• Numerieke Berekening: Het berekent de gewogen ED-graad (22) voor de Daisy-oppervlakte met specifieke data en gewichten.
• Homotopie Efficiëntie: Het pakket demonstreert dat na het berekenen van een eenheid ED-graad, daaropvolgende generieke ED-graden efficiënt berekend kunnen worden door de initiële homotopie-fase te hergebruiken. Een experiment op een ellips levert een gemiddelde reële ED-graad op van ongeveer 3.41 over 100 monsters, wat consistent is met theoretische verwachtingen.
• Toepassingen:
  • Polynomiale Neurale Netwerken: Het pakket berekent de generieke ED-graad voor ondiepe polynomiale neurale netwerken (bijv. graad 13 voor specifieke architecturen), voortbouwend op eerder werk over neurovariëteiten.
  • Multiview Variëteiten: Het berekent ED-graden voor affiene multiview variëteiten verankerd aan rationale oppervlakken, waarbij het graden van 8 en 12 vindt voor specifieke configuraties, wat empirisch bewijs levert voor potentiële generalisaties van bekende resultaten voor rationale krommen.

Betekenis
Het artikel positioneert het EuclideanDistanceDegree pakket als een gespecialiseerd instrument dat een gat vult in het landschap van computationele algebraïsche geometrie. Terwijl algemene symbolische pakketten (zoals AlgebraicOptimization of ToricInvariants) bestaan voor specifieke settings, en algemene homotopie-solvers (zoals Bertini of PHCpack) bestaan voor numeriek oplossen, biedt dit pakket een toegewijde, gebruiksvriendelijke interface specifiek voor ED-graden. Het overbrugt de kloof tussen symbolische exactheid en numerieke schaalbaarheid, waardoor onderzoekers in algebraïsche optimalisatie, computer vision en machine learning de algebraïsche complexiteit van hun modellen beter kunnen begrijpen door deze kritische invarianten te berekenen. De auteurs merken op dat hoewel er voorheen geen toegewezen numerieke ED-pakket bestond, hun instrument gebruikmaakt van bestaande robuuste solvers om een gestroomlijnde workflow voor deze specifieke problemen te bieden.