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

Resumen Técnico: Búsqueda de Valores y Vectores Propios Precisos de Matrices Semidefinidas Positivas Dado un Subespacio

Enunciado del Problema
El artículo aborda un problema clásico en el álgebra lineal numérica: dado una matriz $n \times n$ semidefinida positiva (PSD) $A$ y un subespacio $Q$ de dimensión $k$ (representado por una matriz de base ortonormal $Q \in \mathbb{R}^{n \times k}$) que aproxima el espacio propio principal de $A$, ¿cómo se pueden extraer valores y vectores propios de alta precisión? Aunque el método de Rayleigh-Ritz (RR) es el enfoque estándar para esta tarea, los autores investigan si la propiedad estructural específica de que $A$ sea PSD puede explotarse para mejorar la precisión más allá de lo que ofrece RR, sin aumentar la complejidad computacional.

Metodología
El artículo compara tres métodos basados en proyección que comparten la misma complejidad computacional de $O(Nk + nk^2)$, donde $N$ es el costo de una multiplicación matriz-vector con $A$:

1. Rayleigh-Ritz (RR): El método estándar que calcula los valores propios de la matriz proyectada $Q^\top A Q$. Los valores propios aproximados son $\hat{\lambda}_i^{(RR)} = \lambda_i(Q^\top A Q)$.
2. Extracción-SVD: Este método explota la equivalencia entre valores propios y valores singulares para matrices PSD. Calcula los valores singulares de la proyección unilateral $AQ$. Los valores propios aproximados son $\hat{\lambda}_i^{(SVD)} = \sigma_i(AQ)$.
3. Método de Nyström: Este método construye una aproximación de rango bajo de $A$, denotada como $A_{\langle Q \rangle} = AQ(Q^\top AQ)^\dagger (AQ)^\top$, y extrae los valores propios de esta aproximación. Los valores propios aproximados son $\hat{\lambda}_i^{(Nys)} = \lambda_i(A_{\langle Q \rangle})$.

Los autores analizan estos métodos teóricamente modelando el subespacio $Q$ como una $\epsilon$-aproximación al subespacio invariante dominante $U_1$ de $A$. Utilizan análisis de perturbación, complementos de Schur y propiedades de las matrices PSD para derivar cotas de error para las aproximaciones de los valores propios.

Contribuciones Clave y Resultados Teóricos

• Jerarquía de Precisión para Valores Propios Principales: El artículo establece un orden estricto de precisión para aproximar los valores propios principales (aquellos correspondientes a los valores propios más grandes de $A$). Los autores prueban la siguiente desigualdad para los valores propios aproximados:
  $$\lambda_i(A) \geq \lambda_i(A_{\langle Q \rangle}) \geq \sigma_i(AQ) \geq \lambda_i(Q^\top A Q)$$
  En consecuencia, el error absoluto satisface:
  $$|\lambda_i(A) - \hat{\lambda}_i^{(RR)}| \geq |\lambda_i(A) - \hat{\lambda}_i^{(SVD)}| \geq |\lambda_i(A) - \hat{\lambda}_i^{(Nys)}|$$
  Esto demuestra que Nyström proporciona las estimaciones más precisas, seguido por la extracción-SVD, siendo RR el menos preciso.

• Precisión de Orden Superior de Nyström: Los autores derivan cotas de error cuantitativas que muestran que Nyström logra una precisión de orden superior en comparación con RR y la extracción-SVD. Específicamente, cuando el espectro de $A$ decae rápidamente (es decir, $\lambda_1 \gg \lambda_{k+1}$), el error del método de Nyström para los valores propios principales puede ser menor que el de RR y la extracción-SVD por un factor proporcional a $\lambda_1(A)/\lambda_{k+1}(A)$. Esta mejora puede ser arbitrariamente grande.

• Inversión para Valores Propios Trailing: El artículo señala que la situación se invierte cuando se apuntan a los valores propios trailing (más pequeños). En este régimen, el método de Nyström funciona mal y RR se convierte en el método más preciso. Los autores atribuyen esto al hecho de que el subespacio $\text{span}(AQ)$ (utilizado por Nyström y SVD-$\tilde{U}$) es una mejor aproximación del subespacio invariante principal $U_1$ pero una peor aproximación del subespacio invariante trailing $U_2$ en comparación con $\text{span}(Q)$.

• Remedio para Valores Propios Trailing: Para abordar el mal rendimiento de Nyström para los valores propios trailing, los autores sugieren una estrategia de desplazamiento e inversión. Al calcular los pares propios principales de la matriz desplazada $\gamma I - A$ (donde $\gamma \geq \lambda_{\max}(A)$), el método de Nyström puede aplicarse eficazmente para recuperar los valores propios trailing de la matriz original.

Resultados y Experimentos Numéricos
Los hallazgos teóricos se validan mediante experimentos numéricos:

• Valores Propios Principales: Cuando $A$ tiene un espectro de decaimiento rápido (decaimiento exponencial), el método de Nyström supera significativamente a RR y a la extracción-SVD, con pendientes de error que indican convergencia de orden superior. Cuando el espectro decae lentamente (algebraica o linealmente), la ventaja de Nyström disminuye pero sigue presente.
• Vectores Propios: Se observan tendencias similares para las aproximaciones de vectores propios. Los métodos que utilizan el subespacio $\text{span}(AQ)$ (Nyström y SVD-$\tilde{U}$) producen vectores propios principales más precisos que aquellos restringidos a $\text{span}(Q)$ (RR y SVD-$Q\tilde{V}$).
• Valores Propios Trailing: Los experimentos confirman que RR es superior para los valores propios trailing, mientras que Nyström falla a menos que se emplee la técnica de desplazamiento e inversión.

Significado y Afirmaciones
El artículo afirma resolver una aparente inconsistencia en la literatura: si bien se sabe que RR es óptimo en el sentido de la caracterización min-max y la proyección de subespacios, esta optimalidad no excluye la existencia de aproximaciones de valores propios más precisas cuando la propiedad PSD se explota explícitamente.

El significado principal de la obra es la demostración de que, para matrices PSD, el método de Nyström es una alternativa superior al método estándar de Rayleigh-Ritz para extraer pares propios principales, ofreciendo una precisión significativamente mayor sin costo computacional adicional. Los autores enfatizan que esta mejora es particularmente crítica en aplicaciones que involucran matrices con espectros de decaimiento rápido, como las matrices de kernel en aprendizaje automático y las matrices de covarianza en el análisis de componentes principales. El artículo nota modestamente que, si bien las cotas teóricas se derivan para matrices reales, resultados análogos se mantienen para matrices complejas.