A Variational Equation and Lower Bound for the Linear Least-Squares Backward Error

Technische Zusammenfassung: Eine Variationsgleichung und eine untere Schranke für den linearen kleinsten Quadrate-Rückwärtsfehler

Problemstellung
Der Artikel behandelt die Herausforderung, den Rückwärtsfehler $\mu$ für lineare Ausgleichsprobleme mit mehreren rechten Seiten effizient zu schätzen:
$$\min_{X \in \mathbb{R}^{n \times d}} \|AX - B\|_F$$
wobei $A \in \mathbb{R}^{m \times n}$ und $B \in \mathbb{R}^{m \times d}$. Der Rückwärtsfehler $\mu$ ist definiert als die minimale Norm von Störungen $[E, \theta F]$, sodass die Näherungslösung $X$ zu einer exakten Lösung des gestörten Systems $(A+E)^T(A+E)X = (A+E)^T(B+F)$ wird.

Die direkte Berechnung von $\mu$ ist für iterative Löser prohibitiv teuer, da sie die Lösung eines großen Eigenwertproblems oder eines verallgemeinerten Eigenwertproblems erfordert. Zwar existieren Schätzungen (wie die Karlson-Waldén-Schätzung), diese sind jedoch oft teuer exakt zu berechnen oder verfügen nicht über garantierte Schranken (d. h., sie sind weder strikte obere noch untere Schranken). Der Artikel sucht nach einer Methode, zuverlässige und rechnerisch günstige Schätzungen abzuleiten, wobei der Fokus speziell auf unteren Schranken liegt, die als Abbruchkriterien für iterative Verfahren wie LSQR und LSMR dienen können.

Methodik
Die Kernmethodik basiert darauf, den Rückwärtsfehler im Rahmen der indefiniten linearen Algebra als verallgemeinertes Eigenwertproblem auszudrücken.

1. Variationsformulierung: Der Artikel stellt zunächst eine Variationsgleichung für den Rückwärtsfehler $\mu(A, R_\theta)$ auf, wobei $R_\theta$ eine transformierte Residuenmatrix ist. Er drückt $\mu$ als Maximierungsproblem über eine indefiniente Mannigfaltigkeit aus, die durch die Bedingung $X^T J_{n,d} X = -I_d$ definiert ist, wobei $J_{n,d} = \text{diag}(I_n, -I_d)$.
   $$\mu(A, R_\theta) = \sup_{X^T J_{n,d} X = -I_d} \left( \|R_\theta\|_F^2 - \|[A, R_\theta]X\|_F^2 \right)^{1/2}$$
2. Hyperbolische CS-Zerlegung: Um dieses Optimierungsproblem zu lösen, nutzen die Autoren die hyperbolische CS-Zerlegung (ein indefinites Analogon zur CS-Zerlegung für unitäre Matrizen). Diese Zerlegung ermöglicht es, die Optimierung über die Matrix $X$ in Optimierungen über orthogonale Matrizen und diagonale Skalierungsmatrizen zu entkoppeln.
3. Zerlegungstheorem: Durch Anwendung dieser Zerlegung leitet der Artikel ein Theorem her, das zeigt, dass sich der Rückwärtsfehler für ein Problem mit $d$ rechten Seiten in die Summe von $d$ kleineren Rückwärtsfehlerproblemen zerlegen lässt, wobei jedes einzelne eine rechte Seite betrifft.
4. Konstruktion einer unteren Schranke: Unter Ausnutzung dieser Zerlegung schlagen die Autoren eine skizzierungsbasierte untere Schranke vor. Durch Berechnung eines einzelnen Testvektors $p$ unter Verwendung einer geskizzeten Matrix $SA$ (wobei $S$ eine Skizzierungsmatrix ist), können sie die Formel für den Rückwärtsfehler mit einer rechten Seite auswerten. Dies liefert eine beweisbare untere Schranke für den wahren Rückwärtsfehler.

Hauptbeiträge

• Theorem 1 (Zerlegung): Der primäre theoretische Beitrag ist die Zerlegung des Rückwärtsfehlers $\mu(A, R_\theta)$ in eine Summe kleinerer Terme:
  $$\mu(A, R_\theta) = \max_{P, Q} \left( \sum_{i=1}^k \mu^2(Ap_i, R_\theta q_i) \right)^{1/2}$$
  wobei $P$ und $Q$ Matrizen mit orthonormalen Spalten sind. Dies reduziert die Komplexität des Problems auf eine Reihe skalarer Optimierungen.
• Exakter Ausdruck für eine rechte Seite: Der Artikel liefert einen stabilen, geschlossenen Ausdruck für den Rückwärtsfehler im Fall einer rechten Seite, $\mu(a, r)$, der von den Normen der Summe und Differenz der Vektoren abhängt:
  $$\mu(a, r) = \frac{2|a^T r|}{\|a+r\|_2 + \|a-r\|_2}$$
