Approximation theorems in bilipschitz invariant theory

1. Il Problema

La teoria invariante bilipschitziana si occupa dell'immersione a bassa distorsione di spazi delle orbite in spazi euclidei.
Sia $G \le O(d)$ un gruppo finito che agisce sullo spazio euclideo $\mathbb{R}^d$. L'azione di $G$ partiziona $\mathbb{R}^d$ in orbite $[x] = G \cdot x$, formando lo spazio delle orbite $\mathbb{R}^d/G$. Questo spazio è dotato di una metrica quoziente:
$$d_{\mathbb{R}^d/G}([x], [y]) = \min_{g \in G} \|x - gy\|.$$
L'obiettivo è trovare una mappa $f: \mathbb{R}^d \to \mathbb{R}^n$ invariante per $G$ tale che la mappa indotta $f_\downarrow: \mathbb{R}^d/G \to \mathbb{R}^n$ sia bilipschitziana con la distorsione minima possibile. La distorsione è definita come il rapporto tra la costante di Lipschitz superiore ($\beta$) e quella inferiore ($\alpha$):
$$\text{dist}(f_\downarrow) = \frac{\beta(f_\downarrow)}{\alpha(f_\downarrow)}.$$
La distorsione minima teorica raggiungibile è nota come distorsione euclidea dello spazio delle orbite, denotata $c_2(\mathbb{R}^d/G)$.

Fino ad ora, le mappe ottimali (che raggiungono $c_2$) erano note solo per pochi casi specifici:

1. Rotazioni piane ($d=2$, $G \le SO(2)$).
2. Recupero di fase reale ($G = \{\pm I\}$).
3. Gruppi di riflessione finiti.

In questi casi, le mappe ottimali note godono della proprietà di omogeneità positiva ($h(rx) = rh(x)$). Tuttavia, non esisteva un approccio universale per costruire tali mappe o per approssimare la distorsione ottimale in modo sistematico.

2. Metodologia

Gli autori propongono un approccio universale basato sulla composizione di un banco di filtri massimi (max filter bank) con una trasformazione lineare.

Il Concetto di Max Filter

Dato un template $y \in \mathbb{R}^d$, il filtro massimo è definito come:
$$\langle\langle [x], [y] \rangle\rangle = \max_{g \in G} \langle x, gy \rangle.$$
Un banco di filtri massimi $\Phi$ utilizza $m$ template per mappare $\mathbb{R}^d/G$ in $\mathbb{R}^m$. Sebbene i filtri massimi da soli forniscano immersioni bilipschitziane, la loro distorsione è spesso subottimale (specialmente per i gruppi di riflessione, dove la distorsione può essere $\Theta(d)$ invece di 1).

L'Ipotesi Principale

Il paper dimostra che, per le tre classi di gruppi citate sopra, la distorsione minima $c_2(\mathbb{R}^d/G)$ può essere quasi raggiunta (o raggiunta esattamente) componendo un banco di filtri massimi $\Phi$ con una mappa lineare $L$:
$$f = L \circ \Phi.$$
La strategia di prova si articola in due fasi fondamentali:

1. Riduzione a spazi di funzioni Lipschitz: Si dimostra che è sufficiente mostrare che le funzioni coordinate di un'immersione bilipschitziana ottimale $h$ appartengono alla chiusura di Lipschitz dello span (spazio vettoriale) dei filtri massimi. La vicinanza nella norma di Lipschitz implica la vicinanza nella distorsione.
2. Dimostrazione dell'inclusione: Si prova che le funzioni coordinate ottimali possono essere approssimate arbitrariamente bene da combinazioni lineari di filtri massimi.

Strumenti Matematici

• Teorema di Rademacher forte: Utilizzato per caratterizzare la norma di Lipschitz attraverso il gradiente essenziale.
• Analisi Armonica: Per i casi di rotazioni piane e recupero di fase, le funzioni coordinate ottimali (che sono polinomi invarianti) vengono espresse come combinazioni integrali di filtri massimi. Questo permette di approssimare l'integrale con somme di Riemann (combinazioni lineari finite).
• Armoniche Sferiche: Utilizzate nel caso del recupero di fase reale ($G=\{\pm I\}$) per decomporre i polinomi invarianti rispetto alla sfera.
• Geometria dei Gruppi di Riflessione: Per i gruppi di riflessione, si dimostra che lo span dei filtri massimi è finito-dimensionale e coincide esattamente con lo span delle funzioni coordinate ottimali.

