Computing adjoint mismatch of linear maps

Dit artikel presenteert een stochastisch algoritme dat bijna zeker convergeert naar de operatornorm van het verschil tussen twee lineaire afbeeldingen, waarbij voor de ene afbeelding alleen een black-box voor de evaluatie en voor de andere alleen een black-box voor de geadjungeerde evaluatie beschikbaar is.

De kern

Titel: De "Geheime Tweeling" van Wiskundige Machines: Hoe we hun onvolmaaktheid opsporen

Stel je voor dat je twee zeer slimme, maar mysterieuze machines hebt. Laten we ze Machine A en Machine V noemen.

• Machine A is een zwarte doos. Je kunt er een bal in gooien (een getal of een plaatje), en hij gooit er een andere bal uit. Je ziet wat eruit komt, maar je weet niet precies hoe hij binnenin werkt.
• Machine V is ook een zwarte doos, maar hij is een beetje anders. Hij heeft een "tweelingbroer" die we V-ster noemen. Jij kunt alleen maar naar V-ster kijken. Als je een bal naar V-ster gooit, gooit hij er een andere uit. Je ziet nooit wat Machine V zelf doet, alleen wat zijn tweelingbroer doet.

Het Probleem: De Gebroken Spiegel
In de echte wereld, bijvoorbeeld bij medische scanners (zoals CT-scanners), moeten deze machines perfect op elkaar afgestemd zijn. Ze moeten elkaars spiegelbeeld zijn. Als Machine A iets doet, zou Machine V precies het tegenovergestelde moeten doen om het beeld scherp te krijgen.

Maar vaak is dat niet zo. Door kleine foutjes in de software of de manier waarop de computer de wereld in stukjes verdeelt, zijn ze niet perfect elkaars spiegelbeeld. Ze zijn "mismatched" (niet op elkaar afgestemd).

De vraag is: Hoe groot is die onvolmaaktheid? Hoe ver zijn ze van elkaar verwijderd? Wiskundig gezien willen we de "afstand" tussen deze twee machines meten.

Het Dilemma: Te groot om te tellen
Normaal gesproken zou je alle mogelijke ballen die je kunt gooien uitproberen om de afstand te meten. Maar bij medische scanners zijn er zoveel mogelijke ballen (miljarden!), dat je ze niet allemaal kunt opslaan in je geheugen. Het is alsof je probeert elke zandkorrel op het strand te tellen, maar je hebt maar één emmertje om ze in te doen.

Daarom hebben de auteurs van dit papier een slimme truc bedacht.

De Oplossing: De "Gokker" met een Geluksdop
In plaats van alles te meten, hebben ze een stochastisch algoritme (een slimme gokker) bedacht.

1. Het Willekeurige Begin: De gokker begint met een willekeurige bal (een willekeurig getal) en gooit die naar Machine A en Machine V-ster.
2. De Zwaai: Hij kijkt naar het resultaat. Is het resultaat goed? Nee? Dan draait hij de bal een beetje, alsof hij een kompas in de wind draait. Hij zoekt een nieuwe richting die beter werkt.
3. De Slimme Stap: In plaats van willekeurig te draaien, gebruikt hij een wiskundige formule om de perfecte stapgrootte te berekenen. Het is alsof hij niet zomaar een stap zet, maar precies de juiste hoeveelheid kracht gebruikt om het hoogste punt van een heuvel te bereiken.
4. Herhaling: Hij doet dit keer op keer. Elke keer wordt zijn schatting van de "afstand" tussen de machines nauwkeuriger.

De Magie van de "Bijna Zekerheid"
Het mooiste aan dit algoritme is dat het bijna zeker (met een kans van 99,9999%) het juiste antwoord vindt. Het is alsof je een schat zoekt op een eiland. Je loopt niet elke hoek van het eiland af (dat duurt te lang), maar je loopt slim en willekeurig rond. Na een tijdje weet je met bijna 100% zekerheid waar de schat ligt, zonder dat je de hele eiland hebt afgezocht.

Waarom is dit belangrijk?

