Uncertainty Principle for Vertex-Time Graph Signal Processing

Sintesi Tecnica: Principio di Incertezza per l'Elaborazione di Segnali su Grafi Vertice-Tempo

Definizione del Problema
Gli attuali framework di Elaborazione di Segnali su Grafi (GSP) si concentrano principalmente sulla localizzazione all'interno del dominio dei vertici o del classico dominio tempo-frequenza. Sebbene siano stati stabiliti principi di incertezza sia per i segnali su grafi (vertice vs. spettrale) che per i segnali a tempo continuo (tempo vs. frequenza), manca un framework unificato che affronti i segnali definiti su domini vertice-tempo irregolari. Applicazioni del mondo reale, come le reti di sensori e sociali, incontrano spesso osservazioni sparse, irregolari o vincolate, dove i sensori registrano dati a intervalli non uniformi, falliscono intermittentemente o riportano dati solo per sottoinsiemi della rete. I metodi convenzionali, come la Trasformata di Fourier Tempo-Vertice a Breve Tempo (STVFT) e la Trasformata Wavelet Spettrale Tempo-Vertice (STVWT), si affidano a basi fisse o assunzioni di campionamento regolare, rendendoli inadatti a catturare l'energia del segnale concentrata su sottoinsiemi di vertici e intervalli temporali irregolari o dipendenti dai dati. Inoltre, i metodi esistenti di apprendimento su grafi spesso ignorano il trade-off intrinseco tra la localizzazione vertice e quella spettrale.

Metodologia
Il documento propone un principio di incertezza generalizzato per i segnali su grafi vertice-tempo che unifica i classici principi di incertezza tempo-frequenza e di grafo. La metodologia procede attraverso i seguenti passaggi:

1. Formulazione Teorica:

   • Gli autori definiscono una trasformata di Fourier congiunta (JFT) per i segnali vertice-tempo $f: \mathcal{V} \times \mathcal{T} \to \mathbb{C}$, mappando i segnali dal dominio vertice-tempo al dominio spettrale-frequenza ($\Lambda \times \Omega$).
   • Introducono la dispersione vertice-tempo ($\alpha_{VT}$) e la dispersione spettrale-frequenza ($\beta_{SF}$) basate sulla concentrazione di energia su sottospazi chiusi di $L^2(\mathcal{V} \times \mathcal{T})$ e $L^2(\Lambda \times \Omega)$, rispettivamente.
   • Il Teorema 1 stabilisce il principio di incertezza, definendo una regione ammissibile $\Theta$ per la coppia $(\alpha_{VT}, \beta_{SF})$. Questa regione è delimitata dal valore massimo dell'autovalore della composizione dell'operatore $\Pi_{SF}\Pi_{VT}\Pi_{SF}$, dove $\Pi$ denota gli operatori di proiezione ortogonale.
   • Il documento identifica le condizioni in cui i segnali possono raggiungere una perfetta localizzazione in entrambi i domini simultaneamente e caratterizza i segnali che massimizzano la concentrazione quando la perfetta localizzazione non è possibile.

