A Sketched Generalized Krylov Subspace Method for Large-Scale Regularization

Technische Samenvatting: Een geschetste algemene Krylov-subruimte methode voor grootschalige regularisatie

Probleemstelling
Het artikel behandelt grootschalige slecht gestelde kleinste-kwadratenproblemen van de vorm $\min_{x} \|Ax - b\|_2^2$, waarbij de matrix $A$ ernstig slecht geconditioneerd is en $b$ door ruis gecontamineerd is. Om de oplossing te stabiliseren, wordt Tikhonov-regularisatie toegepast, wat leidt tot het gepenaliseerde probleem:
$$\min_{x \in \mathbb{R}^n} \left\{ \|Ax - b\|_2^2 + \lambda \|Lx\|_2^2 \right\},$$
waarbij $L$ een algemene regularisatiematrix is die voorkennis codeert. Hoewel efficiënte methoden bestaan voor standaardvorm Tikhonov ($L=I$), is het afhandelen van een algemene $L$ computationeel uitdagend. De Generalized Krylov Subspace (GKS) methode [28] werd voorgesteld om algemene $L$ te behandelen door een zoekruimte uit te breiden met behulp van de gradiënt van de Tikhonov-functionaal. Echter, naarmate de dimensie van de subruimte groeit, krijgt GKS te maken met twee verboden computationele knelpunten:

1. Dunne QR-factorisaties: Het bijwerken van de QR-factorisaties van de geprojecteerde matrices $AV_k$ en $LV_k$ bij elke iteratie.
2. Reorthogonalisatie: Het expliciet reorthogonaliseren van nieuwe basisvectoren tegen alle voorgaande kolommen om numerieke stabiliteit te behouden, wat volledige inwendige productberekeningen vereist.

Deze operaties schalen ongunstig met het aantal iteraties en de probleemgrootte, wat de schaalbaarheid van GKS voor grootschalige inverse problemen beperkt.

Methodologie: Geschetste GKS (sGKS)
De auteurs stellen sGKS voor, een gerandomiseerde variant van de GKS-methode die gebruikmaakt van sketching (gerandomiseerde dimensionaliteitsreductie) om de meest kostbare stappen te versnellen terwijl de benaderingskwaliteit behouden blijft. De methodologie rust op twee primaire observaties:

1. Eliminatie van expliciete reorthogonalisatie: De auteurs observeren dat het GKS-algoritme voor zijn kernstappen niet intrinsiek afhankelijk is van de orthogonaliteit van de basisvectoren (in tegen tegenstelling tot klassieke Krylov-methoden voor lineaire stelsels die vertrouwen op Arnoldi/Lanczos-relaties). Bijgevolg slaat sGKS de expliciete reorthogonalisatie van de basis volledig over. In plaats van een orthonormale basis $V_k$ te onderhouden, onderhoudt sGKS een niet-orthonormale basis $W_k$ gevormd door het aanhangen van de ruwe gradiëntvectoren. Dit verwijdert de $O(d_k^2 n)$ kosten van reorthogonalisatie (waarbij $d_k$ de dimensie van de subruimte is).

2. Sketch-and-Solve voor geprojecteerde problemen: Om de kosten van het oplossen van het geprojecteerde Tikhonov-probleem en het bijwerken van QR-factorisaties te verminderen, gebruikt sGKS sketching-operatoren $S_A$ en $S_L$.

   • Het geprojecteerde kleinste-kwadratenprobleem wordt opgelost op gecomprimeerde matrices $S_A A W_k$ en $S_L L W_k$ in plaats van de volledige $A W_k$ en $L W_k$.
   • De QR-factorisaties worden uitgevoerd op deze geschetste matrices van grootte $s \times d_k$ en worden incrementeel bijgewerkt via rang-één extensies.
   • De gebruikte sketching-operatoren zijn Oblivious Subspace Embeddings (specifiek Subsampled Randomized Trigonometric Transforms, SRTT), die alleen afhangen van de dimensie van de subruimte, niet van de subruimte zelf.

Belangrijkste Bijdragen

