Entropy and Distributed Source Coding of Connected Soft Random Geometric Graphs

Riassunto Tecnico: Entropia e Codifica di Sorgente Distribuita di Grafi Geometrici Casuali Morbidi Connessi

Formulazione del Problema
Questo articolo affronta i limiti teorico-informativi della compressione di Grafi Geometrici Casuali Morbidi (SRGG) in un contesto distribuito. Sebbene lavori precedenti abbiano esplorato la compressione di grafi casuali (ad esempio, Erdős-Rényi, modelli a blocchi stocastici) e l'entropia degli SRGG in contesti centralizzati, la compressione distribuita degli SRGG rimane inesplorata. Gli autori si concentrano su un regime specifico in cui il grafo è connesso con alta probabilità al tendere del numero di nodi $n \to \infty$, eppure il grafo è "sparso" nel senso che il grado atteso è sublineare.

Crucialmente, gli autori distinguono il loro lavoro dai regimi in cui la sparsità è ottenuta rimuovendo casualmente archi da un insieme denso. Invece, studiano il regime in cui la "distanza di connessione" di ciascun nodo diminuisce all'aumentare di $n$ (o equivalentemente, il dominio di embedding cresce). In questo contesto, l'SRGG è una "sorgente non standard" che non può essere modellata come una sequenza di simboli stazionari, ergodici o markoviani, rendendo necessaria l'uso della teoria dello spettro informativo.

Il problema è formulato come segue: un grafo $G_n$ è partizionato in $L$ blocchi, dove ciascun blocco è osservato da un codificatore distinto. Questi codificatori comprimono le loro sezioni locali indipendentemente senza comunicazione. Un decodificatore riceve i messaggi compressi e tenta di ricostruire l'intero grafo. L'obiettivo è caratterizzare la regione di velocità raggiungibile (la regione di Slepian-Wolf) per questo schema di compressione distribuita.

Metodologia
Gli autori impiegano tecniche dalla teoria dello spettro informativo per gestire la natura non standard della sorgente SRGG. Il loro approccio coinvolge tre pilastri metodologici principali:

1. Teoremi Limite per l'Entropia: Stabiliscono un teorema limite per il tasso di entropia dell'SRGG. Discretizzando il dominio spaziale e condizionando sulle posizioni dei nodi, relazionano l'entropia del grafo $H(G_n)$ all'entropia condizionata data dalle posizioni dei nodi $H(G_n|Z_n)$. Dimostrano che la differenza tra queste quantità, quando normalizzata per il numero effettivo di archi, si annulla asintoticamente.
2. Proprietà di Equipartizione Asintotica (AEP): Utilizzando la legge debole dei grandi numeri e l'analisi della varianza, gli autori dimostrano un'AEP per l'SRGG. Dimostrano che i tassi di entropia spettrale (sup-entropia spettrale e inf-entropia spettrale) convergono in probabilità a un valore costante, $h^*$. Ciò permette la definizione di "insiemi tipici" di grafi che dominano lo spazio delle probabilità.
3. Binning Casuale per la Compressione Distribuita: Per derivare la regione di Slepian-Wolf, gli autori applicano tecniche di binning casuale. Definiscano insiemi tipici per sottoinsiemi di blocchi e analizzano la probabilità di errori di decodifica. La dimostrazione si basa su un lemma chiave che mostra come l'entropia condizionata di un sottoinsieme di vicinanze dato il complemento sia equivalente all'entropia di un SRGG più piccolo formato da quel sottoinsieme di nodi.

Contributi e Risultati Chiave

1. Teorema Limite per il Tasso di Entropia: L'articolo stabilisce che il tasso di entropia dell'SRGG converge a una costante $h^*$, definita da un integrale che coinvolge la funzione di connessione $p(r)$ e la funzione di entropia binaria $h_2$. Nello specifico:
   $$\lim_{n \to \infty} \frac{H(G_n)}{\binom{n}{2}s(n)^d} = h^*$$
   dove $s(n)$ è il parametro di sparsità e $d$ è la dimensione dello spazio di embedding.

2. Proprietà di Equipartizione Asintotica (AEP): Gli autori dimostrano che l'SRGG è una sorgente informazionalmente stabile. L'autoinformazione di una realizzazione tipica del grafo converge in probabilità al tasso di entropia:
   $$p\text{-}\lim_{n \to \infty} \frac{1}{\binom{n}{2}s(n)^d} \log \frac{1}{P(G_n)} = h^*$$
   Questo risultato valida l'uso di argomenti basati sugli insiemi tipici per questa classe di grafi.

3. Regione di Velocità di Slepian-Wolf: L'articolo fornisce una caratterizzazione completa della regione di velocità raggiungibile per la compressione distribuita con $L$ codificatori. Una terna di velocità $(R_1, \dots, R_L)$ è raggiungibile se e solo se per ogni sottoinsieme di codificatori $\Lambda \subseteq \{1, \dots, L\}$:
   $$\sum_{l \in \Lambda} R_l \geq \frac{|\Lambda|}{L} \frac{h^*}{2} \lim_{n \to \infty} \frac{s(|\Lambda|n/L)^d}{s(n)^d}$$
   Il fattore $1/2$ deriva dal fatto che l'informazione sugli archi è memorizzata due volte (una volta nel vettore di vicinato di ciascun estremo).

Significato e Affermazioni
Gli autori affermano che questo lavoro rappresenta il primo studio sulla compressione distribuita per Grafi Geometrici Casuali Morbidi. Superando i modelli di compressione centralizzata, affrontano uno scenario più realistico per le reti su larga scala in cui i nodi o i cluster di nodi possiedono solo informazioni parziali.

Il significato del lavoro risiede in:

• Estensione Teorica: Estendere la teoria dello spettro informativo ai grafi casuali embedded spazialmente in un regime sparso e connesso, un contesto precedentemente inesplorato nella teoria dell'informazione.
• Nuovi Teoremi Limite: Dimostrare nuovi teoremi limite e AEP specificamente adattati alle probabilità di connessione dipendenti dalla geometria degli SRGG.
• Limiti Operativi: Fornire i primi limiti operativi (regione di Slepian-Wolf) per la compressione distribuita di questo specifico modello di grafo, stabilendo i limiti fondamentali dell'efficienza di compressione quando l'informazione globale del grafo non è disponibile ai singoli codificatori.

L'articolo conclude notando che, sebbene i limiti teorici siano stabiliti, lo sviluppo di algoritmi di compressione distribuita trattabili e l'estensione di questi risultati a regimi con un numero crescente di codificatori o scenari di compressione con perdita rimangono direzioni aperte per la ricerca futura.