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

Technische Samenvatting: Een Variationale Vergelijking en Ondergrens voor de Lineaire Kleinste-Kwadraten Achterwaartse Fout

Probleemstelling
Het artikel behandelt de uitdaging om de achterwaartse fout, $\mu$, voor lineaire kleinste-kwadratenproblemen met meerdere rechterhandkanten efficiënt te schatten:
$$\min_{X \in \mathbb{R}^{n \times d}} \|AX - B\|_F$$
waarbij $A \in \mathbb{R}^{m \times n}$ en $B \in \mathbb{R}^{m \times d}$. De achterwaartse fout $\mu$ wordt gedefinieerd als de minimale norm van perturbaties $[E, \theta F]$ zodat de benaderde oplossing $X$ een exacte oplossing wordt van het geperturbeerde systeem $(A+E)^T(A+E)X = (A+E)^T(B+F)$.

De directe berekening van $\mu$ is voor iteratieve oplosmethoden onbetaalbaar duur, omdat deze het oplossen van een groot eigenwaardeprobleem of een gegeneraliseerd eigenwaardeprobleem vereist. Hoewel er schattingen bestaan (zoals de Karlson-Waldén-schatting), zijn deze vaak duur om exact te berekenen of missen ze gegarandeerde grenzen (d.w.z. ze zijn strikt geen boven- of ondergrenzen). Het artikel zoekt een methode om betrouwbare, rekenkundig goedkope schattingen af te leiden, met name gericht op ondergrenzen die kunnen dienen als stopcriteria voor iteratieve methoden zoals LSQR en LSMR.

Methodologie
De kernmethodologie vertrouwt op het uitdrukken van de achterwaartse fout in termen van een gegeneraliseerd eigenwaardeprobleem binnen het kader van indefiniete lineaire algebra.

1. Variationale Formulering: Het artikel stelt eerst een variationale vergelijking op voor de achterwaartse fout $\mu(A, R_\theta)$, waarbij $R_\theta$ een getransformeerde residumatrix is. Het drukt $\mu$ uit als een maximalisatieprobleem over een indefiniete variëteit die wordt gedefinieerd door de constraint $X^T J_{n,d} X = -I_d$, waarbij $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-decompositie: Om dit optimalisatieprobleem op te lossen, maken de auteurs gebruik van de hyperbolische CS-decompositie (een indefiniet analogon van de CS-decompositie voor unitaire matrices). Deze decompositie maakt het mogelijk om de optimalisatie over de matrix $X$ te ontkoppelen in optimalisaties over orthogonale matrices en diagonale schalingsmatrices.
3. Decompositiestelling: Door deze decompositie toe te passen, leidt het artikel een stelling af die aantoont dat de achterwaartse fout voor een probleem met $d$ rechterhandkanten kan worden opgesplitst in de som van $d$ kleinere achterwaartse foutproblemen, waarbij elk slechts één rechterhandkant betreft.
4. Constructie van Ondergrens: Door gebruik te maken van deze decompositie, stellen de auteurs een op schetsing gebaseerde ondergrens voor. Door een enkele testvector $p$ te berekenen met behulp van een gesketste matrix $SA$ (waarbij $S$ een schetsingsmatrix is), kunnen ze de formule voor de achterwaartse fout met één rechterhandkant evalueren. Dit levert een bewijsbaar ondergrens op de ware achterwaartse fout.

Belangrijkste Bijdragen

• Stelling 1 (Decompositie): De primaire theoretische bijdrage is de decompositie van de achterwaartse fout $\mu(A, R_\theta)$ in een som van kleinere termen:
  $$\mu(A, R_\theta) = \max_{P, Q} \left( \sum_{i=1}^k \mu^2(Ap_i, R_\theta q_i) \right)^{1/2}$$
  waarbij $P$ en $Q$ matrices zijn met orthonormale kolommen. Dit reduceert de complexiteit van het probleem tot een reeks scalaire optimalisaties.
• Exacte Uitdrukking voor Eén Rechterhandkant: Het artikel biedt een stabiele, gesloten-vorm uitdrukking voor de achterwaartse fout in het geval van één rechterhandkant, $\mu(a, r)$, die afhankelijk is van de normen van de som en het verschil van de vectoren:
  $$\mu(a, r) = \frac{2|a^T r|}{\|a+r\|_2 + \|a-r\|_2}$$
