Finding accurate eigenvalues and eigenvectors of positive semi-definite matrices given a subspace

Technische Samenvatting: Het Vinden van Nauwkeurige Eigenwaarden en Eigenvectoren van Positief Semi-Definiete Matrices Gegeven een Deelruimte

Probleemstelling
Het artikel behandelt een klassiek probleem in de numerieke lineaire algebra: gegeven een $n \times n$ positief semi-definiete (PSD) matrix $A$ en een $k$-dimensionale deelruimte $Q$ (weergegeven door een orthonormale basis-matrix $Q \in \mathbb{R}^{n \times k}$) die de leidende eigenruimte van $A$ benadert, hoe kan men dan nauwkeurige eigenwaarden en eigenvectoren extraheren? Hoewel de Rayleigh-Ritz (RR) methode de standaardbenadering voor deze taak is, onderzoeken de auteurs of het specifieke structurele kenmerk dat $A$ PSD is, kan worden benut om de nauwkeurigheid te verbeteren ten opzichte van wat RR biedt, zonder de computationele complexiteit te verhogen.

Methodologie
Het artikel vergelijkt drie projectie-gebaseerde methoden die dezelfde computationele complexiteit van $O(Nk + nk^2)$ delen, waarbij $N$ de kosten zijn van een matrix-vector vermenigvuldiging met $A$:

1. Rayleigh-Ritz (RR): De standaardmethode die de eigenwaarden van de geprojecteerde matrix $Q^\top A Q$ berekent. De benaderde eigenwaarden zijn $\hat{\lambda}_i^{(RR)} = \lambda_i(Q^\top A Q)$.
2. SVD-extract: Deze methode maakt gebruik van de equivalentie tussen eigenwaarden en singuliere waarden voor PSD-matrices. Het berekent de singuliere waarden van de eenzijdige projectie $AQ$. De benaderde eigenwaarden zijn $\hat{\lambda}_i^{(SVD)} = \sigma_i(AQ)$.
3. Nyström-methode: Deze methode construeert een laag-rang benadering van $A$, aangeduid als $A_{\langle Q \rangle} = AQ(Q^\top AQ)^\dagger (AQ)^\top$, en extrahert eigenwaarden uit deze benadering. De benaderde eigenwaarden zijn $\hat{\lambda}_i^{(Nys)} = \lambda_i(A_{\langle Q \rangle})$.

De auteurs analyseren deze methoden theoretisch door de deelruimte $Q$ te modelleren als een $\epsilon$-benadering van de dominante invariantie-deelruimte $U_1$ van $A$. Zij maken gebruik van perturbatie-analyse, Schur-complementen en eigenschappen van PSD-matrices om foutgrenzen voor de eigenwaarde-benaderingen af te leiden.

Belangrijkste Bijdragen en Theoretische Resultaten

• Nauwkeurigheidshiërarchie voor Leidende Eigenwaarden: Het artikel stelt een strikte ordening van nauwkeurigheid vast voor het benaderen van de leidende eigenwaarden (die welke corresponderen met de grootste eigenwaarden van $A$). De auteurs bewijzen de volgende ongelijkheid voor de benaderde eigenwaarden:
  $$\lambda_i(A) \geq \lambda_i(A_{\langle Q \rangle}) \geq \sigma_i(AQ) \geq \lambda_i(Q^\top A Q)$$
  Bijgevolg voldoet de absolute fout aan:
  $$|\lambda_i(A) - \hat{\lambda}_i^{(RR)}| \geq |\lambda_i(A) - \hat{\lambda}_i^{(SVD)}| \geq |\lambda_i(A) - \hat{\lambda}_i^{(Nys)}|$$
  Dit demonstreert dat Nyström de meest nauwkeurige schattingen biedt, gevolgd door SVD-extract, waarbij RR de minst nauwkeurige is.

