Computing adjoint mismatch of linear maps

Dieses Papier stellt einen stochastischen Algorithmus vor, der fast sicher gegen die Operatornorm der Differenz zweier linearer Abbildungen konvergiert, wobei für eine Abbildung nur eine Black-Box-Bewertung und für die andere nur eine Black-Box für die adjungierte Abbildung verfügbar ist.

Das Wesentliche

Die Detektive für unsichtbare Fehler: Wie man den "Adjoint-Mismatch" findet

Stellen Sie sich vor, Sie haben zwei riesige, geheime Maschinen.

1. Maschine A nimmt einen Ball (einen Vektor) und wirft ihn durch einen Tunnel. Sie können den Ball hineinwerfen und sehen, wo er herauskommt. Aber Sie dürfen die Maschine nicht öffnen.
2. Maschine V ist das genaue Gegenteil. Sie nimmt einen Ball, der aus einem anderen Tunnel kommt, und wirft ihn zurück. Auch hier: Sie können nur hineingucken, aber nicht sehen, wie die Räder im Inneren drehen.

In der Welt der Mathematik (speziell bei Computertomografie, also CT-Scans) wollen diese beiden Maschinen perfekte Spiegelbilder voneinander sein. Wenn Maschine A etwas "vorwärts" macht, sollte Maschine V es exakt "rückwärts" undo können.

Das Problem: In der Praxis sind diese Maschinen oft nicht perfekt. Sie sind wie zwei Tanzpartner, die versuchen, einen Walzer zu tanzen, aber einer macht einen kleinen Schritt zu viel, während der andere zu wenig macht. Dieser kleine Fehler nennt sich "Adjoint Mismatch" (Rückwärts-Fehler).

Die Frage der Autoren dieses Papiers lautet: Wie groß ist dieser Fehler eigentlich? Und das Tückische daran: Wir dürfen die Maschinen nicht auseinanderbauen, um die Fehler zu messen. Wir haben nur einen "Blackbox"-Zugang.

Die Lösung: Der zufällige Sucher

Die Autoren (Jonas Bresch und Kollegen) haben einen cleveren Algorithmus entwickelt, der wie ein Blindes Huhn, das aber sehr klug ist, funktioniert.

1. Der Tanz auf dem Seil (Die Suche nach dem Maximum)
Stellen Sie sich vor, Sie wollen herausfinden, wie stark diese beiden Maschinen zusammenarbeiten. Sie nehmen einen zufälligen Ball, werfen ihn durch Maschine A, holen ihn mit Maschine V zurück und messen, wie gut das passt.

• Wenn es perfekt passt, ist der Fehler null.
• Wenn es nicht passt, gibt es eine "Spannung".

Der Algorithmus sucht nun nach dem schlimmsten Fall. Er fragt sich: "Welcher Ball führt zu dem größten Missverständnis zwischen den beiden Maschinen?" Dieser größte Missverständnis-Wert ist genau das, was wir messen wollen (die sogenannte Operator-Norm).

2. Der Zufalls-Compass (Stochastischer Algorithmus)
Da die Maschinen zu groß sind, um alle möglichen Bälle durchzuprobieren (das würde ewig dauern), wirft der Algorithmus zufällig Bälle in verschiedene Richtungen.

• Er wirft einen Ball.
• Er prüft, ob der Fehler größer wird.
• Wenn ja, macht er einen Schritt in diese Richtung.
• Er nutzt dabei eine Art "intuitiven Kompass", der ihm sagt: "Hey, wenn wir hier noch ein bisschen weitergehen, wird der Fehler noch größer!"

Das Besondere: Der Algorithmus berechnet nicht nur den Fehler, sondern findet auch heraus, welcher Ball diesen Fehler verursacht. Das ist wie wenn ein Detektiv nicht nur sagt: "Hier wurde gestohlen", sondern auch genau zeigt: "Der Dieb hat genau diesen Schrank geöffnet."

3. Warum ist das genial?
Frühere Methoden brauchten oft riesige Speicher, um die ganze Maschine abzubilden. Das ist wie wenn Sie versuchen, eine ganze Stadt auf einem einzelnen Blatt Papier zu zeichnen – unmöglich.
Dieser neue Algorithmus ist extrem sparsam. Er braucht nur Platz für zwei kleine Notizzettel (einen für den Input, einen für den Output). Er vergisst alles andere sofort. Das macht ihn perfekt für riesige Datenmengen, wie sie in der modernen Medizin oder KI vorkommen.

