An Improved Lower Bound on Cardinality of Support of the Amplitude-Constrained AWGN Channel

1. Problema e Contesto

Il lavoro si concentra sul canale a rumore bianco additivo gaussiano (AWGN) soggetto a un vincolo di potenza di picco (ampiezza). Il modello di canale è definito come:
$$Y = X + Z$$
dove $X$ è la variabile casuale di ingresso soggetta al vincolo $|X| \le A$ quasi certamente, e $Z$ è una variabile casuale normale standard indipendente da $X$.

L'obiettivo è determinare la capacità del canale $C(A)$ e, in particolare, la struttura della distribuzione di ingresso ottimale $P_{X^*}$ che massimizza l'informazione mutua $I(X; Y)$.
È noto da lavori seminali (Smith, 1971) che:

1. La distribuzione di ingresso ottimale è discreta e supportata su un numero finito di punti.
2. La distribuzione è unica e simmetrica rispetto all'origine.

Tuttavia, la dimensione esatta del supporto (il numero di punti di massa, indicato come $K$) in funzione del vincolo di ampiezza $A$ rimane un problema aperto.

• Stato dell'arte: Le migliori stime precedenti (Dytso et al., 2020) fornivano un limite inferiore di ordine $O(A)$ e un limite superiore di ordine $O(A^2)$.
• Congettura: Sulla base di questi risultati e di evidenze numeriche, era stata congetturata una scalatura lineare del supporto ($K \propto A$).
• Contesto numerico: Studi numerici successivi hanno suggerito comportamenti diversi (es. $A^{4/3}$ o $A\sqrt{\log A}$), ma le simulazioni sono estremamente sensibili agli errori di arrotondamento e ai bias algoritmici, specialmente per $A$ grandi, rendendo difficile distinguere tra le diverse ipotesi.

2. Metodologia

Gli autori sviluppano un approccio analitico rigoroso per superare le limitazioni dei metodi numerici e migliorare il limite inferiore noto. La metodologia si articola in tre fasi principali:

A. Operazione di "Wrapping" (Avvolgimento)

Per gestire il dominio non limitato della variabile casuale, gli autori introducono un operatore di "wrapping" che mappa le variabili reali su un dominio compatto (un cerchio).
Definito un parametro $B > 0$, l'operatore è:
$$\langle W \rangle_B = \frac{\pi}{B} (W \mod 2B) \in [-\pi, \pi)$$
Questa trasformazione permette di studiare l'approssimazione della distribuzione uniforme sul cerchio mediante miscele gaussiane finite, un problema più trattabile analiticamente.

B. Teoria di Migliore Approssimazione con Miscele Gaussiane

Il cuore della dimostrazione risiede nella quantificazione di quanto bene una distribuzione uniforme (ottenuta da un ingresso uniforme su $[-A, A]$) possa essere approssimata da una distribuzione di uscita generata da un ingresso discreto con $K$ punti.

• Viene utilizzato il metodo dei momenti trigonometrici.
• Si dimostra che la divergenza $\chi^2$ tra la distribuzione di uscita "avvolta" dell'ingresso ottimo e quella dell'ingresso uniforme è limitata inferiormente da una funzione esponenziale decrescente rispetto a $K^2/A^2$.
• Specificamente, si mostra che se l'ingresso ha $K$ punti di massa, l'errore di approssimazione non può essere arbitrariamente piccolo, ma è vincolato da termini del tipo $\exp(-c K^2/A^2)$.

C. Stabilità della Distribuzione Ottimale

Gli autori sfruttano le proprietà di stabilità della capacità. Dimostrano che la distribuzione di uscita indotta dall'ingresso ottimale $X^*$ è molto vicina alla distribuzione uniforme in termini di entropia relativa (divergenza di Kullback-Leibler), con un errore dell'ordine di $O(1/A)$.
Combinando questo fatto con il limite inferiore sull'approssimazione delle miscele gaussiane, si ottiene un vincolo su $K$.

3. Risultati Principali

Il risultato centrale è il Teorema 1, che stabilisce un nuovo limite inferiore per la cardinalità del supporto $|supp(P_{X^*})|$:

$$|supp(P_{X^*})| \ge \max \left\{ \frac{A \sqrt{\log^+(c A)}}{2\pi}, \sqrt{1 + \frac{2}{\pi e}A^2}, 2 \right\}$$

dove $c > 0$ è una costante esplicita ($c \approx 0.0337$) e $\log^+(x) = \max\{\log(x), 0\}$.

Implicazioni chiave del risultato:

1. Miglioramento del limite inferiore: Il nuovo limite è di ordine $O(A \sqrt{\log A})$, che rappresenta un miglioramento asintotico rispetto al precedente limite lineare $O(A)$.
2. Smentita della congettura lineare: Il risultato dimostra rigorosamente che la scalatura lineare ($K \propto A$) è impossibile. La dimensione del supporto deve crescere in modo superlineare.
3. Validità non asintotica: A differenza di alcune euristiche precedenti (come quelle di Zhang basate su spaziatura asintotica), questo limite è valido per valori finiti di $A$ (non asintotici), fornendo garanzie matematiche precise.

4. Contributi Chiave

• Rottura della scalatura lineare: È il primo lavoro che fornisce una prova analitica rigorosa che la dimensione del supporto non può essere lineare rispetto al vincolo di ampiezza, invalidando la congettura precedente basata su dati numerici.
• Nuova tecnica di dimostrazione: L'uso combinato dell'operatore di wrapping, della teoria di approssimazione delle miscele gaussiane su domini compatti e delle proprietà di stabilità dell'entropia relativa rappresenta un contributo metodologico significativo.
• Quantificazione della vicinanza all'uniformità: Viene stabilito un limite superiore rigoroso sulla divergenza relativa tra la distribuzione di uscita ottima e quella uniforme, quantificando quanto "piatta" sia la distribuzione ottima nel bulk del dominio.

5. Significato e Prospettive Future

Questo lavoro risolve un problema fondamentale nella teoria dell'informazione riguardante la struttura delle distribuzioni ottimali nei canali con vincoli di ampiezza.

• Impatto teorico: Chiarisce la natura della complessità delle distribuzioni ottimali, indicando che la struttura diventa più complessa (più punti di massa) di quanto previsto in passato man mano che aumenta il vincolo di potenza.
• Domande aperte: Sebbene sia stata esclusa la scalatura lineare, la scalatura esatta rimane incerta. Potrebbe essere $A\sqrt{\log A}$, $A \log A$, $A^{4/3}$ o $A^2$. Il lavoro suggerisce che la scalatura corretta potrebbe essere intermedia tra i limiti noti.
• Estensibilità: La metodologia sviluppata (wrapping + approssimazione su dominio compatto) è promettente per lo studio di altri canali, inclusi canali vettoriali gaussiani, canali con fading e problemi di stima di medie normali vincolate.

In sintesi, il paper fornisce un avanzamento teorico sostanziale, spostando il confine della conoscenza sulla cardinalità del supporto da una crescita lineare a una crescita superlineare, offrendo al contempo strumenti analitici robusti per future indagini in questo campo.