3. Contributi Chiave

1. Teorema Principale (Teorema 3): Per le tre classi di gruppi (rotazioni piane, recupero di fase reale, gruppi di riflessione), per ogni $\epsilon > 0$, esiste un banco di filtri massimi $\Phi$ e una mappa lineare $L$ tali che la distorsione di $L \circ \Phi$ è al massimo $c_2(\mathbb{R}^d/G) + \epsilon$. Nel caso dei gruppi di riflessione, l'uguaglianza esatta ($\epsilon=0$) è raggiungibile.
2. Teorema di Inclusione (Teorema 5): Gli autori classificano le relazioni tra diversi spazi di funzioni invarianti:
   • Lo span delle funzioni coordinate ottimali è contenuto nella chiusura di Lipschitz dello span dei filtri massimi.
   • Viene mostrato che questi casi non possono essere trattati con un'unica dimostrazione unificata perché le interazioni con altri spazi funzionali (come i polinomi omogenei o le funzioni lineari a tratti) variano drasticamente tra i casi.
3. Dimostrazione della Superiorità della Riduzione Dimensionale: A differenza di teoremi precedenti che mostravano come la riduzione dimensionale non danneggi l'iniettività ("non fa male"), questo lavoro dimostra che la riduzione dimensionale tramite una mappa lineare post-composta migliora la distorsione ("aiuta"), permettendo di raggiungere l'ottimalità.
4. Risultati Numerici: Gli autori testano l'approccio su gruppi non trattati teoricamente (es. gruppi ciclici complessi, gruppi di simmetria di poligoni) e su dati reali (distretti congressuali USA, dataset di forme 2D).

4. Risultati Sperimentali

Gli esperimenti numerici confermano la validità dell'approccio "LMF" (Linear Max Filter) al di là dei casi teorici provati:

• Confronto Architetture: L'approccio LMF (banco di filtri massimi + strato lineare addestrato) supera costantemente i filtri massimi puri (MF), le reti neurali ReLU standard (che non sono invarianti senza augmentation) e i polinomi invarianti grezzi.
• Casi Specifici:
  • Per $\mathbb{R}^2/\{\pm I\}$, LMF raggiunge una distorsione empirica molto vicina a $\sqrt{2}$ (il limite teorico), superando il limite inferiore dei filtri massimi puri ($\approx 1.659$).
  • Per gruppi di riflessione e altri gruppi finiti, LMF ottiene le distorsioni più basse tra tutte le architetture testate.
• Applicazioni Reali:
  • Distretti Congressuali: L'embedding LMF dei distretti congressuali USA ha rivelato strutture geometriche significative, separando i distretti gerrymandered (manipolati) in base a convessità ed eccentricità.
  • Forme 2D: L'analisi delle forme ha permesso di visualizzare lo spazio delle forme in modo geometricamente interpretabile, distinguendo classi di oggetti in base a caratteristiche topologiche e geometriche.

5. Significato e Implicazioni

Questo lavoro rappresenta un passo avanti fondamentale nella teoria degli invarianti per l'apprendimento automatico e l'elaborazione dei segnali:

• Universalità Pratica: Suggerisce che l'architettura "Max Filter + Lineare" è un candidato universale per costruire feature map invarianti a bassa distorsione, senza bisogno di progettare manualmente invarianti specifici per ogni gruppo.
• Efficienza: Dimostra che è possibile ottenere la massima fedeltà geometrica (bassa distorsione) mantenendo una dimensione di output ridotta, essenziale per l'efficienza computazionale nel machine learning.
• Nuova Direzione di Ricerca: Apre la strada alla domanda se questo risultato si estenda a qualsiasi sottogruppo chiuso di $O(d)$ (Problema 6 nel paper), suggerendo che la struttura dei filtri massimi potrebbe essere più potente di quanto precedentemente ipotizzato.

In sintesi, il paper stabilisce che la combinazione di filtri massimi (che catturano la struttura geometrica non lineare delle orbite) e trasformazioni lineari (che ottimizzano la metrica euclidea risultante) è una strategia robusta e quasi ottimale per l'immersione di spazi delle orbite, con applicazioni dirette e promettenti nell'analisi di dati simmetrici.