2. Apprendimento del Dizionario Vertice-Tempo (Ricostruzione del Segnale):

   • Sfruttando il principio di incertezza, gli autori progettano un Dizionario a Energia Concentrata Congiunta (JECD).
   • Propongono due costruzioni specifiche per gli atomi del dizionario:
     • Sottospazio a Supporto Limitato: Gli atomi sono costruiti come prodotti tensoriali di autovettori di grafi localizzati su un sottoinsieme di vertici $V'$ e Funzioni Sferoidali Prolate (PSWFs) localizzate su un intervallo temporale $T'$. I parametri ($V'$, centro temporale $t_c$, durata $\ell$) sono ottimizzati tramite un algoritmo greedy e minimizzazione alternata per massimizzare la concentrazione di energia sui dati osservati.
     • Sottospazio a Kernel di Calore Gaussiano: Gli atomi sono formati utilizzando atomi di calore su grafo e kernel gaussiani temporali. Le scale di diffusione ($\tau_v, \tau_t$) sono selezionate tramite ricerca su griglia per massimizzare un punteggio di concentrazione.
   • La ricostruzione del segnale viene eseguita risolvendo un problema di codifica sparsa utilizzando il dizionario appreso, accomodando dati irregolari e mancanti senza richiedere il ricampionamento.

3. Inferenza della Topologia del Grafo:

   • Il documento introduce un algoritmo di Apprendimento di Grafi a Energia Concentrata (ECGL).
   • Questo approccio apprende il Laplaciano del grafo $L$ (e i suoi autovettori $U$) massimizzando la concentrazione di energia spettrale-frequenza nel rispetto del trade-off tra localizzazione vertice e spettrale dettato dal principio di incertezza.
   • L'ottimizzazione stima congiuntamente la base di Fourier del grafo, i coefficienti sparsi e la matrice Laplaciana, incorporando la regolarizzazione della variazione totale e vincoli per garantire Laplaciani combinatori validi.

Contributi Chiave

1. Principio di Incertezza Generalizzato: La formulazione di un principio di incenza unificato per i segnali su grafi vertice-tempo che estende le esistenti formulazioni grafo e tempo-continuo attraverso una misura di localizzazione basata su sottospazi.
2. Segnali a Massima Concentrazione: L'identificazione di una classe di segnali vertice-tempo che raggiungono la massima concentrazione nei domini vertice-tempo e spettrale-frequenza, fungendo da atomi fondamentali per un nuovo dizionario.
3. Nuovo Framework di Ricostruzione: Lo sviluppo del metodo JECD, che apprende basi a energia concentrata adattate a pattern di osservazione irregolari, migliorando l'accuratezza della ricostruzione sotto vincoli pratici.
4. Approccio di Apprendimento del Grafo: La proposta di ECGL, un metodo di inferenza del grafo che incorpora esplicitamente i trade-off di localizzazione del principio di incertezza per apprendere topologie di grafi che si allineano con le strutture intrinseche dei segnali.

Risultati Sperimentali
Gli autori validano il loro approccio utilizzando dataset sintetici e reali:

• Ricostruzione del Segnale: Gli esperimenti sul dataset California COVID-19 (58 contee su 2 anni) e sui dati di flusso del traffico mostrano che JECD supera i baseline (JFT, STVFT, STVWT e un'estensione ingenua del principio di incertezza del grafo). JECD ottiene un guadagno medio di 4 dB nell'accuratezza della ricostruzione e dimostra una robustezza superiore, mantenendo prestazioni stabili anche a livelli di rumore di 0 dB.
• Sottospazio Gaussiano: Sui grafi sintetici di Erdős-Rényi, il basis a kernel di calore gaussiano ha ottenuto l'errore quadratico relativo (RSE) più basso attraverso diversi rapporti segnale-rumore (SNR), superando i metodi concorrenti anche in regimi di basso SNR.
• Inferenza della Topologia del Grafo: Su un grafo sintetico, ECGL ha superato TV-GL (Total Variation Graph Learning) ed ESA-GL (Estimated-Signal-Aided Graph Learning). ECGL ha ottenuto un coefficiente di correlazione più elevato (0.9288 vs ~0.927) tra i Laplaciani appresi e quelli reali e ha migliorato il richiamo dei bordi (edge recall) di circa il 4,7%.

Significatività
Il documento afferma che la sua importanza primaria risiede nel colmare il divario tra l'analisi tempo-frequenza classica e l'elaborazione di segnali su grafi per scenari irregolari a tempo continuo. Caratterizzando rigorosamente i trade-off tra la localizzazione vertice-tempo e quella spettrale-frequenza, il lavoro fornisce una base teorica per progettare dizionari che si adattano a supporti guidati dai dati piuttosto che a griglie fisse. Ciò è particolarmente prezioso per applicazioni che coinvolgono la raccolta di dati intermittenti o asincroni, come le reti di sensori, dove i metodi tradizionali non riescono a catturare le concentrazioni di energia localizzate. Inoltre, l'integrazione del principio di incertezza nell'apprendimento del grafo offre un modo principato per inferire strutture di grafi che rispettano i vincoli fisici o strutturali dei segnali sottostanti.