A Data-Driven Interpolation Method on Smooth Manifolds via Diffusion Processes and Voronoi Tessellations

Titolo del Lavoro

Metodo di Interpolazione Basato sui Dati per Varietà Lisce tramite Processi di Diffusione e Tassellazioni di Voronoi

1. Il Problema

Il lavoro affronta la sfida di approssimare funzioni reali lisce definite su varietà lisce ($M \subset \mathbb{R}^d$) partendo da un insieme finito di valutazioni puntuali. Questo problema è centrale nell'apprendimento delle varietà (manifold learning) e in applicazioni inverse come la tomografia computerizzata (CT) con viste sparse.
Le sfide principali identificate includono:

• Complessità Computazionale: I metodi classici basati sui dati, come le Reti Neurali (FNN), le Reti a Funzioni di Base Radiale (RBF) e la Regressione Gaussiana (GPR), richiedono fasi di addestramento costose (spesso con complessità $O(N^2)$ o $O(N^3)$) e possono soffrire di instabilità numerica o convergenza lenta.
• Ricostruzione da Dati Sparsi: Nella tomografia a viste sparse, la scarsità dei dati angolari porta a problemi mal posti, introducendo oscillazioni spurie e degradando la qualità dell'immagine ricostruita.
• Mancanza di Adattabilità Geometrica: Molti metodi non sfruttano efficacemente la geometria intrinseca dei dati o richiedono pre-elaborazioni complesse.

2. Metodologia Proposta

L'autore propone un metodo di interpolazione puramente basato sui dati, privo di fase di addestramento, che combina l'operatore di Laplace-Beltrami, i processi di diffusione e le tassellazioni di Voronoi.

• Approccio Geometrico e Diffusivo:
  Il metodo si basa sull'ipotesi che i dati giacciano su una varietà liscia. Utilizza un kernel Gaussiano $G_\varepsilon(z) = \exp(-\|z\|^2/\varepsilon^2)$ per definire un'approssimazione convoluta della funzione $g$. Teoricamente, per $\varepsilon \to 0$, questa approssimazione converge alla funzione originale più un termine legato all'operatore di Laplace-Beltrami ($\Delta g$).

• Parametro di Scala Adattivo ($\varepsilon(x)$):
  Un elemento cruciale è la selezione dinamica del parametro di scala $\varepsilon$. Invece di usare un valore globale fisso (che può causare instabilità numerica se troppo piccolo o perdita di dettaglio se troppo grande), il metodo definisce $\varepsilon(x)$ come la distanza dal punto di query $x$ al punto campione più vicino:
  $$\varepsilon(x) = \min_{1 \le i \le N} \|x - x_i\|$$
  Questa scelta è intrinsecamente legata alla tassellazione di Voronoi generata dai dati. Garantisce che il fattore di normalizzazione rimanga limitato inferiormente, prevenendo instabilità numeriche, e adatta la scala di diffusione alla densità locale dei dati.

• Formula di Interpolazione Chiusa:
  L'interpolante $\bar{g}(x)$ è calcolato direttamente tramite una formula esplicita (media pesata dei valori dei campioni con pesi Gaussiani adattivi):
  $$\bar{g}(x) = \frac{\sum_{i=1}^N G_{\varepsilon(x)}(x - x_i) g(x_i)}{\sum_{i=1}^N G_{\varepsilon(x)}(x - x_i)}$$
  Non è richiesto alcun addestramento iterativo (come la retropropagazione nelle reti neurali).

• Applicazione alla Tomografia (Regolarizzazione Angolare):
  Nel contesto della CT a viste sparse, il metodo viene utilizzato come passo di pre-elaborazione. Si interpola il sinogramma (i dati di proiezione) lungo la variabile angolare. Questo agisce come un filtro passa-basso che attenua le alte frequenze (rumore e oscillazioni) mantenendo la fedeltà ai dati misurati, fornendo un'ottima inizializzazione per metodi di ricostruzione iterativa (es. minimizzazione della Variazione Totale - TV).