• Medische Beeldvorming: Het helpt artsen om te weten of hun CT-scanners goed werken. Als de "mismatch" te groot is, kan de reconstructie van het lichaam onscherp zijn. Met dit algoritme kunnen ze de fouten meten en de software corrigeren.
• Geheugenbesparing: Omdat het algoritme niet alles hoeft op te slaan, kan het werken op computers die niet heel krachtig zijn. Het is alsof je een hele bibliotheek in je hoofd kunt houden zonder de boeken fysiek te dragen.
• Snelheid: Het algoritme wordt steeds beter naarmate je het langer laat draaien. Als je na 1000 pogingen nog niet tevreden bent, kun je gewoon doorgaan tot je precies genoeg hebt.

Samenvattend:
De auteurs hebben een slimme, willekeurige "speurhond" bedacht die, zonder de volledige blauwdrukken van de machines te kennen, toch precies kan meten hoe ver twee complexe wiskundige processen van elkaar verwijderd zijn. Het is een manier om de onvolmaaktheid van onze digitale wereld te meten, zelfs als die wereld te groot is om te bevatten.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "Computing adjoint mismatch of linear maps" in het Nederlands.

Titel: Berekening van Adjoint Mismatch van Lineaire Afbeeldingen

Auteurs: Jonas Bresch, Dirk A. Lorenz, Felix Schneppe, Maximilian Winkler
Datum: 10 maart 2026

---

1. Probleemstelling

Het paper adresseert het fundamentele probleem van het berekenen van de operatornorm van het verschil tussen twee lineaire afbeeldingen, $A$ en $V$, tussen eindig-dimensionale reële Hilbertruimten ($\mathbb{R}^d \to \mathbb{R}^m$). De specifieke uitdaging ligt in de volgende restrictieve voorwaarden:

• Black-box toegang: Voor de afbeelding $A$ is alleen een black-box beschikbaar die $Av$ berekent voor een gegeven input $v$. Voor de afbeelding $V$ is alleen een black-box beschikbaar die de geadjungeerde $V^*u$ berekent voor een gegeven input $u$. De expliciete matrices van $A$ en $V$ zijn niet beschikbaar.
• Beperkt geheugen: Het is niet mogelijk om een groot aantal vectoren op te slaan. De methode moet een opslagvereiste hebben van $O(\max\{m, d\})$, wat betekent dat er slechts een constant aantal vectoren (ongeveer twee per dimensie) tijdens de iteratie bewaard moeten worden.
• Toepassing: Dit probleem is cruciaal in de computerized tomography (CT), waar de projectie (voorwaartse projectie) en de backprojectie (geadjungeerde) vaak onafhankelijk worden gediskretiseerd. Hierdoor zijn ze vaak niet exact elkaars geadjungeerde, wat leidt tot een "adjoint mismatch". Het kwantificeren van deze mismatch ($\|A - V\|$) is essentieel voor de convergentieanalyse van reconstructie-algoritmen (zoals de Chambolle-Pock methode).

Het doel is om een methode te ontwikkelen die $\|A - V\|$ met willekeurige nauwkeurigheid kan benaderen en die verder kan verbeteren als de huidige output onvoldoende is.

2. Methodologie

De auteurs stellen een stochastisch algoritme voor dat gebaseerd is op een generalisatie van de Rayleigh-kwotiënt en een random search-methode met optimale stapgroottes.

Kernconcepten:

• Doelfunctie: Het probleem wordt geformuleerd als het maximaliseren van de kwotiënt:
  $$\|A - V\| = \max_{u \neq 0, v \neq 0} \frac{\langle u, (A - V)v \rangle}{\|u\| \cdot \|v\|}$$
  De iteraties proberen de vectoren $u_k$ en $v_k$ zo aan te passen dat deze kwotiënt convergeert naar de operatornorm.
• Iteratief Proces:
  1. Initialisatie: Start met willekeurige eenheidsvectoren $u_0$ en $v_0$.
  2. Zoekrichtingen: Genereer willekeurige zoekrichtingen $x_k$ (in de raakruimte van $v_k$) en $w_k$ (in de raakruimte van $u_k$) door projectie van Gaussische vectoren.
  3. Optimale Stapgroottes: Bereken de optimale stapgroottes $\tau_k$ en $\xi_k$ die de doelwaarde maximaliseren in de richting van de zoekvectoren. Dit wordt gedaan door een analytische oplossing te vinden voor het maximaliseren van een functie $q_k(\tau, \xi)$, wat leidt tot een gesloten vorm voor de stapgroottes zonder lineair zoeken.
  4. Update: Werk $u_k$ en $v_k$ bij met de berekende stapgroottes en normaliseer ze.
