Stabilizing the Rayleigh--Ritz procedure by randomization

Titel: Stabilisatie van de Rayleigh–Ritz-procedure door randomisatie

Auteur: Nian Shao (EPFL)
Datum: April 2026

---

1. Het Probleem

De kern van dit onderzoek ligt bij het extraheren van benaderingen voor eigenparen (eigenwaarde $\lambda$ en eigenvector $v$) vanuit een voorgeschreven deelruimte $W_\epsilon$. Dit is een fundamenteel probleem in numerieke lineaire algebra, waarbij deelruimtes vaak voortkomen uit methoden zoals Krylov-deelruimtes of reduced-basis technieken.

Hoewel het projecteren van de exacte eigenvector op de deelruimte een goede benadering oplevert, is het vinden van een eigenpaar (een Ritz-paar) dat een vergelijkbare convergentiesnelheid bereikt, een langdurig open probleem.

• De standaard Rayleigh–Ritz (RR) procedure is de gangbare methode, maar deze heeft ernstige stabiliteitsproblemen:
  • Voor niet-Hermitische matrices kan de convergentie van Ritz-waarden verslechteren tot $O(\epsilon^{1/m})$ (waarbij $m$ de dimensie van de deelruimte is).
  • Voor interne eigenwaarden van Hermitische matrices kunnen Ritz-waarden lineair convergeren in plaats van kwadratisch, en kunnen Ritz-vector volledig falen om te convergeren.
  • Bij generaliseerde en niet-lineaire eigenwaardeproblemen kan de standaardprocedure zelfs volledig falen (bijvoorbeeld als de gecomprimeerde matrixpencil singulair wordt, zelfs als de originele pencil regulier is).

De vraag is: Hoe kunnen we betrouwbaar een goede benadering van een eigenpaar extraheren uit een willekeurige deelruimte, zelfs als de standaardmethode faalt?

2. Methodologie: De Randomized Rayleigh–Ritz (RRR) Procedure

De auteur introduceert een gerandomiseerde Rayleigh–Ritz (RRR) procedure (Algorithm 1 en 2) die het stabiliteitsprobleem oplost door het gebruik van een oblivious subspace embedding via een complex Gaussische willekeurige matrix.

Het algoritme:

1. Input: Een matrixfunctie $A(\xi)$ (lineair of niet-lineair) en een orthonormale basis $W_\epsilon$ van de deelruimte.
2. Randomisatie: Trek een complex Gaussische willekeurige matrix $\Omega \in \mathbb{C}^{n \times m}$.
3. Gecomprimeerd probleem: In plaats van de standaard Galerkin-conditie ($W_\epsilon^H A W_\epsilon y = \mu y$) te gebruiken, wordt een Petrov–Galerkin-conditie opgelegd met de willekeurige matrix:
   $$\Omega^H A(\xi) W_\epsilon y = \mu \Omega^H W_\epsilon y$$
   Dit resulteert in een gecomprimeerd veralgemeend eigenwaardeprobleem van dimensie $m \times m$.
4. Verfijning: De verkregen "randomized Ritz-waarden" ($\mu_\epsilon$) worden verfijnd door de Rayleigh-kwotiënt (voor lineaire problemen) of een Rayleigh-functie/stationair punt (voor niet-lineaire problemen) te berekenen op de gevonden vector $W_\epsilon y_\epsilon$.

Het fundamentele idee:
Wanneer men een matrix $A(\lambda)W$ comprimeert met een willekeurige matrix $\Omega$, behoudt men met hoge waarschijnlijkheid de simple singulariteit van het probleem. In de standaard RR-procedure kan de compressie degenereren (bijvoorbeeld tot een nulmatrix of een Jordan-blok), wat leidt tot instabiliteit. De randomisatie voorkomt dit bijna zeker.

3. Belangrijkste Bijdragen

1. Oplossing voor een langdurig open probleem: De paper biedt een theoretisch onderbouwd antwoord op de vraag hoe men stabiel eigenparen kan extraheren, zelfs in situaties waar de standaard RR-procedure faalt (interne eigenwaarden, niet-Hermitisch, generaliseerde problemen).
2. Niet-asymptotische convergentiebewijzen: De auteur levert strikte, niet-asymptotische probabilistische grenzen. Dit betekent dat de resultaten gelden voor een specifieke, eindige dimensie en niet alleen in de limiet.
3. Generalisatie naar niet-lineaire problemen: De methode en de theorie zijn uitgebreid naar niet-lineaire eigenwaardeproblemen ($A(\lambda)v = 0$), wat een significant vooruitgang is ten opzichte van eerdere werken die zich beperkten tot lineaire problemen.
4. Vergelijking met bestaande methoden: De paper onderscheidt de RRR-procedure van de "sketched Rayleigh–Ritz" (die oversampling vereist) en verfijnde/harmonische RR-methoden (die geen garantie geven voor generaliseerde problemen).