Die Metapher: Der Blindenführer im Labyrinth

Stellen Sie sich vor, Sie sind in einem riesigen, dunklen Labyrinth (die mathematische Welt der großen Matrizen). Sie wollen den höchsten Punkt finden (den größten Fehler).

• Alte Methoden: Sie versuchen, eine Karte des ganzen Labyrinths zu zeichnen. Das dauert ewig und Sie brauchen einen riesigen Rucksack für das Papier.
• Diese neue Methode: Sie haben einen Blindenführer (den Algorithmus). Er tastet sich vorwärts. Er sagt: "Hier ist es steiler!" und macht einen Schritt. Er weiß nicht, wie das ganze Labyrinth aussieht, aber er findet garantiert den höchsten Punkt, wenn er nur lange genug sucht. Und er braucht dafür nur seine Füße und ein kleines Seil.

Was bringt uns das?

1. Sicherheit in der Medizin: Bei CT-Scans müssen die Bilder rekonstruiert werden. Wenn die Maschinen (Vorwärts- und Rückwärtsprojektion) nicht perfekt zusammenarbeiten, entstehen unscharfe Bilder oder Fehler. Mit diesem Algorithmus können Ingenieure prüfen: "Ist unsere neue Software-Implementierung der CT-Maschine gut genug?"
2. Keine Geheimnisse nötig: Man muss nicht wissen, wie die Maschine im Inneren funktioniert. Man braucht nur den "Eingang" und den "Ausgang".
3. Zuverlässigkeit: Die Autoren beweisen mathematisch, dass dieser zufällige Sucher fast sicher (mit einer Wahrscheinlichkeit von 100 %) den exakten Fehlerwert findet, wenn man ihn lange genug laufen lässt.

Fazit

Dieses Papier ist wie ein neues Werkzeug im Werkzeugkasten der Ingenieure. Es erlaubt uns, die Qualität von riesigen, komplexen mathematischen Maschinen zu überprüfen, ohne sie auseinanderzubauen. Es ist effizient, spart Speicherplatz und findet die Fehler dort, wo sie am schlimmsten sind – ganz gleich, wie groß die Maschine ist.

Kurz gesagt: Es ist der perfekte "Fehler-Detektor" für die unsichtbare Welt der großen Daten.

Technische Zusammenfassung

Hier ist eine detaillierte technische Zusammenfassung des vorliegenden Papiers auf Deutsch:

Titel: Berechnung der Adjoint-Mismatch von linearen Abbildungen

Autoren: Jonas Bresch, Dirk A. Lorenz, Felix Schneppe, Maximilian Winkler
Datum: 10. März 2026

---

1. Problemstellung

Das Papier adressiert das Problem der Berechnung der Operatornorm $\|A - V\|$ für die Differenz zweier linearer Abbildungen $A$ und $V$ zwischen endlichdimensionalen reellen Hilbert-Räumen (Dimensionen $d$ und $m$).

Die Berechnung erfolgt unter extrem restriktiven Bedingungen, die typisch für Anwendungen in der computergestützten Tomographie (CT) sind:

• Black-Box-Zugriff: Für die Abbildung $A$ steht nur eine Black-Box-Implementierung zur Verfügung, die $Av$ für einen gegebenen Eingabevektor $v$ berechnet. Für die Abbildung $V$ steht nur eine Black-Box für die Berechnung des Adjungierten $V^*u$ für einen gegebenen Eingabevektor $u$ zur Verfügung.
• Kein Zugriff auf Matrizen: Die Matrizen $A$ und $V$ (bzw. $V^*$) sind nicht explizit verfügbar, da ihre Speicherung den verfügbaren Arbeitsspeicher in praktischen Anwendungen (z. B. bei großen Diskretisierungen der Radon-Transformation) sprengen würde.
• Speicherbeschränkung: Der Algorithmus darf nur einen Speicherbedarf von $O(\max\{m, d\})$ haben. Das bedeutet, es können nur eine konstante Anzahl von Vektoren (insbesondere zwei Eingabe- und zwei Ausgabevektoren) während der Iteration gespeichert werden.
• Ziel: Die Methode soll den Wert $\|A - V\|$ mit beliebiger Genauigkeit approximieren und inkrementelle Verbesserungen ermöglichen.

