Spectral Graph Uncertainty Principles via the Graph Fractional Fourier Transform

Sintesi Tecnica: Principi di Incertezza Spettrale su Grafi tramite la Trasformata di Fourier Frazionaria su Grafi

Enunciato del Problema
L'elaborazione di segnali su grafi (Graph Signal Processing - GSP) ha stabilito principi di incertezza che caratterizzano il compromesso tra la localizzazione di un segnale nel dominio dei vertici e nel dominio spettrale standard del grafo (definito dalla Trasformata di Fourier su Grafo, GFT). Tuttavia, i principi esistenti sono ampiamente confinati al quadro convenzionale della GFT, che offre una rappresentazione spettrale fissa determinata unicamente dall'operatore di spostamento del grafo. Questa limitazione restringe la capacità di modellare segnali con caratteristiche simili a chirp o di controllare la transizione tra i domini dei vertici e spettrali. Sebbene la Trasformata di Fourier Frazionaria su Grafo (GFRFT) sia stata introdotta per fornire una rappresentazione spettrale frazionaria con ordine $\alpha$ variabile, le fondamenta teoriche per i principi di incertezza all'interno del dominio GFRFT rimangono sottoutilizzate. Nello specifico, manca una formulazione unificata per caratterizzare come l'ordine frazionario rimodelli le regioni di localizzazione ammissibili e se i classici quadri di concentrazione dell'energia e di range numerico possano essere estesi a questo setting generalizzato.

Metodologia
Gli autori propongono un framework basato su operatori per quantificare la localizzazione congiunta nel dominio dei vertici e nel dominio spettrale frazionario del grafo. La metodologia procede attraverso i seguenti passaggi:

1. Operatori di Localizzazione: Il documento introduce due operatori ermitiani semidefiniti positivi normalizzati:

   • $D_f$: Un operatore di localizzazione nel dominio dei vertici definito da un filtro $f$.
   • $B^\alpha_g$: Un operatore di localizzazione spettrale frazionaria su grafo definito da un filtro $g$ e dall'ordine della GFRFT $\alpha$. Questo operatore è costruito tramite la base GFRFT $F_\alpha$ come $B^\alpha_g = F^{-\alpha} D_{\hat{g}} F_\alpha$.
     La localizzazione congiunta di un segnale $x$ è misurata dalle forme quadratiche $\zeta_f(x) = \langle D_f x, x \rangle$ e $\eta^\alpha_g(x) = \langle B^\alpha_g x, x \rangle$.

2. Operatore Congiunto "Sandwiched": Per caratterizzare il limite fondamentale della concentrazione simultanea, gli autori costruiscono un operatore congiunto "sandwiched" (a sandwich):
   $$S^\alpha_{f,g} = (B^\alpha_g)^{1/2} D_f (B^\alpha_g)^{1/2}$$
   Il più grande autovalore $\sigma_1$ di questo operatore quantifica la massima concentrazione congiunta ottenibile. Ciò porta a una relazione di incertezza in cui il prodotto delle misure di localizzazione è limitato, e le coppie ammissibili $(\zeta_f, \eta^\alpha_g)$ sono vincolate da una curva derivata da $\sigma_1$.

3. Operatori Ruotati e Range Numerico: Per fornire una descrizione geometrica della regione di incertezza ammissibile $\Gamma(D_f, B^\alpha_g)$, gli autori definiscono una famiglia di operatori congiunti ruotati:
   $$R^\alpha_{f,g}(\beta) = \cos \beta D_f + \sin \beta B^\alpha_g$$
   Analizzando il range numerico del complesso operatore $A^\alpha_{f,g} = D_f + i B^\alpha_g$, il documento stabilisce che la regione ammissibile è un sottoinsieme convesso e compatto di $[0, 1]^2$. Il confine di questa regione è sostenuto da rette determinate dai più grandi autovalori $\rho_1(\beta)$ degli operatori ruotati $R^\alpha_{f,g}(\beta)$.

4. Approssimazione Numerica: Viene sviluppato un metodo di approssimazione poligonale per calcolare la regione ammissibile. Campionando un insieme finito di angoli $\beta$, gli autori costruiscono approssimazioni interne (inviluppi convessi di punti di confine ottenuti tramite autovettori) e approssimazioni esterne (intersezioni di semispazi di supporto).

Contributi Chiave

• Framework Unificato: Il documento costruisce operatori di localizzazione nei vertici e nello spettro frazionario associati alla GFRFT, fornendo un framework unificato per misurare la localizzazione dei segnali su grafi che si applica sia a filtri "soft" che a operatori di concentrazione di energia.
• Principio di Incertezza basato sulla GFRFT: Viene stabilito un nuovo principio di incertezza utilizzando l'operatore congiunto "sandwiched". Questo risultato generalizza i classici principi di incertezza su grafi, caratterizzando il limite della localizzazione simultanea nei vertici e nello spettro frazionario basandosi sul più grande autovalore dell'operatore congiunto.
• Caratterizzazione Geometrica: Gli autori forniscono una descrizione geometrica della regione di incertezza utilizzando operatori ruotati e il range numerico. Questo approccio connette il confine della regione ammissibile agli autovettori di una famiglia di operatori ermitiani e supporta un'approssimazione poligonale numerica.
• Analisi dell'Ordine Frazionario: Il framework dimostra come l'ordine frazionario $\alpha$ agisca come un parametro continuo che rimodella la geometria della regione di incertezza, offrendo un meccanismo per controllare il trade-off tra vertici e spettro oltre il caso fisso della GFT.

Risultati
Esperimenti numerici sono stati condotti su grafi Erdős–Rényi e guppy utilizzando vari filtri di localizzazione (basati sulla distanza, parametrizzati, basati sulla diffusione e basati sulla concentrazione di energia).

• Effetto dell'Ordine Frazionario: I risultati mostrano che variare $\alpha$ altera significativamente la forma e la dimensione della regione di incertezza. Per il grafo Erdős–Rényi, determinati ordini frazionari hanno ridotto la regione ammissibile rispetto al caso GFT ($\alpha=1$), mentre per il grafo guppy, la regione è stata ampliata. Ciò indica che l'ordine frazionario può restringere o rilassare il trade-off di incertezza a seconda della topologia del grafo.
• Influenza del Filtro: Diverse scelte di filtri di localizzazione $f$ e $g$ hanno prodotto geometrie di incertezza distinte, confermando la flessibilità del framework basato su operatori.
• Analisi Spettrale: L'analisi del decadimento degli autovalori dei generatori congiunti ha rivelato che l'ordine frazionario e l'angolo di rotazione $\beta$ influenzano la concentrazione dei modi congiuntamente localizzati e i limiti dell'errore di approssimazione. I più grandi autovalori $\sigma_1$ e $\rho_1(\beta)$ sono variati con $\alpha$, riflettendo cambiamenti nella localizzazione congiunta ottenibile.

Significatività
Il documento afferma che questi risultati generalizzano i classici principi di incertezza su grafi al dominio della GFRFT, fornendo uno strumento flessibile per l'analisi di segnali frazionari su grafi. Introducendo l'ordine frazionario come parametro regolabile, il framework permette la progettazione di rappresentazioni localizzate adattate al grafo con specifiche caratteristiche spettrali. Il lavoro colma il divario tra i concetti classici di incertezza tempo-frequenza e l'elaborazione di segnali su grafi, consentendo una comprensione più sfumata della localizzazione dei segnali su domini irregolari. Il metodo di approssimazione numerica proposto facilita ulteriormente la visualizzazione pratica e l'analisi quantitativa di questi trade-off di incertezza.