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

Riepilogo Tecnico: Trovare Autovalori e Autovettori Accurati di Matrici Semidefinite Positive Data una Sottospazio

Enunciato del Problema
Il lavoro affronta un problema classico nell'algebra lineare numerica: data una matrice $n \times n$ semidefinita positiva (PSD) $A$ e un sottospazio $Q$ di dimensione $k$ (rappresentato da una matrice di base ortonormale $Q \in \mathbb{R}^{n \times k}$) che approssima il sottospazio degli autovettori principali di $A$, come si possono estrarre autovalori e autovettori ad alta accuratezza? Sebbene il metodo di Rayleigh-Ritz (RR) sia l'approccio standard per questo compito, gli autori investigano se la proprietà strutturale specifica di $A$ di essere semidefinita positiva possa essere sfruttata per migliorare l'accuratezza oltre quanto offerto da RR, senza aumentare la complessità computazionale.

Metodologia
Il lavoro confronta tre metodi basati su proiezione che condividono la stessa complessità computazionale di $O(Nk + nk^2)$, dove $N$ è il costo di una moltiplicazione matrice-vettore con $A$:

1. Rayleigh-Ritz (RR): Il metodo standard che calcola gli autovalori della matrice proiettata $Q^\top A Q$. Gli autovalori approssimati sono $\hat{\lambda}_i^{(RR)} = \lambda_i(Q^\top A Q)$.
2. SVD-extract: Questo metodo sfrutta l'equivalenza tra autovalori e valori singolari per le matrici PSD. Calcola i valori singolari della proiezione unilaterale $AQ$. Gli autovalori approssimati sono $\hat{\lambda}_i^{(SVD)} = \sigma_i(AQ)$.
3. Metodo Nyström: Questo metodo costruisce un'approssimazione di rango basso di $A$, indicata come $A_{\langle Q \rangle} = AQ(Q^\top AQ)^\dagger (AQ)^\top$, ed estrae gli autovalori da questa approssimazione. Gli autovalori approssimati sono $\hat{\lambda}_i^{(Nys)} = \lambda_i(A_{\langle Q \rangle})$.

Gli autori analizzano questi metodi teoricamente modellando il sottospazio $Q$ come un'approssimazione $\epsilon$ del sottospazio invariante dominante $U_1$ di $A$. Utilizzano l'analisi delle perturbazioni, i complementi di Schur e le proprietà delle matrici PSD per derivare limiti di errore per le approssimazioni degli autovalori.

Contributi Chiave e Risultati Teorici

• Gerarchia di Accuratezza per gli Autovalori Principali: Il lavoro stabilisce un ordinamento rigoroso dell'accuratezza per l'approssimazione degli autovalori principali (quelli corrispondenti ai più grandi autovalori di $A$). Gli autori dimostrano la seguente disuguaglianza per gli autovalori approssimati:
  $$\lambda_i(A) \geq \lambda_i(A_{\langle Q \rangle}) \geq \sigma_i(AQ) \geq \lambda_i(Q^\top A Q)$$
  Di conseguenza, l'errore assoluto soddisfa:
  $$|\lambda_i(A) - \hat{\lambda}_i^{(RR)}| \geq |\lambda_i(A) - \hat{\lambda}_i^{(SVD)}| \geq |\lambda_i(A) - \hat{\lambda}_i^{(Nys)}|$$
  Ciò dimostra che Nyström fornisce le stime più accurate, seguito da SVD-extract, con RR che è il meno accurato.

• Accuratezza di Ordine Superiore di Nyström: Gli autori derivano limiti di errore quantitativi che mostrano come Nyström raggiunga un'accuratezza di ordine superiore rispetto a RR e SVD-extract. Nello specifico, quando lo spettro di $A$ decade rapidamente (cioè $\lambda_1 \gg \lambda_{k+1}$), l'errore del metodo Nyström per gli autovalori principali può essere inferiore a quello di RR e SVD-extract per un fattore proporzionale a $\lambda_1(A)/\lambda_{k+1}(A)$. Questo miglioramento può essere arbitrariamente grande.

• Inversione per gli Autovalori Trailing: Il lavoro nota che la situazione si inverte quando si mirano agli autovalori trailing (più piccoli). In questo regime, il metodo Nyström performa male e RR diventa il metodo più accurato. Gli autori attribuiscono questo al fatto che il sottospazio $\text{span}(AQ)$ (usato da Nyström e SVD-$\tilde{U}$) è una migliore approssimazione del sottospazio invariante principale $U_1$ ma una peggiore approssimazione del sottospazio invariante trailing $U_2$ rispetto a $\text{span}(Q)$.

• Rimedio per gli Autovalori Trailing: Per affrontare le scarse prestazioni di Nyström per gli autovalori trailing, gli autori suggeriscono una strategia di shift-and-flip. Calcolando le coppie autovalore-autovettore principali della matrice shiftata $\gamma I - A$ (dove $\gamma \geq \lambda_{\max}(A)$), il metodo Nyström può essere applicato efficacemente per recuperare gli autovalori trailing della matrice originale.

Risultati ed Esperimenti Numerici
I risultati teorici sono validati attraverso esperimenti numerici:

• Autovalori Principali: Quando $A$ ha uno spettro a decadimento rapido (decadimento esponenziale), il metodo Nyström supera significativamente RR e SVD-extract, con pendenze di errore che indicano una convergenza di ordine superiore. Quando lo spettro decade lentamente (algebrico o lineare), il vantaggio di Nyström diminuisce ma rimane presente.
• Autovettori: Tendenze simili sono osservate per le approssimazioni degli autovettori. I metodi che utilizzano il sottospazio $\text{span}(AQ)$ (Nyström e SVD-$\tilde{U}$) producono autovettori principali più accurati rispetto a quelli limitati a $\text{span}(Q)$ (RR e SVD-$Q\tilde{V}$).
• Autovalori Trailing: Gli esperimenti confermano che RR è superiore per gli autovalori trailing, mentre Nyström fallisce a meno che non venga impiegata la tecnica shift-and-flip.

Significato e Affermazioni
Il lavoro afferma di risolvere un'apparente incoerenza nella letteratura: mentre RR è noto per essere ottimale nel senso della caratterizzazione min-max e della proiezione su sottospazi, questa ottimalità non preclude l'esistenza di approssimazioni di autovalori più accurate quando la proprietà PSD è sfruttata esplicitamente.

Il significato primario del lavoro è la dimostrazione che per le matrici PSD, il metodo Nyström è un'alternativa superiore al metodo standard di Rayleigh-Ritz per estrarre le coppie principali, offrendo un'accuratezza significativamente più alta senza costi computazionali aggiuntivi. Gli autori sottolineano che questo miglioramento è particolarmente critico nelle applicazioni che coinvolgono matrici con spettri a rapido decadimento, come le matrici kernel nell'apprendimento automatico e le matrici di covarianza nell'analisi delle componenti principali. Il lavoro nota modestamente che, sebbene i limiti teorici siano derivati per matrici reali, risultati analoghi valgono per le matrici complesse.