Dieses Szenario ist insbesondere relevant, da in der CT die Vorwärtsprojektion und ihre Adjungierte (Rückprojektion) oft unabhängig diskretisiert werden. Dadurch sind sie mathematisch nicht mehr exakt adjungiert zueinander. Die Größe des Fehlers $\|A - V\|$ beeinflusst die Konvergenz und die Lösungsqualität iterativer Rekonstruktionsverfahren (z. B. Chambolle-Pock).

---

2. Methodik und Algorithmus

Die Autoren schlagen einen stochastischen Algorithmus vor, der auf einer Verallgemeinerung des Rayleigh-Quotienten basiert und als randomisierte Suchmethode fungiert.

Grundidee:
Die Operatornorm lässt sich als Maximum des Rayleigh-Quotienten formulieren:
$$\|A - V\| = \max_{\substack{u \in \mathbb{R}^m, u \neq 0 \\ v \in \mathbb{R}^d, v \neq 0}} \frac{\langle u, (A - V)v \rangle}{\|u\| \cdot \|v\|}$$
Da $A$ und $V^*$ als Black-Boxen vorliegen, kann der klassische Potenz-Algorithmus (Power Method), der $L^*L$ benötigt, nicht direkt angewendet werden.

Der Algorithmus (Algorithm 1):

1. Initialisierung: Zufällige Startvektoren $u_0 \in S^{m-1}$ und $v_0 \in S^{d-1}$ werden gewählt. Das Vorzeichen von $u_0$ wird so gewählt, dass der Startwert $\langle u_0, (A-V)v_0 \rangle \geq 0$ ist.
2. Suchrichtungen: In jedem Schritt $k$ werden Suchrichtungen $x_k$ und $w_k$ unabhängig und uniform auf den Tangentialräumen der aktuellen Vektoren $v_k$ bzw. $u_k$ (d.h. orthogonal zu $v_k$ und $u_k$) gesampelt. Dies erfolgt durch Projektion von Gauß-verteilten Zufallsvektoren.
3. Optimale Schrittweiten: Anstatt einer festen Schrittweite werden optimale Schrittweiten $\tau_k$ und $\xi_k$ berechnet, die den Zielwert (den quadrierten Rayleigh-Quotienten) in den Richtungen $w_k$ und $x_k$ maximieren.
   • Dies führt auf eine analytische Lösung eines eindimensionalen Optimierungsproblems, das sich aus der Struktur des Quotienten ergibt.
   • Die Schrittweiten werden explizit durch Formeln berechnet, die von den Skalarprodukten $a_k, b_k, c_k, d_k$ abhängen (die nur $A$, $V^*$ und die aktuellen Vektoren benötigen).
4. Update: Die Vektoren werden aktualisiert und wieder normalisiert:
   $$u_{k+1} = \frac{u_k + \tau_k w_k}{\|u_k + \tau_k w_k\|}, \quad v_{k+1} = \frac{v_k + \xi_k x_k}{\|v_k + \xi_k x_k\|}$$
5. Schätzung: Der aktuelle Schätzwert für die Norm ist $\langle u_k, (A-V)v_k \rangle$.

Theoretische Analyse:

• Der Algorithmus wird als stochastisches Gradientenverfahren interpretiert, bei dem die Suchrichtung eine Projektion des Gradienten auf den orthogonalen Raum ist.
• Es wird bewiesen, dass die Folge der Zielwerte fast sicher (almost surely, a.s.) monoton steigt und gegen den größten Singulärwert $\sigma_1 = \|A-V\|$ konvergiert.
• Die Vektoren $(u_k, v_k)$ konvergieren fast sicher gegen ein Paar von links/rechts Singulärvektoren zum größten Singulärwert (sofern der zugehörige Eigenraum eindimensional ist).
• Die Konvergenzrate für die Eigenvektorgleichung wird als $O(1/n)$ (sublinear) nachgewiesen, wobei numerische Experimente eine schnellere, fast exponentielle Konvergenz andeuten.