• Op Schetsing Gebaseerde Ondergrens: De auteurs stellen een nieuwe ondergrens voor iteratieve methoden voor. Door een schetsingsmatrix $S$ te gebruiken om een benaderingsrichting $p$ te berekenen, kunnen ze de formule voor één rechterhandkant evalueren om een waarde $\mu(Ap/\|p\|_2, r_\theta)$ te verkrijgen.
  • Deze waarde is bewijsbaar een ondergrens op de ware achterwaartse fout.
  • Het artikel bewijst dat deze ondergrens van kwaliteit vergelijkbaar is met de gesketste Karlson-Waldén-schatting, en specifiek voldoet aan de ongelijkheid:
    $$\frac{1-\eta^2}{1+\eta^2} \nu(A, r_\theta) \leq \mu(Ap/\|p\|_2, r_\theta) \leq \mu(A, r_\theta)$$
    waarbij $\eta$ de vervorming van de schets voorstelt en $\nu$ de Karlson-Waldén-schatting is.
• Iteratieve Verfijning en Hergebruik: Het artikel bespreekt methoden om deze schatting te verbeteren via iteratieve verfijning van de vector $p$ en het "hergebruiken" van de berekende vector $Ap$ over iteraties heen om de rekenkosten te verlagen.

Resultaten
Numerieke experimenten werden uitgevoerd met de LSMR-oplosser op een matrix uit de SuiteSparse-collectie met een hoge conditiegetal ($\approx 3.5 \times 10^{16}$). De resultaten geven aan:

• De voorgestelde ondergrens is consequent vergelijkbaar in nauwkeurigheid met de gesketste Karlson-Waldén-schatting.
• In gevallen met goedkopere schetsen (kleinere $n_{sketch}$) was de voorgestelde ondergrens soms nauwkeuriger dan de gesketste Karlson-Waldén-schatting.
• De "hergebruikte" ondergrens (waarbij $Ap$ over iteraties wordt hergebruikt) bleef gedurende een aanzienlijk deel van de iteratiegeschiedenis dicht bij de ware achterwaartse fout, wat wijst op bruikbaarheid als goedkope foutmonitor.
• Iteratieve verfijning van de vector $p$ verbeterde de nauwkeurigheid alleen wanneer de schetsgrootte zeer groot was ($16n$), wat suggereert dat voor standaard schetsgroottes de extra rekenkosten mogelijk niet gerechtvaardigd zijn.
• Pogingen om bovengrenzen te construeren met vergelijkbare technieken bleken slechts marginaal beter dan bestaande eenvoudige grenzen (zoals $\|A^T r\|_2 / \|r\|_2$) en onderschatten de ware fout nog steeds aanzienlijk.

Betekenis en Beweringen
Het artikel claimt dat zijn primaire betekenis theoretisch is: het biedt een decompositie van de achterwaartse fout die op natuurlijke wijze leidt tot berekenbare ondergrenzen.

• Betrouwbaarheid: In tegenstelling tot de gesketste Karlson-Waldén-schatting, die niet gegarandeerd een boven- of ondergrens is, levert de voorgestelde methode een strikt ondergrens op. Dit is waardevol voor stopcriteria, omdat het garandeert dat de ware fout ten minste zo groot is als de schatting.
• Efficiëntie: De methode maakt het mogelijk om een op schetsing gebaseerde schatting om te zetten in een ondergrens met vergelijkbare kwaliteit, maar met de toegevoegde garantie dat het een grens is.
• Bescheidenheid: De auteurs zijn bescheiden wat betreft bovengrenzen, en merken op dat hun pogingen om op vergelijkbare wijze bovengrenzen te produceren "over het algemeen mislukten". Zij erkennen dat de decompositie voor meerdere rechterhandkanten optimalisatie over twee matrices ($P$ en $Q$) vereist, wat complexer is dan de optimalisatie over één vector die nodig is voor de ondergrens. Er wordt voorgesteld om toekomstig werk te richten op het geval met meerdere rechterhandkanten en om te onderzoeken waarom het vinden van goede bovengrenzen moeilijker lijkt dan het vinden van goede ondergrenzen.