Euclidean Distance Degrees in Macaulay2

Sintesi Tecnica: Grado di Distanza Euclidea in Macaulay2

Enunciato del Problema
Il grado di distanza euclidea (ED degree) è un invariante fondamentale nell'ottimizzazione algebrica, che misura la complessità dei problemi di punto più vicino per varietà reali. Nello specifico, per un punto di dato generico $u \in \mathbb{R}^n$ e una varietà $X \subseteq \mathbb{R}^n$, il grado ED è definito come il numero di punti critici complessi non singolari della funzione di distanza euclidea al quadrato $\|x - u\|^2$ (o di una variante pesata $\|x - u\|_w^2$) ristretta a $X$. Sebbene molti modelli scientifici e ingegneristici siano espressi tramite sistemi polinomiali, gli strumenti per calcolare i gradi ED per varietà arbitrarie sono stati limitati. Questo articolo affronta la necessità di un'implementazione software robusta capace di calcolare questi gradi utilizzando tecniche di geometria algebrica sia simboliche che numeriche.

Metodologia
Gli autori introducono il pacchetto EuclideanDistanceDegree per il sistema di calcolo computazionale Macaulay2. Il pacchetto implementa quattro distinti approcci algoritmici per calcolare i gradi ED, categorizzati in base alla natura della varietà di input (implicita o parametrizzata) e alla strategia computazionale (simbolica o numerica):

1. Metodo dei Minori (Simbolico):

   • Approccio: Questo metodo tratta la varietà $X$ come una varietà complessa definita da un ideale primo $I_X$. Costruisce una matrice Jacobiana aumentata $\hat{J}$ appendendo un vettore riga derivato dal gradiente della distanza pesata alla Jacobiana standard $J$ dei polinomi definitori.
   • Computazione: L'ideale critico pesato viene calcolato tramite saturazione: $C_{X,u,w} = (I_X + \text{minors}_{c+1}(\hat{J})) : I_{X_{sing}}^\infty$.
   • Output: Il grado di questo ideale fornisce il grado ED. Questo approccio è implementato in modo simbolico e può restituire le equazioni esplicite dell'ideale critico.

2. Metodo del Nucleo Sinistro (Numerico/Intersezioni Complete):

   • Approccio: Progettato per varietà di grande codimensione dove il metodo dei minori è computazionalmente proibitivo a causa del passaggio di saturazione e dell'esplosione dei minori. Utilizza i moltiplicatori di Lagrange per risolvere direttamente le equazioni dei punti critici.
   • Computazione: Per una intersezione completa definita da $f_1, \dots, f_k$, viene formato il sistema $G(x, \lambda) = 0$, che combina i polinomi definitori con la condizione del moltiplicatore di Lagrange $\lambda_0(x-u) + \sum \lambda_i \nabla f_i = 0$.
   • Implementazione: Questo sistema viene risolto numericamente utilizzando il software Bertini tramite l'omotopia di continuazione.

3. Metodo dell'Omotopia (Numerico/Oltre le Intersezioni Complete):

   • Approccio: Un'estensione del metodo del nucleo sinistro adatta a varietà che non sono intersezioni complete o per esplorare pesi parametrizzati.
   • Computazione: Impiega un processo di omotopia di continuazione a due stadi. Primo, un "sistema di partenza" viene risolto usando pesi generici per stabilire un limite iniziale sul grado ED. Secondo, un'omotopia di parametri traccia queste soluzioni verso il sistema target (pesi o dati specifici).
   • Efficienza: Ciò consente la computazione efficiente di gradi ED per molteplici configurazioni di pesi o dati, poiché lo stadio iniziale deve essere eseguito solo una volta.

4. Metodo delle Varietà Conormali (Parametrizzata):

   • Approccio: Mirato a varietà date da una parametrizzazione $\phi: \mathbb{C}^d \to \mathbb{C}^n$.
   • Computazione: Costruisce una varietà conormale affine trovando il nucleo della Jacobiana trasposta della parametrizzazione. I punti critici sono identificati come coppie $(x, \lambda)$ che soddisfano un sistema lineare specifico che coinvolge la parametrizzazione e i generatori del nucleo.
   • Implementazione: Questo può essere calcolato simbolicamente o numericamente utilizzando il pacchetto MonodromySolver.

Contributi Chiave

• Pacchetto Software: Il contributo primario è il pacchetto Macaulay2 EuclideanDegreeDistance, che unifica i metodi simbolici e numerici per la computazione del grado ED.
• Diversità Algoritmica: Il pacchetto fornisce implementazioni per quattro metodi distinti (Minori, Nucleo Sinistro, Omotopia, Conormale), permettendo agli utenti di selezionare lo strumento più appropriato in base alla struttura della varietà (es. codimensione, implicita vs parametrizzata) e all'output desiderato (grado simbolico esatto vs approssimazione numerica).
• Interoperabilità: I metodi simbolici includono un'opzione per restituire i polinomi generatori dell'ideale critico, facilitando la replicazione e la validazione incrociata con altri software come HomotopyContinuation.jl.
• Robustezza Numerica: Il pacchetto si integra con Bertini e MonodromySolver, offrendo opzioni di configurazione per gestire i fallimenti dei percorsi (es. percorsi che divergono all'infinito) e supportando il calcolo di gradi ED unitari, pesati e generici.

Risultati ed Esempi
Il documento valida il pacchetto attraverso una gamma di esempi:

• Verifica Simbolica: Il pacchetto calcola con successo il grado ED unitario (5) e il grado ED generico (9) per la superficie Dingdong, recuperando le equazioni dell'ideale critico.
• Computazione Numerica: Calcola il grado ED pesato (22) per la superficie Daisy utilizzando dati e pesi specifici.
• Efficienza dell'Omotopia: Il pacchetto dimostra che dopo aver calcolato un grado ED unitario, i successivi gradi ED generici possono essere calcolati efficientemente riutilizzando lo stadio iniziale dell'omotopia. Un esperimento su un'ellisse produce un grado ED reale medio di circa 3.41 su 100 campioni, coerente con le aspettative teoriche.
• Applicazioni:
  • Reti Neurali Polinomiali: Il pacchetto calcola il grado ED generico per reti neurali polinomiali superficiali (es. grado 13 per specifiche architetture), seguendo lavori precedenti sulle neurovarietà.
  • Varietà Multiview: Calcola i gradi ED per varietà multiview affini ancorate a superfici razionali, trovando gradi di 8 e 12 per configurazioni specifiche, fornendo prove empiriche per potenziali generalizzazioni di risultati noti per curve razionali.

Significato
L'articolo posiziona il pacchetto EuclideanDistanceDegree come uno strumento specializzato che colma una lacuna nel panorama della geometria algebrica computazionale. Mentre esistono pacchetti simbolici generali (come AlgebraicOptimization o ToricInvariants) per setting specifici, e solver numerici generali (come Bertini o PHCpack) per la risoluzione numerica, questo pacchetto offre un'interfaccia dedicata e user-friendly specificamente per i gradi ED. Esso colma il divario tra l'esattezza simbolica e la scalabilità numerica, consentendo ai ricercatori nell'ottimizzazione algebrica, la visione artificiale e il machine learning di comprendere meglio la complessità algebrica dei loro modelli calcolando questi invarianti critici. Gli autori osservano che, sebbene non esistesse precedentemente un pacchetto numerico dedicato per l'ED, il loro strumento sfrutta i robusti solver esistenti per fornire un flusso di lavoro snello per questi problemi specifici.