---

3. Wichtige Beiträge

1. Neuer Algorithmus: Entwicklung eines stochastischen Algorithmus zur Berechnung von $\|A - V\|$ unter der Annahme, dass nur $A$ und $V^*$ als Black-Boxen verfügbar sind.
2. Speichereffizienz: Der Algorithmus benötigt nur $O(\max\{m, d\})$ Speicherplatz, was für hochdimensionale Probleme in der Bildrekonstruktion entscheidend ist.
3. Optimale Schrittweiten: Im Gegensatz zu einfachen Gradientenverfahren werden in jedem Schritt analytisch optimale Schrittweiten berechnet, was die Konvergenz beschleunigt.
4. Konvergenzbeweise: Strenge Beweise für die fast sichere Konvergenz der Zielwerte gegen die Operatornorm und der Vektoren gegen die Singulärvektoren.
5. Erweiterbarkeit: Die Methode kann nicht nur die Norm, sondern auch die zugehörigen Singulärvektoren liefern und prinzipiell auf weitere Singulärwerte erweitert werden.

---

4. Ergebnisse und Experimente

Die Autoren führten numerische Experimente durch, um die Leistung des Algorithmus zu validieren:

• Gauß-Matrizen: Bei zufällig generierten Gauß-Matrizen unterschiedlicher Größen ($m \times d$) zeigte der Algorithmus eine stabile Konvergenz. Die relative Fehlerkurve sank mit der Anzahl der Iterationen.
• Vergleich mit [4]: Der Algorithmus wurde mit der Methode aus [4] (die nur $\|A\|$ berechnet, wenn $V=0$) verglichen.
  • Der vorgeschlagene Algorithmus ist etwas langsamer als die Methode aus [4] für den Spezialfall $V=0$, da er zwei Suchrichtungen und komplexere Schrittweitenoptimierung nutzt.
  • Dennoch ist er für den allgemeinen Fall $A-V$ die einzige bekannte Methode unter den gegebenen Speicherbeschränkungen.
• Anwendung auf Radon-Transformation (Astra-Toolbox):
  • Es wurde die Adjoint-Eigenschaft verschiedener Implementierungen der Radon-Transformation (Parallelstrahl-Geometrie) in der Astra-Toolbox getestet.
  • Für die Implementierungen $R_1, R_2, R_3$ und ihre zugehörigen Rückprojektionen $B_i$ ergab sich $\|R_i - B_i^*\| \approx 10^{-9}$. Dies bestätigt, dass diese Implementierungen numerisch adjungiert sind.
  • Im Gegensatz dazu zeigte der Vergleich mit der MATLAB-Funktion radon (und iradon ohne Filter) eine signifikante Diskrepanz ($\|A - V\| \geq 0.1$), was die Nicht-Adjoint-Eigenschaft dieser spezifischen Implementierung quantifiziert.

---

5. Bedeutung und Ausblick

Die Arbeit liefert ein essentielles Werkzeug für die numerische lineare Algebra und die angewandte Mathematik in der Bildgebung:

• Validierung von CT-Algorithmen: Sie ermöglicht es Ingenieuren und Wissenschaftlern, die Qualität der Diskretisierung von Vorwärts- und Rückprojektoren in der Computertomographie zu überprüfen, ohne die Matrizen explizit zu speichern.
• Robustheit iterativer Verfahren: Da viele Rekonstruktionsalgorithmen (wie Chambolle-Pock) von der Adjoint-Eigenschaft abhängen, hilft die Kenntnis von $\|A - V\|$ bei der Abschätzung von Konvergenzraten und Fehlergrenzen.
• Allgemeine Anwendbarkeit: Die Methode ist nicht auf die CT beschränkt, sondern kann überall dort eingesetzt werden, wo große lineare Operatoren als Black-Boxen vorliegen und deren Differenznorm geschätzt werden muss.

Zusammenfassend bietet das Papier eine theoretisch fundierte und praktisch effiziente Lösung für ein Problem, das bisher aufgrund von Speicherbeschränkungen und fehlenden Matrixdarstellungen schwer lösbar war.