An Improved Incremental Singular Value Decomposition and New Error Bounds

Technische Samenvatting: Een Verbeterde Incrementele Singuliere Waarde Decompositie en Nieuze Foutgrenzen

Probleemstelling
De Incrementele Singuliere Waarde Decompositie (SVD), oorspronkelijk voorgesteld door Brand [2, 3] en uitgebreid naar gewogen inproducten door Fareed et al. [10], is een standaardmethode voor laag-rangbenadering in streaming-data scenario's waarbij de volledige matrix niet kan worden opgeslagen. Het algoritme update een afgeknotte SVD ($U \approx Q\Sigma R^\top$) naarmate nieuwe kolommen binnenkomen. Echter, in drijvende-kommaberekening vermenigvuldigt elke update de lopende singuliere basis $Q$ met een kleine orthogonale factor. Hoewel individuele vermenigvuldigingen de orthogonaliteit tot aan afrondingsfouten behouden, hopen deze fouten zich op over de streamlengte $n$. Uiteindelijk verliest $Q$ numerieke orthogonaliteit, waardoor singuliere waarden onnauwkeurig worden en afkortingcriteria onbetrouwbaar.

De standaardremedie is periodieke reorthogonalisatie (bijvoorbeeld via Gewijzigde Gram–Schmidt), geactiveerd wanneer de orthogonaliteit verslechtert. De frequentie die nodig is om een voorgeschreven precisieniveau te handhaven, is echter een open vraag gebleven. Zoals opgemerkt door Brand [3, p. 28], was het onduidelijk hoe vaak reorthogonalisatie nodig is om een bepaald algeheel niveau van numerieke precisie te garanderen, vooral in gewogen settings (bijvoorbeeld eindige-elementen Proper Orthogonal Decomposition) waar reorthogonalisatie computationeel duur is.

Methodologie
De auteurs stellen een herstructurering van het incrementele SVD-algoritme voor die updates van de lopende singuliere factoren uitstelt. De kernmethodologie rust op twee observaties:

1. Rang-Niet-Toenemende Dominantie: In laag-rangtoepassingen liggen de meeste binnenkomende kolommen binnen de huidige deelruimte (residu $< \text{tol}$). Deze "rang-niet-toenemende" kolommen breiden de deelruimte niet uit.
2. Batchen: Het cumulatieve effect van $s$ opeenvolgende rang-niet-toenemende kolommen kan worden gereproduceerd door een enkele dunne SVD van een kort-en-dik buffermatrix die de projectiecoëfficiënten bevat, in plaats van $s$ aparte SVD's van omrande matrices uit te voeren.

Het voorgestelde algoritme (Algoritme 5) onderhoudt een buffer voor projectiecoëfficiënten van rang-niet-toenemende kolommen. De lopende factor $Q$ blijft tijdens deze stappen onveranderd. Wanneer een "rang-vergroterende" kolom binnenkomt (residu $\ge \text{tol}$), voert het algoritme het volgende uit:

• Het spoelt de buffer door een enkele dunne SVD te berekenen van de geaccumuleerde coëfficiënten en $Q$ en $R$ in een batch te updaten.
• Het verwerkt de nieuwe kolom, waarbij mogelijk een tweede afkortingstest wordt toegepast op de kleinste singuliere waarde van de lokale omrande matrix om verwaarloosbare rang te verwijderen.
• Het past een Klassieke Gram–Schmidt met twee doorgangen (CGS-2) alleen toe bij deze rang-vergroterende gebeurtenissen om de $W$-orthogonaliteit van de toegevoegde kolom te herstellen.

Deze herstructurering reduceert het aantal dure orthogonale vermenigvuldigingen toegepast op $Q$ van $O(n)$ (de streamlengte) naar $O(r + J_{E2})$, waarbij $r$ de numerieke rang is en $J_{E2}$ het aantal afkortende rang-vergroterende gebeurtenissen.

Belangrijkste Bijdragen
Het paper biedt twee primaire theoretische vooruitgangen en een praktische algoritmische verbetering:

1. Orthogonaliteitsgrens Onafhankelijk van Streamlengte:
   De auteurs bewijzen (Stelling 4.1) dat onder een standaard probabilistisch afrondingsfoutmodel het verlies van $W$-orthogonaliteit van de berekende linkerfactor $Q$ begrensd is door:
   $$\|I - Q^\top W Q\|_2 \leq c_1 (r + J_{E2}) r \sqrt{m} \log(2/\delta) \varepsilon_{\text{mach}} + O(\varepsilon_{\text{mach}}^2)$$
   Cruciaal is dat deze grens onafhankelijk is van de streamlengte $n$. Deze hangt af van $m$ (kolomdimensie) uitsluitend via een $\sqrt{m}$-factor. Dit lost Brands open vraag op: reorthogonalisatie is niet bij elke stap nodig; de voorgestelde batchingstrategie zorgt ervoor dat orthogonaliteit uniform in $n$ op machin precisie wordt gehandhaafd.

2. Scherpe Voorwaartse-Foutgrens:
   Het paper stelt een nieuwe voorwaartse-foutgrens vast voor de factorisatie in de $W$-gewogen operatornorm (Stelling 4.5):
   $$\|U - Q\Sigma R^\top\|_W \leq \sqrt{n} \, \text{tol} + (\text{rondoff-termen uniform in } n)$$
   Dit verscherpt de bestaande grens van Fareed en Singler [9], die $n \, \text{tol}$ was. De auteurs demonstreren via een constructief voorbeeld dat de $\sqrt{n}$-snelheid haalbaar is, wat aantoont dat de vorige grens een factor $\sqrt{n}$ te ruim was.

3. Algoritmische Efficiëntie:
   Door het aantal dure reorthogonalisatiestappen te reduceren en updates te batchen, reduceert het voorgestelde algoritme de computationele overhead aanzienlijk.

Resultaten
Numerieke experimenten werden uitgevoerd op een 2D parabolisch testprobleem (zowel ongewogen als gewogen eindige-elementen settings) en synthetische data.

• Orthogonaliteit: Terwijl bestaande algoritmen (Brands directe update en Fareeds gereorthogonaliseerde update) een degradatie van de orthogonaliteit vertoonden die groeide met $n$ (afdrijvend naar $10^{-3}$ in gewogen gevallen), handhaafde het voorgestelde algoritme de orthogonaliteit op machin precisie ($\sim 10^{-14}$) over streamlengten tot $n=10.000$ en kolomdimensies tot $m=100.000$.
• Foutgrenzen: Experimenten bevestigden de $\sqrt{n} \, \text{tol}$-afkortingssnelheid. Op een constructief voorbeeld kwam de gemeten fout overeen met de $\sqrt{n} \, \text{tol}$-voorspelling, terwijl de Fareed–Singler-grens ($n \, \text{tol}$) een factor los was die groeide als $\sqrt{n}$.
• Prestaties: Het voorgestelde algoritme draaide 4,5$\times$ tot 34$\times$ sneller dan zijn naaste concurrenten. In het gewogen geval besteedde het bestaande algoritme 94% van zijn tijd aan reorthogonalisatie, terwijl het voorgestelde algoritme deze kosten met drie ordes van grootte reduceerde.

Betekenis
Het paper claimt de open vraag betreffende de frequentie van reorthogonalisatie in incrementele SVD op te lossen. Door het algoritme te herstructureren om rang-niet-toenemende updates te batchen, wordt het volgende bereikt:

1. Uniforme Orthogonaliteit: De lopende basis blijft numeriek orthogonaal ongeacht de streamlengte, waardoor de behoefte aan heuristische, periodieke reorthogonalisatiecontroles die geen a priori garanties bieden, wordt geëlimineerd.
2. Strakkere Foutanalyse: Het biedt een wiskundig rigoureuze, scherpe foutgrens ($\sqrt{n} \, \text{tol}$) die de state-of-the-art verbetert met een factor $\sqrt{n}$.
3. Praktische Snelheidswinst: De methode biedt aanzienlijke snelheidswinsten in toepassingen die worden gedomineerd door kosten voor reorthogonalisatie, zoals eindige-elementen POD, zonder nauwkeurigheid op te offeren.

De auteurs merken op dat het algoritme al in voorlopige versies is toegepast op tijds-fractionele PDE's, integro-differentiaalvergelijkingen en door PDE's beperkte optimalisatie, vertrouwend op de nu vastgestelde orthogonaliteits- en foutgaranties. Toekomstig werk wordt voorgesteld om de analyse van de orthogonaliteitsdrift te verscherpen (momenteel conservatief met $\sim 10^3$) en de projectiestap te optimaliseren, die momenteel de runtime domineert.