Robust Tangent Space Estimation via Laplacian Eigenvector Gradient Orthogonalization

Sintesi Tecnica: Stima Robusta dello Spazio Tangente tramite LEGO

Problematica
Stimare gli spazi tangenti di un manifold di dati è un compito fondamentale nell'analisi geometrica dei dati, che sostiene applicazioni quali l'apprendimento di varietà (manifold learning), la rimozione del rumore dai dati, la rilevazione dei bordi e la stima della dimensione intrinseca locale. L'approccio standard, la PCA Locale (LPCA), costruisce una matrice di covarianza locale partendo dai $k$-vicini più prossimi per identificare la base tangente. Tuttavia, la LPCA soffre di un compromesso critico riguardante la dimensione del vicinato: i vicinati piccoli sono altamente suscettibili alla corruzione da rumore, mentre i vicinati più grandi introducono bias dovuto alla curvatura sottostante e al reach del manifold. La selezione di una dimensione ottimale del vicinato richiede tipicamente una conoscenza a priori delle caratteristiche geometriche e del rumore che spesso non è disponibile, rendendo il problema mal posto in contesti ad alto rumore.

Metodologia: LEGO
Gli autori propongono LEGO (Laplacian Eigenvector Gradient Orthogonalization), un metodo spettrale che sfrutta la struttura globale dei dati per guidare la stima dello spazio tangente locale. Invece di fare affidamento esclusivamente sui vicinati locali, LEGO stima lo spazio tangente in ogni punto del dato attraverso l'ortogonalizzazione dei gradienti degli autovettori a bassa frequenza del Laplaciano del grafo costruito dai dati rumorosi.

L'algoritmo procede come segue:

1. Costruzione del Grafo: Un grafo Laplaciano $L$ viene costruito dal nuvolo di punti rumoroso utilizzando metodi basati su kernel (ad esempio, random walk, self-tuned o doubly stochastic kernels).
2. Stima del Gradiente: I gradienti dei primi $m$ autovettori a bassa frequenza ($\phi_1, \dots, \phi_m$) vengono stimati in ogni punto del dato. Per garantire fedeltà locale e stabilità numerica, questi gradienti sono modellati come vettori nello span dei primi $m_0$ autovettori ($m_0 \gg m$).
3. Regolarizzazione: Viene applicato un termine di regolarizzazione di Tikhonov al processo di stima del gradiente per prevenire l'instabilità numerica in contesti a basso rumore o con rango debole. Il parametro di regolarizzazione $\eta_j$ è derivato dalla geometria del vicinato locale, con un iperparametro $\beta$ che controlla la potenza della penalità della distanza.
4. Ortogonalizzazione: In ogni punto $j$, i vettori gradiente stimati $\hat{\nabla}\phi(X_j)$ vengono ortogonalizzati (tramite SVD) per estrarre la base ortonormale $Q_j$ dello spazio tangente $d$-dimensionale. Se la dimensione intrinseca $d$ è ignota, essa viene inferita dai valori singolari della matrice del gradiente.

Giustificazioni Teoriche
Il documento fornisce due quadri teorici complementari per giustificare la robustezza di LEGO:

1. Prospettiva della Geometria Differenziale:
   Gli autori modellano i dati rumorosi come campionamenti da un vicinato tubolare $T_{\epsilon r}$ che circonda un sotto-manifold pulito $B$ di dimensione $d$. Analizzano gli autofunzioni di Neumann del Laplaciano su questo tubo.

   • Risultato Chiave: Stabiliscono dei limiti che mostrano come l'autovalore $\lambda$ di un autofunzione scali come $\Omega(\epsilon^{-2} E^\perp_B(\phi))$ rispetto alla sua "energia verticale" (gradiente nella direzione del rumore) e come $O(E_B(\phi))$ rispetto alla sua "energia orizzontale" (gradiente lungo il manifold).
   • Implicazione: Le autofunzioni con gradienti significativi nella direzione del rumore devono avere autovalori elevati. Al contrario, le autofunzioni a bassa frequenza hanno gradienti concentrati nello spazio tangente (orizzontale), rendendo i loro gradienti stimatori robusti del bundle tangente.