• Algoritmisch Ontwerp: De ontwikkeling van sGKS, die gerandomiseerde sketching integreert in het GKS-raamwerk voor algemene vorm Tikhonov-regularisatie.
• Theoretische Analyse:
  • Equivalentie: De auteurs bewijzen dat als sketching wordt weggelaten in de geprojecteerde oplossing, sGKS iteraten produceert die wiskundig identiek zijn aan standaard GKS (Propositie 1).
  • Quasi-optimaliteit: Ze demonstreren dat wanneer sketching wordt toegepast, de methode quasi-optimale residunormen oplevert, waarbij de fout wordt gecontroleerd door de embedding-kwaliteit ($\epsilon$) van de sketching-operatoren (Propositie 2).
  • Iteratieve Verfijning: Voor gevallen waarin het verlies van basis-orthogonaliteit significant wordt (wat leidt tot numerieke rangtekort), tonen zij aan dat het opnemen van een klein aantal stappen van iteratieve verfijning (IR) in de geprojecteerde oplossing de spectrale eigenschappen van de basis herstelt en de volledige nauwkeurigheid van de ongeschetste methode terugwint.
• Computationele Efficiëntie: De methode vermindert de kosten per iteratie door dure full-rank QR-updates en reorthogonalisatie te vervangen door goedkopere operaties op gecomprimeerde matrices.

Numerieke Resultaten
Het artikel evalueert sGKS op vier grootschalige inverse problemen:

1. Beeldontblurring (Image Deblurring): sGKS met verschillende sketch-dimensies ($s$) bereikt een reconstructiekwaliteit die vergelijkbaar is met standaard GKS. Grotere $s$ levert convergentietrajecten op die bijna ononderscheidbaar zijn van GKS, terwijl kleinere $s$ resulteert in iets hogere eindfouten maar snellere convergentie.
2. X-ray CT Reconstructie: Op een probleem met $n=250.000$ onbekenden en een grote regularisatie-operator ($p \approx 500.000$), evenaart sGKS de reconstructienauwkeurigheid van GKS (RRE $\approx 0,183$) terwijl de rekentijd aanzienlijk wordt verminderd. De versnelling wordt gedreven door het elimineren van reorthogonalisatie en het verminderen van de QR-updatekosten van $O(p)$ naar $O(s)$.
3. Seismische Travel-Time Tomografie: Op een spaar systeem, overgedetermineerd, presteert sGKS beter dan hybride LSQR-methoden in zowel nauwkeurigheid als snelheid. Hoewel de versnelling ten opzichte van standaard GKS hier bescheiden is (omdat gradiëntberekening domineert), biedt sGKS nog steeds een reductie van 10% in tijd terwijl een superieure reconstructiekwaliteit wordt behouden vergeleken met LSQR-varianten.
4. Dynamische CT: In een ruimte-tijd formulering met een massieve regularisatie-operator, domineren de QR- en reorthogonalisatiekosten de standaard GKS-runtime. Hier bereikt sGKS een 3$\times$ versnelling ten opzichte van standaard GKS. De inclusie van iteratieve verfijning (IR) stelt sGKS in staat om het exacte convergentietraject en de optimale regularisatieparameter van de ongeschetste GKS te herstellen, terwijl sGKS zonder IR stagneert op een iets hogere fout.

Betekenis en Claims
Het artikel claimt dat sGKS een schaalbaar alternatief is voor standaard GKS voor grootschalige regularisatie met algemene matrices. De betekenis ligt in:

• Schaalbaarheid: Het verwijdert de computationele knelpunten (reorthogonalisatie en full-rank QR-updates) die voorheen de toepasbaarheid van GKS op zeer grote problemen beperkten.
• Behoud van Nauwkeurigheid: Het behoudt de reconstructiekwaliteit van de oorspronkelijke methode, met theoretische garanties op residunormen en empirisch bewijs dat iteratieve verfijning de volledige nauwkeurigheid kan herstellen, zelfs wanneer de orthogonaliteit van de basis verloren gaat.
• Generaliteit: De aanpak is onafhankelijk van de specifieke keuze van de sketching-operator en is toepasbaar op algemene regularisatiematrices $L$, niet alleen op standaardvorm-problemen.

De auteurs concluderen dat hoewel de methode een sketching-parameter ($s$) introduceert om de afweging tussen snelheid en nauwkeurigheid af te stemmen, het een robuust raamwerk biedt voor het oplossen van grootschalige inverse problemen waarbij standaard projectiemethoden computationeel onhaalbaar zijn. Voorgesteld toekomstig werk omvat adaptieve selectie van de sketch-dimensie en uitbreidingen naar nietlineaire inverse problemen.