3. Contributi Chiave

1. Metodologia "Training-Free": Introduzione di un nuovo approccio che evita completamente la fase di addestramento, offrendo una soluzione analitica a forma chiusa.
2. Complessità Lineare: La complessità computazionale per la fase di inferenza scala linearmente ($O(N)$) con il numero di punti campione, offrendo un vantaggio significativo rispetto ai metodi classici (GPR: $O(N^3)$, RBF: $O(N^2)$).
3. Proprietà Teoriche Dimostrate:
   • Gradiente Nullo: È dimostrato che il gradiente dell'interpolante si annulla esattamente nei punti campione e decade esponenzialmente nelle loro vicinanze.
   • Minimizzazione della Variazione Totale: Il metodo è interpretato come una soluzione approssimata a un problema di minimizzazione della variazione totale (TV), fornendo una regolarizzazione implicita.
   • Attenuazione delle Alte Frequenze: Lo spettro della funzione approssimata attenua le componenti ad alta frequenza, agendo come un filtro passa-basso data-driven.
4. Applicazione alla CT: Dimostrazione pratica dell'efficacia nel ridurre i costi computazionali e migliorare la qualità della ricostruzione in scenari di tomografia a viste sparse.

4. Risultati Sperimentali

Gli esperimenti numerici sono stati condotti su due fronti:

• Interpolazione Sintetica (Toro 2D):

  • Confronto con Reti Neurali Feedforward (FNN), GPR e RBF.
  • Risultati: Il metodo proposto ha ottenuto l'errore quadratico medio (MSE) più basso su tutti i livelli di campionamento (da 100 a 2000 punti).
  • Efficienza: Ha richiesto tempi di calcolo significativamente inferiori rispetto alle controparti, specialmente all'aumentare della dimensione del dataset.

• Ricostruzione Tomografica (CT):

  • Test su fantocci (Shepp-Logan) e immagini reali (testa e addome umano) con proiezioni sparse (100 e 300 angoli).
  • Qualità dell'Immagine: Il metodo proposto ha prodotto sinogrammi e immagini ricostruite più stabili e fedeli rispetto a spline cubiche, FNN e RBF, competendo direttamente con la GPR ma con costi computazionali drasticamente inferiori.
  • Sinergia con TV: Quando usato come inizializzazione per algoritmi di regolarizzazione TV iterativa, il metodo proposto ha raggiunto l'errore minimo molto più velocemente rispetto all'inizializzazione con FBP (Filtered Back Projection). In alcuni casi, ulteriori iterazioni TV partendo dalla soluzione proposta hanno addirittura aumentato l'errore, suggerendo che la soluzione proposta è già vicina all'ottimo regolarizzato.

5. Significato e Impatto

Questo lavoro rappresenta un avanzamento significativo nel campo dell'approssimazione di funzioni su varietà e della ricostruzione di immagini inverse.

• Efficienza Scalabile: Elimina il collo di bottiglia dell'addestramento, rendendo possibile l'interpolazione in tempo reale su grandi dataset senza pre-elaborazione.
• Robustezza Geometrica: L'uso delle tassellazioni di Voronoi per adattare il parametro di diffusione garantisce che il metodo sia robusto a distribuzioni di dati non uniformi.
• Ponte tra Teoria e Applicazione: Fornisce un collegamento teorico solido tra i processi di diffusione, la geometria delle varietà e la teoria del compressed sensing, offrendo una soluzione pratica a problemi di ricostruzione medica complessi.
• Versatilità: La metodologia è presentata come un approccio generale applicabile non solo alla tomografia, ma anche a problemi di ingegneria, finanza quantitativa e risoluzione numerica di equazioni differenziali alle derivate parziali.

In sintesi, il metodo proposto offre un compromesso ottimale tra accuratezza, stabilità numerica ed efficienza computazionale, superando molte limitazioni delle tecniche di interpolazione basate sui dati tradizionali.