Weighted Riemannian Optimization for Solving Quadratic Equations from Gaussian Magnitude Measurements

1. Il Problema: Recupero di Fase (Phase Retrieval)

Il lavoro affronta il problema classico del recupero di fase, ovvero la ricostruzione di un segnale complesso $x \in \mathbb{C}^n$ a partire da $m$ campioni privi di fase (magnitude-only). Le misurazioni sono date da:
$$y_k = |\langle a_k, x \rangle|^2, \quad k = 1, \dots, m$$
dove $a_k$ sono vettori di misurazione noti (assunti distribuiti secondo una Gaussiana complessa i.i.d.) e $y_k$ sono i valori osservati.

Il problema è intrinsecamente non convesso e non lineare. Una strategia comune per affrontarlo è la "lifting" (sollevamento), che trasforma il vettore incognito $x$ in una matrice $X = xx^*$ di rango 1 e semidefinita positiva. Il problema diventa quindi trovare una soluzione di rango 1 per un sistema di equazioni lineari:
$$y_k = \langle a_k a_k^*, X \rangle$$
o in forma compatta $\mathcal{A}(X) = y$, dove $\mathcal{A}$ è un operatore lineare.

2. Metodologia: Ottimizzazione Riemanniana Ponderata (WRGD)

Gli autori analizzano gli algoritmi esistenti, come il Wirtinger Flow (WF) e la Discesa del Gradiente Riemanniana Canonica (RGD), notando che entrambi possono essere visti come metodi di discesa del gradiente su una varietà Riemanniana di matrici Hermitiane di rango 1 ($\mathcal{M}_1$), ma utilizzano metriche diverse.

Il Limite degli Algoritmi Esistenti

La velocità di convergenza di questi algoritmi dipende dal numero di condizionamento dell'operatore di misurazione $\frac{1}{\sqrt{m}}\mathcal{A}$ ristretto allo spazio tangente della varietà.

• La metrica canonica porta a un numero di condizionamento che tende a 2.
• La metrica di WF porta a un numero di condizionamento che tende a 4.
  Poiché il numero di condizionamento è strettamente maggiore di 1, la convergenza è lineare ma lenta (fattore di contrazione non ottimale).

La Soluzione Proposta: WRGD

Per superare questo limite, gli autori propongono una nuova metrica Riemanniana, chiamata metrica ponderata, progettata per rendere l'operatore di misurazione quasi isometrico (il numero di condizionamento tende a 1).

1. Definizione della Metrica: La nuova metrica $\langle \cdot, \cdot \rangle_o$ è definita attraverso l'aspettativa del prodotto interno delle misurazioni:
   $$\langle W_1, W_2 \rangle_o = \mathbb{E}\left[ \frac{1}{m} \langle \mathcal{A}(W_1), \mathcal{A}(W_2) \rangle \right] = \langle W_1, W_2 \rangle + \text{tr}(W_1)\text{tr}(W_2)$$
   Questa scelta garantisce che, per grandi $m$, la norma indotta dalla metrica ponderata approssimi perfettamente la norma delle misurazioni, portando il numero di condizionamento $\kappa_o \approx 1$.

2. L'Algoritmo (TWRGD): Viene sviluppato un algoritmo di Discesa del Gradiente Riemanniana Ponderata Troncata (TWRGD).

   • Inizializzazione: Utilizza un metodo spettrale troncato per garantire che il punto di partenza sia sufficientemente vicino alla soluzione globale.
   • Aggiornamento: Calcola il gradiente Riemanniano rispetto alla nuova metrica e applica un operatore di retrazione (SVD troncata a rango 1) per mantenere la soluzione sulla varietà $\mathcal{M}_1$.
   • Troncamento: Incorpora regole di troncamento adattive per eliminare le misurazioni "fuori scala" che potrebbero destabilizzare la convergenza, garantendo robustezza.

3. Contributi Chiave

• Metrica Ottimale: Derivazione di una metrica Riemanniana semplice ed efficiente dal punto di vista computazionale che minimizza il numero di condizionamento dell'operatore di misurazione sulla varietà di rango 1.
• Garanzie Teoriche di Recupero Esatto: Dimostrazione che l'algoritmo TWRGD converge linearmente alla soluzione globale con un fattore di contrazione arbitrariamente vicino a zero (aumentando i parametri di troncamento), a condizione che il numero di misurazioni sia $m = O(n)$. Questo è un miglioramento teorico rispetto agli algoritmi esistenti, il cui fattore di contrazione ha un limite inferiore non nullo.
• Complessità dei Campioni Ottimale: L'algoritmo richiede un numero di campioni proporzionale alla dimensione del segnale ($O(n)$), che è ottimale per il problema del recupero di fase.
• Unificazione Teorica: Il lavoro fornisce un quadro unificato che collega gli algoritmi basati su fattorizzazione (come WF) e quelli basati su varietà (come RGD) come casi speciali di ottimizzazione Riemanniana con metriche diverse.

4. Risultati Sperimentali

Gli autori hanno condotto esperimenti numerici su segnali complessi di dimensione $n=1000$ con misurazioni Gaussiane.

• Confronto: TWRGD è stato confrontato con TRGD (Riemannian Gradient Descent canonico), TWF (Truncated Wirtinger Flow) e TAF (Truncated Amplitude Flow).
• Efficienza Computazionale: TWRGD ha mostrato una convergenza significativamente più rapida sia in termini di numero di iterazioni che di tempo CPU. In particolare, riduce drasticamente il numero di iterazioni necessarie rispetto a TRGD e TWF.
• Robustezza: Anche con un numero elevato di misurazioni ($m=30n$), TWRGD mantiene la velocità di convergenza più alta, confermando che il suo fattore di condizionamento vicino a 1 permette prestazioni superiori.
• Tasso di Successo: Tutti gli algoritmi basati su troncamento (incluso TWRGD) raggiungono un recupero esatto con probabilità vicina a 1 quando $m \ge 5n$, ma TWRGD lo fa con minori risorse computazionali.

5. Significato e Impatto

Questo lavoro rappresenta un avanzamento significativo nella teoria e nella pratica del recupero di fase:

1. Superamento dei Limiti Teorici: Dimostra che la lentezza di convergenza degli algoritmi precedenti non è una limitazione intrinseca del problema, ma una conseguenza della scelta subottimale della metrica Riemanniana.
2. Nuovo Standard: Introduce un nuovo paradigma per l'ottimizzazione su varietà a rango basso, suggerendo che la progettazione attenta della metrica può portare a convergenze quasi istantanee (fattore di contrazione $\to 0$).
3. Applicabilità: Poiché il costo computazionale per iterazione è simile a quello degli algoritmi vettoriali (WF), l'approccio proposto offre prestazioni superiori senza penalità computazionali significative, rendendolo ideale per applicazioni reali come la cristallografia a raggi X, l'imaging a diffrazione e la microscopia.

In sintesi, il paper propone WRGD come un algoritmo superiore per il recupero di fase, combinando garanzie teoriche ottimali (complessità dei campioni e tasso di convergenza) con un'efficienza pratica dimostrata sperimentalmente.