Complejidad de encontrar la descomposición propia de una matriz * simétrica *

9

Esta es una versión especializada de una pregunta anterior: Complejidad de encontrar la descomposición propia de una matriz .

Para las matrices simétricas NxN, se sabe que el tiempo O (N ^ 3) es suficiente para calcular la descomposición propia. La pregunta es: ¿podemos lograr una complejidad subcúbica? Gracias.

ds.algorithms time-complexity matrices linear-algebra na.numerical-analysis Lihong Li
fuente
¿Esto realmente necesita una pregunta por separado? Seguramente, si alguien supiera la respuesta a este caso especial, lo habría dicho en la otra pregunta.
Warren Schudy
Hice hincapié en el peor de los casos en mi pregunta, así que creo que esto es justo ...
Lev Reyzin
2
¿Estás seguro de que el límite de tiempo O (N ^ 3)? Vea mi pregunta relacionada sobre la eliminación gaussiana.
Jeff el
Parece que de mathoverflow.net/questions/24287/… puede obtener para una solución aproximada . O(norte3)
Lev Reyzin

Respuestas:

2

A mi entender, este caso especial no es más fácil que el caso general. Simplemente simbólicamente, puede reducir el problema de encontrar la descomposición de valor singular (SVD) al problema de diagonalizar una matriz simétrica. Se puede leer la SVD de M de los vectores propios y los valores propios de M * M. Tenga en cuenta que la reducción implica solo una multiplicación de matriz para calcular M * M. No parece que haya problemas numéricos serios.


fuente