Weighted Riemannian Optimization for Solving Quadratic Equations from Gaussian Magnitude Measurements

Probleemstelling: Faseherstel (Phase Retrieval)

Het artikel richt zich op het faseherstelprobleem, een fundamenteel inverse probleem waarbij een complex signaal $x \in \mathbb{C}^n$ moet worden gereconstrueerd uit een reeks fase-loze metingen. De metingen worden gegeven door:
$$y_k = |\langle a_k, x \rangle|^2, \quad k = 1, \dots, m$$
waarbij $a_k$ bekende meetvectoren zijn en $y_k$ de gemeten intensiteiten (amplitudes) vertegenwoordigen. De fase-informatie gaat verloren door fysieke beperkingen van optische sensoren.

Het probleem kan worden herschreven als het vinden van een positief semi-definiete rang-1 matrix $X = xx^*$ die voldoet aan een stelsel lineaire vergelijkingen:
$$y_k = \langle a_k a_k^*, X \rangle$$
Dit transformeert het niet-convexe probleem in een lineair probleem op de variëteit van rang-1 matrices, maar het vinden van een rang-1 oplossing blijft uitdagend.

Methodologie en Analyse van Bestaande Methoden

De auteurs analyseren bestaande algoritmen, zoals Wirtinger Flow (WF) en Canonische Riemanniaanse Gradient Descent (RGD), binnen een gemeenschappelijk raamwerk van Riemanniaanse optimalisatie. Ze tonen aan dat deze methoden in wezen gradient-descent algoritmen zijn op de gladde Riemanniaanse variëteit $\mathcal{M}_1$ (de verzameling van alle Hermitische rang-1 matrices), maar dat ze gebruikmaken van verschillende metrieken.

Het kernprobleem met bestaande methoden:
De convergentiesnelheid van Riemanniaanse gradient-descent wordt bepaald door de conditienummer ($\kappa$) van de sensingsoperator $A$ beperkt tot de raakruimte van de variëteit.

• Voor Canonische RGD (gebaseerd op de Frobenius-norm) is het conditienummer $\kappa \approx 2$.
• Voor Wirtinger Flow (gebaseerd op een pseudo-inproduct) is het conditienummer $\kappa \approx 4$.

Omdat deze conditienummers strikt groter zijn dan 1, zelfs bij een oneindig aantal metingen, blijft de convergentiefactor (de snelheid waarmee de fout afneemt) beperkt. Dit leidt tot een lineaire convergentie met een aanzienlijke vertraging.

De voorgestelde oplossing: Weighted Riemannian Gradient Descent (WRGD)
Om dit te overwinnen, stellen de auteurs een nieuwe Riemanniaanse metriek voor, genaamd de "gewogen metriek" ($\langle \cdot, \cdot \rangle_o$). Deze metriek wordt afgeleid uit de verwachting van het inproduct van de gemeten data:
$$\langle W_1, W_2 \rangle_o := \mathbb{E}\left[ \frac{1}{m} \langle A(W_1), A(W_2) \rangle \right] = \langle W_1, W_2 \rangle + \text{tr}(W_1)\text{tr}(W_2)$$
Deze keuze is cruciaal omdat deze metriek zorgt voor een bijna-isometrische inbedding van de rang-1 matrices in $\mathbb{R}^m$. Hierdoor nadert het conditienummer $\kappa_o$ de waarde 1 (in plaats van 2 of 4). Een conditienummer van 1 impliceert dat de convergentiefactor willekeurig dicht bij 0 kan komen, wat leidt tot een veel snellere convergentie.

Het algoritme WRGD (en zijn getruncereerde variant TWRGD) voert updates uit op basis van deze nieuwe metriek, gecombineerd met een getruncereerde spectrale initialisatie om de iteraties te starten in de buurt van de ware oplossing.

Kernbijdragen

1. Optimale Metriek: De afleiding van een eenvoudige, computationeel efficiënte Riemanniaanse metriek die direct voortkomt uit de statistische eigenschappen van de meetoperator (voor complexe Gaussische metingen). Deze metriek minimaliseert het conditienummer.
2. Theoretische Garantie: Het bewijs dat het TWRGD-algoritme lineair convergeert naar de globale minimum (de ware rang-1 matrix $X$) met een convergentiefactor die willekeurig dicht bij 0 ligt, mits het aantal metingen $m = O(n)$ is (optimaal voor dit probleem).
3. Verbeterde Convergentie: In tegenstelling tot bestaande methoden waarbij de convergentiesnelheid een ondergrens heeft, toont het artikel aan dat door de nieuwe metriek de samentrekkingsfactor (contraction factor) kan worden verlaagd tot bijna nul door de truncatieparameters te verhogen.
4. Efficiëntie: Het algoritme behoudt dezelfde computationele complexiteit per iteratie als vector-gebaseerde methoden (zoals WF), omdat de matrix-updates kunnen worden gereduceerd tot updates van twee vectoren.

Resultaten

De auteurs hebben uitgebreide numerieke experimenten uitgevoerd om WRGD/TWRGD te vergelijken met TRGD (Canonische RGD), TWF (Truncated Wirtinger Flow) en TAF.

• Convergentiesnelheid: TWRGD vereist aanzienlijk minder iteraties en minder rekentijd om dezelfde foutmarge (MSE) te bereiken dan de concurrenten.
• Invloed van $m$: Zelfs bij een groot aantal metingen ($m = 30n$) blijft TWRGD de snelste methode. De andere methoden vertonen een "plateau" in hun convergentiesnelheid door hun hogere conditienummers.
• Succesratio: TWRGD bereikt een hoge waarschijnlijkheid van exact herstel zodra $m \approx 5n$, wat vergelijkbaar is met de beste bestaande methoden, maar met een veel snellere convergentie.
• Robuustheid: De algoritmen presteren goed in ruisvrije scenario's met complexe Gaussische metingen.

Betekenis en Conclusie

Dit artikel biedt een theoretisch onderbouwd en praktisch superieur alternatief voor bestaande faseherstel-algoritmen. De belangrijkste inzichten zijn:

• De keuze van de Riemanniaanse metriek is niet triviaal; een verkeerde keuze (zoals de canonieke metriek) leidt tot suboptimale convergentie.
• Door de metriek af te stemmen op de statistiek van de meetoperator, kan men de geometrie van het optimalisatieprobleem zodanig veranderen dat het probleem "makkelijker" wordt voor gradient-descent methoden (dicht bij een kwadratische functie met een perfecte Hessian).
• De methode bereikt de theoretische limiet van convergentiesnelheid voor dit type niet-convexe optimalisatieproblemen.

De auteurs suggereren dat deze aanpak van "gewogen metrieken" ook toepasbaar is op andere problemen zoals matrixcompletie en blinde deconvolutie, wat een nieuwe richting voor toekomstig onderzoek opent.