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

Resumo Técnico: Encontrando Autovalores e Autovetores Precisos de Matrizes Semidefinidas Positivas Dado um Subespaço

Enunciado do Problema
O artigo aborda um problema clássico em álgebra linear numérica: dada uma matriz $A$ semidefinida positiva (SDP) de dimensão $n \times n$ e um subespaço $Q$ de dimensão $k$ (representado por uma matriz de base ortonormal $Q \in \mathbb{R}^{n \times k}$) que aproxima o autoespaço dominante de $A$, como pode-se extrair autovalores e autovetores de alta precisão? Embora o método de Rayleigh-Ritz (RR) seja a abordagem padrão para essa tarefa, os autores investigam se a propriedade estrutural específica de $A$ ser SDP pode ser explorada para melhorar a precisão além do que o RR oferece, sem aumentar a complexidade computacional.

Metodologia
O artigo compara três métodos baseados em projeção que compartilham a mesma complexidade computacional de $O(Nk + nk^2)$, onde $N$ é o custo de uma multiplicação matriz-vetor com $A$:

1. Rayleigh-Ritz (RR): O método padrão que calcula os autovalores da matriz projetada $Q^\top A Q$. Os autovalores aproximados são $\hat{\lambda}_i^{(RR)} = \lambda_i(Q^\top A Q)$.
2. SVD-extract: Este método explora a equivalência entre autovalores e valores singulares para matrizes SDP. Calcula os valores singulares da projeção unilateral $AQ$. Os autovalores aproximados são $\hat{\lambda}_i^{(SVD)} = \sigma_i(AQ)$.
3. Método de Nyström: Este método constrói uma aproximação de baixo posto de $A$, denotada como $A_{\langle Q \rangle} = AQ(Q^\top AQ)^\dagger (AQ)^\top$, e extrai os autovalores dessa aproximação. Os autovalores aproximados são $\hat{\lambda}_i^{(Nys)} = \lambda_i(A_{\langle Q \rangle})$.

Os autores analisam esses métodos teoricamente modelando o subespaço $Q$ como uma $\epsilon$-aproximação do subespaço invariante dominante $U_1$ de $A$. Eles utilizam análise de perturbação, complementos de Schur e propriedades de matrizes SDP para derivar limites de erro para as aproximações de autovalores.

Contribuições Principais e Resultados Teóricos

• Hierarquia de Precisão para Autovalores Dominantes: O artigo estabelece uma ordenação estrita de precisão para a aproximação dos autovalores dominantes (aqueles correspondentes aos maiores autovalores de $A$). Os autores provam a seguinte desigualdade para os autovalores aproximados:
  $$\lambda_i(A) \geq \lambda_i(A_{\langle Q \rangle}) \geq \sigma_i(AQ) \geq \lambda_i(Q^\top A Q)$$
  Consequentemente, o erro absoluto satisfaz:
  $$|\lambda_i(A) - \hat{\lambda}_i^{(RR)}| \geq |\lambda_i(A) - \hat{\lambda}_i^{(SVD)}| \geq |\lambda_i(A) - \hat{\lambda}_i^{(Nys)}|$$
  Isso demonstra que o Nyström fornece as estimativas mais precisas, seguido pelo SVD-extract, com o RR sendo o menos preciso.

• Precisão de Ordem Superior do Nyström: Os autores derivam limites de erro quantitativos mostrando que o Nyström alcança precisão de ordem superior em comparação com o RR e o SVD-extract. Especificamente, quando o espectro de $A$ decai rapidamente (isto é, $\lambda_1 \gg \lambda_{k+1}$), o erro do método de Nyström para os autovalores dominantes pode ser menor que o do RR e do SVD-extract por um fator proporcional a $\lambda_1(A)/\lambda_{k+1}(A)$. Essa melhoria pode ser arbitrariamente grande.

• Reversão para Autovalores Trailing: O artigo observa que a situação se inverte ao visar os autovalores trailing (menores). Nesse regime, o método de Nyström performa mal, e o RR torna-se o método mais preciso. Os autores atribuem isso ao fato de que o subespaço $\text{span}(AQ)$ (usado pelo Nyström e SVD-$\tilde{U}$) é uma melhor aproximação do subespaço invariante dominante $U_1$, mas uma pior aproximação do subespaço invariante trailing $U_2$, em comparação com $\text{span}(Q)$.

• Remédio para Autovalores Trailing: Para abordar o mau desempenho do Nyström para autovalores trailing, os autores sugerem uma estratégia de deslocamento e inversão (shift-and-flip). Ao calcular os pares próprios dominantes da matriz deslocada $\gamma I - A$ (onde $\gamma \geq \lambda_{\max}(A)$), o método de Nyström pode ser aplicado efetivamente para recuperar os autovalores trailing da matriz original.

Resultados e Experimentos Numéricos
As descobertas teóricas são validadas através de experimentos numéricos:

• Autovalores Dominantes: Quando $A$ possui um espectro de decaimento rápido (decaimento exponencial), o método de Nyström supera significativamente o RR e o SVD-extract, com inclinações de erro indicando convergência de ordem superior. Quando o espectro decai lentamente (algébrico ou linear), a vantagem do Nyström diminui, mas permanece presente.
• Autovetores: Tendências semelhantes são observadas para aproximações de autovetores. Métodos que utilizam o subespaço $\text{span}(AQ)$ (Nyström e SVD-$\tilde{U}$) produzem autovetores dominantes mais precisos do que aqueles restritos a $\text{span}(Q)$ (RR e SVD-$Q\tilde{V}$).
• Autovalores Trailing: Experimentos confirmam que o RR é superior para autovalores trailing, enquanto o Nyström falha, a menos que a técnica de deslocamento e inversão seja empregada.

Significado e Afirmações
O artigo afirma resolver uma aparente inconsistência na literatura: embora o RR seja conhecido por ser ótimo no sentido da caracterização min-max e projeção de subespaço, essa optimalidade não impede a existência de aproximações de autovalores mais precisas quando a propriedade SDP é explicitamente explorada.

O significado primário do trabalho é a demonstração de que, para matrizes SDP, o método de Nyström é uma alternativa superior ao método padrão de Rayleigh-Ritz para extrair pares próprios dominantes, oferecendo precisão significativamente maior sem custo computacional adicional. Os autores enfatizam que essa melhoria é particularmente crítica em aplicações envolvendo matrizes com espectros de decaimento rápido, como matrizes de kernel em aprendizado de máquina e matrizes de covariância em análise de componentes principais. O artigo nota modestamente que, embora os limites teóricos sejam derivados para matrizes reais, resultados análogos valem para matrizes complexas.