4. Kernresultaten

De theoretische analyse toont aan dat voor een simpel eigenpaar $(\lambda, v)$ en een deelruimte met hoek $\epsilon = \angle(v, W_\epsilon)$, de RRR-procedure met hoge waarschijnlijkheid de volgende convergentiesnelheden bereikt:

• Randomized Ritz-vector: Convergeert lineair:
  $$\angle(v, W_\epsilon y_\epsilon) = O(\epsilon)$$
• Randomized Ritz-waarde: Convergeert lineair:
  $$|\lambda - \mu_\epsilon| = O(\epsilon)$$
• Verfijnde Randomized Ritz-waarde ($\rho_\epsilon$):
  • Voor Hermitische problemen: Kwadratische convergentie ($O(\epsilon^2)$).
  • Voor niet-Hermitische problemen: Lineaire convergentie ($O(\epsilon)$).

Belangrijke nuance: De constanten in deze $O$-notatie hangen alleen af van de conditiegetallen van het originele probleem (eigenwaarde en eigenvector conditiegetallen) en zijn onafhankelijk van de specifieke keuze van de deelruimte $W_\epsilon$. Dit is cruciaal, omdat het betekent dat de methode robuust is voor elke deelruimte die de eigenvector goed benadert.

Vergelijking met Standaard RR (Tabel 1 in de paper):

• Standaard RR: Kan falen (convergentie niet gegarandeerd) voor interne eigenwaarden, niet-Hermitische problemen en generaliseerde problemen.
• RRR: Biedt gegarandeerde convergentie voor alle bovenstaande gevallen, mits de eigenwaarde simpel is.

5. Numerieke Experimenten

De paper presenteert drie experimenten om de theorie te valideren:

1. Neutrale modi in Hamiltoniaanse systemen: Hier faalt de standaard RR-procedure volledig (in exacte rekenkunde) omdat de gecomprimeerde pencil verdwijnt. De RRR-procedure werkt echter perfect en levert optimale nauwkeurigheid op.
2. De "Butterfly" niet-lineaire eigenwaardeprobleem: Een complex niet-lineair probleem. De resultaten tonen aan dat voor Hermitische gevallen de verfijnde RRR-waarden kwadratisch convergeren, vergelijkbaar met de ideale projectie, terwijl ze voor niet-Hermitische gevallen significant nauwkeuriger zijn dan de standaard RR-methode.
3. Empirische waarschijnlijkheid en oversampling: Het experiment bevestigt dat de factor $1/\sqrt{\delta}$ in de theoretische foutgrenzen scherp is. Het toont ook aan dat oversampling (het vergroten van de dimensie van $\Omega$) in dit specifieke geval niet de prestaties verbetert, in tegenstelling tot wat vaak gebeurt bij andere gerandomiseerde algoritmen (zoals Randomized SVD).

6. Betekenis en Conclusie

Deze paper is van groot belang voor het veld van numerieke lineaire algebra en eigenwaardeberekeningen.

• Robuustheid: Het biedt een oplossing voor een van de meest bekende zwakke punten van de Rayleigh–Ritz-procedure: het gebrek aan stabiliteit bij niet-ideale situaties (interne eigenwaarden, niet-Hermitisch).
• Theoretische diepgang: De analyse van conditiegetallen na compressie met een Gaussische matrix biedt nieuwe inzichten in hoe randomisatie numerieke stabiliteit kan garanderen zonder de complexiteit van het probleem te vergroten.
• Praktische toepasbaarheid: Omdat de methode geen oversampling vereist en alleen een kleine $m \times m$ eigenwaardeprobleem moet oplossen, is deze computerefficiënt en direct toepasbaar in bestaande iteratieve solvers (zoals Krylov-methoden).

Kortom, de Randomized Rayleigh–Ritz-procedure transformeert een onbetrouwbare stap in eigenwaardeberekeningen in een robuust en wiskundig gegarandeerd proces, met een convergentiesnelheid die dicht bij de theoretische ideale projectie ligt.