• Geheugenefficiëntie: Het algoritme vereist alleen het opslaan van de huidige iteraties $u_k, v_k$ en de zoekvectoren, wat voldoet aan de $O(\max\{m, d\})$ eis.

3. Belangrijkste Bijdragen

• Nieuw Stochastisch Algoritme: Het paper introduceert een algoritme dat convergeert naar de operatornorm $\|A - V\|$ met bijna zekerheid (almost surely), uitsluitend gebruikmakend van evaluaties van $A$ en $V^*$.
• Geen Matrix Opslag: In tegenstelling tot traditionele methoden (zoals de macht-methode op $L^*L$ of Lanczos-methoden) die de geadjungeerde $L^*$ vereisen en vaak grote matrices opslaan, werkt deze methode volledig matrixvrij.
• Analyse van Convergentie:
  • Bewijs van bijna zeker convergentie van de sequentie van doelwaarden naar de grootste singuliere waarde ($\sigma_1 = \|A - V\|$).
  • Bewijs dat de vectoren $(u_k, v_k)$ convergeren naar de bijbehorende singuliere vectoren (als de multipliciteit 1 is) of naar de ruimte van de leidende singuliere vectoren.
  • Analyse van de convergentiesnelheid, waarbij wordt aangetoond dat de fout in de eigenvectorequatie convergeert met een snelheid van $O(1/n)$ (in probabilistische zin).
• Robuustheid: De methode werkt voor willekeurige lineaire afbeeldingen zonder specifieke aannames over de dimensies of de structuur van de matrices, zolang de multipliciteit van de singuliere waarden niet te hoog is (een technisch detail dat in de praktijk zelden een probleem vormt).

4. Resultaten en Numerieke Experimenten

De auteurs hebben het algoritme getest in verschillende scenario's:

• Gaussische Matrices: Toepassing op willekeurig gegenereerde matrices van verschillende maten ($m \times d$). De resultaten tonen aan dat het algoritme stabiel convergeert. De convergentiesnelheid wordt beïnvloed door de dimensie van de outputruimte.
• Vergelijking met Bestaande Methodes: Bij de speciale geval $V=0$ (berekening van $\|A\|$ zonder $A^*$) wordt het algoritme vergeleken met de methode uit [4]. Hoewel de methode uit [4] iets sneller convergeert in sommige gevallen, biedt het nieuwe algoritme de unieke mogelijkheid om het verschil tussen twee verschillende operatoren te meten.
• Radon Transformatie (Astra Toolbox): Een cruciaal experiment waarbij de forward en backprojectie-implementaties in de Astra toolbox voor CT werden getest.
  • De auteurs berekenden $\|R_i - B_i^*\|$ voor drie verschillende modellen (lijn, straal, Joseph-methode).
  • De resultaten waren zeer klein ($\approx 10^{-9}$), wat bevestigt dat deze implementaties inderdaad elkaars geadjungeerde zijn (binnen numerieke precisie).
  • In tegenstelling hiermee toonde een vergelijking met de MATLAB-implementatie (radon vs iradon) een significante mismatch (relatieve normverschil > 0.1), wat aantoont dat deze standaard implementaties niet perfect geadjungeerd zijn.

5. Betekenis en Toekomstperspectief

• Praktische Toepasbaarheid: De methode maakt het mogelijk om de kwaliteit van discretisaties in grote schaal toepassingen (zoals medische beeldvorming) te valideren zonder de volledige matrix te hoeven construeren, wat vaak onmogelijk is vanwege geheugenbeperkingen.
• Iteratieve Reconstructie: Het kwantificeren van de adjoint mismatch is direct relevant voor het verbeteren van iteratieve reconstructie-algoritmen. Een bekende mismatch kan leiden tot suboptimale oplossingen of langzamere convergentie; het weten van de grootte van de mismatch ($\|A-V\|$) helpt bij het instellen van correctieparameters.
• Generalisatie: Het algoritme kan worden uitgebreid om meer singuliere vectoren te vinden of zelfs de kleinste singuliere waarde te berekenen door het maximalisatie-probleem om te draaien naar een minimalisatie-probleem.

Kortom, dit paper biedt een wiskundig onderbouwde, geheugenefficiënte en stochastische oplossing voor een lang bestaand probleem in numerieke lineaire algebra en computationele beeldvorming: het meten van de "mismatch" tussen een operator en zijn geadjungeerde wanneer alleen black-box toegang mogelijk is.