• Skizzierungsbasierte untere Schranke: Die Autoren schlagen eine neue untere Schranke für iterative Verfahren vor. Durch Verwendung einer Skizzierungsmatrix $S$ zur Berechnung einer Näherungsrichtung $p$ können sie die Formel für eine rechte Seite auswerten, um einen Wert $\mu(Ap/\|p\|_2, r_\theta)$ zu erhalten.
  • Dieser Wert ist beweisbar eine untere Schranke für den wahren Rückwärtsfehler.
  • Der Artikel beweist, dass diese untere Schranke qualitativ mit der geskizzierten Karlson-Waldén-Schätzung vergleichbar ist und speziell die Ungleichung erfüllt:
    $$\frac{1-\eta^2}{1+\eta^2} \nu(A, r_\theta) \leq \mu(Ap/\|p\|_2, r_\theta) \leq \mu(A, r_\theta)$$
    wobei $\eta$ die Verzerrung der Skizzierung darstellt und $\nu$ die Karlson-Waldén-Schätzung ist.
• Iterative Verfeinerung und Wiederverwendung: Der Artikel diskutiert Methoden zur Verbesserung dieser Schätzung durch iterative Verfeinerung des Vektors $p$ und das „Recycling" des berechneten Vektors $Ap$ über Iterationen hinweg, um die Rechenkosten zu senken.

Ergebnisse
Numerische Experimente wurden mit dem LSMR-Löser an einer Matrix aus der SuiteSparse-Sammlung mit einer hohen Konditionszahl ($\approx 3.5 \times 10^{16}$) durchgeführt. Die Ergebnisse zeigen:

• Die vorgeschlagene untere Schranke ist in ihrer Genauigkeit konsistent mit der geskizzierten Karlson-Waldén-Schätzung vergleichbar.
• In Fällen mit günstigeren Skizzierungen (kleineres $n_{sketch}$) war die vorgeschlagene untere Schranke manchmal genauer als die geskizzierte Karlson-Waldén-Schätzung.
• Die „recycelte" untere Schranke (Wiederverwendung von $Ap$ über Iterationen hinweg) blieb für einen erheblichen Teil der Iterationshistorie nahe am wahren Rückwärtsfehler, was ihre Eignung als kostengünstiger Fehlermonitor nahelegt.
• Eine iterative Verfeinerung des Vektors $p$ verbesserte die Genauigkeit nur, wenn die Skizzierungsgröße sehr groß war ($16n$), was darauf hindeutet, dass für Standard-Skizzierungsgrößen die zusätzlichen Rechenkosten möglicherweise nicht gerechtfertigt sind.
• Versuche, obere Schranken mit ähnlichen Techniken zu konstruieren, erwiesen sich als nur marginal besser als bestehende einfache Schranken (wie $\|A^T r\|_2 / \|r\|_2$) und überschätzten den wahren Fehler nach wie vor erheblich.

Bedeutung und Behauptungen
Der Artikel beansprucht seine primäre Bedeutung als theoretisch: Er liefert eine Zerlegung des Rückwärtsfehlers, die natürlich zu berechenbaren unteren Schranken führt.

• Zuverlässigkeit: Im Gegensatz zur geskizzierten Karlson-Waldén-Schätzung, für die nicht garantiert ist, dass sie eine obere oder untere Schranke darstellt, liefert die vorgeschlagene Methode eine strikt untere Schranke. Dies ist für Abbruchkriterien wertvoll, da sie garantiert, dass der wahre Fehler mindestens so groß wie die Schätzung ist.
• Effizienz: Die Methode ermöglicht die Umwandlung einer skizzierungsbasierten Schätzung in eine untere Schranke mit vergleichbarer Qualität, jedoch mit dem zusätzlichen Garant, dass es sich um eine Schranke handelt.
• Bescheidenheit: Die Autoren sind bezüglich oberer Schranken bescheiden und stellen fest, dass ihre Versuche, obere Schranken auf ähnliche Weise zu erzeugen, „im Allgemeinen erfolglos" waren. Sie erkennen an, dass die Zerlegung für mehrere rechte Seiten die Optimierung über zwei Matrizen ($P$ und $Q$) beinhaltet, was komplexer ist als die für die untere Schranke erforderliche Optimierung über einen einzelnen Vektor. Als zukünftige Arbeit wird vorgeschlagen, den Fall mehrerer rechter Seiten zu adressieren und zu untersuchen, warum das Finden guter oberer Schranken schwieriger zu sein scheint als das Finden guter unterer Schranken.