2. Prospettiva della Teoria delle Matrici Casuali:
   Gli autori analizzano la stabilità degli autovettori del Laplaciano sotto rumore sub-gaussiano utilizzando un modello "informazione più rumore" dove la varianza proxy del rumore $\epsilon$ scala come $O(1/\sqrt{n \log n})$.

   • Risultato Chiave: Dimostrano che il Laplaciano del grafo rumoroso converge al Laplaciano pulito in norma operatore con un tasso di $O(n^{-1/2})$. In base al teorema di Davis-Kahan, a condizione che i gap spettrali del Laplaciano pulito non decadano troppo rapidamente, gli autovettori del Laplaciano rumoroso rimangono vicini a quelli del Laplaciano pulito.
   • Implicazione: In queste condizioni, le componenti orizzontali dei gradienti stimati dai dati rumorosi convergono a quelle dei dati puliti, garantendo la stabilità delle stime dello spazio tangente.

Contributi Principali

• Proposta Algoritmica: Introduzione di LEGO, un algoritmo spettrale per la stima robusta dello spazio tangente che evita il compromesso sulla dimensione del vicinato tipico della LPCA.
• Quadro Teorico: Derivazione delle leggi di scala asintotiche per i gradienti degli autovettori sotto un modello di rumore tubolare e prova della stabilità degli autovettori sotto perturbazioni di rumore sub-gaussiano.
• Guida agli Iperparametri: Derivazione teorica che suggerisce $\beta = 1/2$ come parametro di regolarizzazione di Tikhonov ottimale quando le caratteristiche del rumore sono ignote.
• Validazione Empirica: Esperimenti completi che dimostrano la superiorità di LEGO rispetto alla LPCA in contesti rumorosi.

Risultati
Esperimenti numerici su dataset sintetici (Swiss roll ad alto rapporto d'aspetto, toro troncato) e dati reali (dataset Puppets) dimostrano che:

• Accuratezza: LEGO produce stime dello spazio tangente significativamente più robuste al rumore rispetto alla LPCA. La discrepanza tra lo spazio tangente stimato e quello reale rimane bassa anche all'aumentare dei livelli di rumore, mentre le stime della LPCA degradano rapidamente.
• Performance nei Task a Valle: Le stime migliorate dello spazio tangente portano a marcati miglioramenti nei compiti successivi:
  • Apprendimento di Manifold: LEGO produce embedding 2D accurati che preservano la topologia intrinseca (ad esempio, rivelando la struttura toroidale del dataset Puppets), mentre gli embedding basati su LPCA collassano o diventano non iniettivi.
  • Rilevazione dei Bordi: I punti di bordo rilevati tramite LEGO si allineano strettamente con la verità fondamentale (ground truth), mentre la LPCA fallisce nell'identificare i bordi accuratamente in condizioni di rumore.
  • Stima della Dimensione Intrinseca: LEGO concentra correttamente la varianza funzionale nelle vere dimensioni intrinseche, mentre la LPCA assegna erroneamente la varianza alle direzioni del rumore.

Significatività
Il documento afferma che LEGO offre un'alternativa fondata ai metodi locali utilizzando l'informazione spettrale globale per filtrare il rumore. Dimostrando che gli autovettori a bassa frequenza del Laplaciano del grafo si allineano naturalmente con il bundle tangente del manifold sottostante sopprimendo al contempo le componenti del rumore, gli autori forniscono una soluzione robusta al problema della selezione della dimensione del vicinato. Questo approccio consente un'analisi geometrica accurata in regimi di alto rumore dove i metodi locali standard falliscono, facilitando un apprendimento di varietà e una riduzione della dimensionalità più affidabili.