• Hoger-orde Nauwkeurigheid van Nyström: De auteurs leiden kwantitatieve foutgrenzen af die aantonen dat Nyström een hoger-orde nauwkeurigheid bereikt in vergelijking met RR en SVD-extract. Specifiek, wanneer het spectrum van $A$ snel afneemt (d.w.z. $\lambda_1 \gg \lambda_{k+1}$), kan de fout van de Nyström-methode voor de leidende eigenwaarden kleiner zijn dan die van RR en SVD-extract met een factor evenredig aan $\lambda_1(A)/\lambda_{k+1}(A)$. Deze verbetering kan willekeurig groot zijn.

• Omkering voor Aanhangende Eigenwaarden: Het artikel merkt op dat de situatie omkeert wanneer men gericht is op de aanhangende (kleinste) eigenwaarden. In dit regime presteert de Nyström-methode slecht, en wordt RR de meest nauwkeurige methode. De auteurs schrijven dit toe aan het feit dat de deelruimte $\text{span}(AQ)$ (gebruikt door Nyström en SVD-$\tilde{U}$) een betere benadering is van de leidende invariantie-deelruimte $U_1$, maar een slechtere benadering van de aanhangende invariantie-deelruimte $U_2$ in vergelijking met $\text{span}(Q)$.

• Remedie voor Aanhangende Eigenwaarden: Om de slechte prestaties van Nyström voor aanhangende eigenwaarden aan te pakken, suggereren de auteurs een shift-and-flip-strategie. Door de leidende eigenparen van de verschoven matrix $\gamma I - A$ te berekenen (waarbij $\gamma \geq \lambda_{\max}(A)$), kan de Nyström-methode effectief worden toegepast om de aanhangende eigenwaarden van de oorspronkelijke matrix te herstellen.

Resultaten en Numerieke Experimenten
De theoretische bevindingen worden gevalideerd door middel van numerieke experimenten:

• Leidende Eigenwaarden: Wanneer $A$ een snel afnemend spectrum heeft (exponentiële afname), presteert de Nyström-methode aanzienlijk beter dan RR en SVD-extract, met fout-hellingen die convergentie van hoger-orde aangeven. Wanneer het spectrum langzaam afneemt (algebraïsch of lineair), neemt het voordeel van Nyström af, maar blijft het aanwezig.
• Eigenvectoren: Vergelijkbare trends worden waargenomen voor eigenvector-benaderingen. Methoden die gebruikmaken van de deelruimte $\text{span}(AQ)$ (Nyström en SVD-$\tilde{U}$) leveren nauwkeurigere leidende eigenvectoren op dan die beperkt tot $\text{span}(Q)$ (RR en SVD-$Q\tilde{V}$).
• Aanhangende Eigenwaarden: Experimenten bevestigen dat RR superieur is voor aanhangende eigenwaarden, terwijl Nyström faalt tenzij de shift-and-flip-techniek wordt toegepast.

Betekenis en Beweringen
Het artikel beweert een ogenschijnlijke inconsistentie in de literatuur op te lossen: terwijl bekend is dat RR optimaal is in de zin van min-max karakterisering en deelruimte-projectie, sluit deze optimaliteit niet uit dat er nauwkeurigere eigenwaarde-benaderingen bestaan wanneer de PSD-eigenschap expliciet wordt benut.

De primaire betekenis van het werk is de demonstratie dat voor PSD-matrices de Nyström-methode een superieur alternatief is voor de standaard Rayleigh-Ritz-methode voor het extraheren van leidende eigenparen, met aanzienlijk hogere nauwkeurigheid tegen geen bijkomende computationele kosten. De auteurs benadrukken dat deze verbetering bijzonder kritiek is in toepassingen die matrices met snel afnemende spectra omvatten, zoals kernel-matrices in machine learning en covariantiematrices in hoofdcomponentenanalyse. Het artikel merkt bescheiden op dat hoewel de theoretische grenzen zijn afgeleid voor reële matrices, analoge resultaten gelden voor complexe matrices.